Задача на многопоточность?
Напишите свою реализацию пула потоков, которые постоянно выбирают из общей очереди задания (объект, реализующий какой-нибудь интерфейс с методом execute) и генератор таких задач. НаУчитесь писать блокирующие очереди и реализуете паттерн producer-consumer. Потом генератор сделайте многопоточным. Потом попробуйте очередь сделать распределенной (по нескольким машинам, например сделайте пару виртуалок), чтоб вы могли распределять нагрузку по узлам кластера из своих виртуалок.
А дальше уже природа вам подскажет, что еще туда прилепить))
Разгадыватель японских кроссвордов — большое поле для оптимизаций.

Многопоточность — одна из таких оптимизаций. В каждый момент времени можно пытаться найти новую информацию в столбцах и строках, и в случае появления такой, перезапустить процесс поиска новой информации на пересечении.