Algorithm

The problem

A Q-Less roll is 12 letter dice. A solution places all 12 letters into one connected crossword grid where every horizontal and vertical run of letters is a valid dictionary word of 3 to 12 letters. The solver answers, for any roll: can it be solved — and eventually, in how many distinct ways?

Step 1 — Find every candidate word

Every word in a solution must be buildable from the roll's 12 letters. The solver precomputes a 26-bit mask of each dictionary word's letters, so most of the 196,000-word NASPA list is eliminated with a single bitwise check per word; survivors get an exact letter-count comparison. A typical roll keeps between 50 and 900 candidate words.

Step 2 — Build crosswords by backtracking

The search places one candidate word, then repeatedly attaches more words through shared letters, exploring every legal placement and undoing each one after exploring it. A placement is legal only if overlapping letters match, the letters it adds are still available on the dice, and every run of letters it creates is either a valid word or could still grow into one — partial runs are allowed mid-search if they are a substring of some candidate word, which lets words emerge letter-by-letter from several crossings. When all 12 dice are used, the whole board is validated one final time.

Two design decisions matter for completeness. First, any solution's words form a connected web through their shared cells, so building word-by-word from every possible starting word reaches every solution. Second, a solution and its transpose (rows and columns swapped) are counted as one, and layouts are compared after shifting to a common origin, so the same shape found in different positions or build orders is never counted twice.

Step 3 — Prove the unsolvable ones

When a roll has no solution, the search must exhaust every combination before saying so — that is what makes it a proof rather than a guess. Three things make this affordable: the same board state is reachable through many placement orders, so every visited state is remembered and never explored twice (memoization); the search runs on PyPy, a just-in-time compiled Python that runs this workload about ten times faster; and ten worker processes each take a roll at a time, keeping all CPU cores busy.

Current scope — first solution only

Enumerating every solution of every roll is the long-term goal, but it costs hours per roll. The current sweep stops at the first solution found, which settles solvable rolls in well under a second and typically proves unsolvable rolls in seconds. Full enumeration will return as an on-demand feature for individual rolls.

Why trust it

The solver was cross-checked against an independently written brute-force enumerator that shares no search logic with it — no pruning, different board representation, validation only on finished boards. On test rolls, both produced the identical set of solutions, layout for layout. The word list is the NASPA Word List 2023; a word is a word because that dictionary says so, and every stored result records how many candidate words the roll had, how many placements were attempted, and how long the search took.