Algorithm

The problem

A roll is 12 letter dice. A solution puts all 12 into one connected grid where every across and down run is a valid 3-to-12-letter word. I answer, for any roll: can it be solved, and in how many ways?

Step 1: Find every anagram

Every word in a solution has to be buildable from the roll's letters. I give each dictionary word a 26-bit letter mask, so one bitwise check rules out most of the 196,000 words; the rest get an exact letter-count check. A roll keeps 50 to 900 anagrams.

Step 2: Build crosswords by backtracking

I place one anagram, then attach more words through shared letters, trying every legal placement and undoing each after. A placement is legal if overlaps match, its new letters are still on the dice, and every run it makes is a word or the start of one. When all 12 dice are down, I check the whole board once more.

Two details keep it complete. A solution's words always connect through shared cells, so building from every starting word reaches every solution. And a layout and its transpose count as one, compared after shifting to a common origin, so nothing is counted twice.

Step 3: Prove the unsolvable ones

To call a roll unsolvable, I have to try everything first. Three things keep that cheap: I remember each board state so I never re-explore it, I run on PyPy (about 10x faster here), and 10 worker processes each take a roll at a time.

Current scope: first solution only

Finding every solution of every roll costs hours per roll, so for now I stop at the first: solvable rolls settle in under a second, unsolvable ones in seconds. Full enumeration is available on demand per roll.

Why trust it

I cross-checked the solver against a separate brute-force one that shares no code: no pruning, a different board layout, checks only at the end. On test rolls both found the exact same solutions. The word list is the NASPA Word List 2023, and every result stores the roll's anagram count, placements tried, and search time.