По словнику.

як в таке грати?
також зі словником?

Було б простіше, якби слова йшли тільки горизонтально або вертикально, а не зигзагами. Тоді, після того, як упав кубик, можна згенерувати регекс для горизонталі й вертикалі, де лежить новий кубик (слово, яке можна зняти, гарантовано перетинається з новим кубиком). Скажімо, якщо на полі ми маємо

. . . а б в . . . г ґ д
е є ж з и і ї й к л м н
о п р с т у ф х ц ч ш щ

то нам треба шукати слова, що містять "(а)?б(в)?|б(и(т)?)?" ^*
Робимо пошук за регексом по базі слів, беремо найдовше знайдене, стираємо зайняті ним клітинки на полі...
В принципі, подібним чином можна шукати й зигзаги, але генеровані для них регекси будуть дещо складнішими.

(Не впевнений, що варіант з регулярками найкращий з точки зору швидкості роботи, але я робив би так).

*) Порядок літер може бути не лише прямим, а й зворотнім — тобто, в наведений вираз треба ще дописати перевірку для зворотнього порядку символів.