Theme Words Fit Solver

Status: Implemented | Updated: February 2026

Overview

The Theme Words Fit Solver (ThemeWordsFitTask) is a specialized constraint satisfaction solver designed to determine if a set of user-provided “theme words” can be placed into a specific grid template. Unlike the general Word Solver, which fills a grid from a dictionary, this solver attempts to place a fixed, small set of words into available slots in the grid.

The algorithm uses a depth-first backtracking approach to try and place each theme word into a compatible slot. If all words can be placed without conflict, the template is considered a “MATCH”.

Algorithm

The solver operates as follows:

Preparation:
- The solver identifies all available “slots” (entries) in the puzzle grid.
- It groups these slots by length.
- It receives a list of theme words from the user.
Sorting & Determinism:
- The theme words are sorted by length (descending) and then alphabetically to enforce a deterministic run.
Recursion (Backtracking): The solver iterates through the sorted list of theme words:
- Base Case: If all words are placed, a solution is found. The task records the result (the filled grid state) and terminates.
- Recursive Step: For the current word W:
  - Look up all grid slots that match the length of W.
  - Iterate through these slots sorted by a “priority score” (preferring central/prominent slots).
  - Check: If a slot is already used by a previous word, skip it.
  - Check: If placing W in the slot conflicts with any existing letters (from words placed in crossing slots), skip it.
  - Place: If the slot is valid, “write” W into the grid overlay. Mark the slot as used.
  - Recurse: Attempt to place the next word in the list.
  - Backtrack: If the recursive call returns without a full solution:
    - “Unwrite” W from the grid overlay (restore the previous state of the cells).
    - Mark the slot as unused.
    - Continue to the next available slot.

Constraints & Limitations

1. Greedy Path Dependency

The solver tries to place words in a fixed order (Longest -> Shortest, A -> Z). It does not attempt to reorder the words if it gets stuck.

Example: If placing “WORD_A” in its preferred slot blocks “WORD_B” from fitting anywhere, the solver will backtrack and try to move “WORD_A”. However, it will not try placing “WORD_B” before “WORD_A”.
Implication: There theoretically exist valid configurations that the solver might miss because the “hardest to place” word (which should have been placed first) happened to be sorted later in the list. In practice, sorting by length descending mitigates this, as longer words are harder to fit and constrain the grid more.

2. Single Solution

By default, the solver stops after finding one valid configuration. It does not try to find the “best” configuration (e.g., one where words are most symmetrically placed). It simply answers the question: “Is it possible to fit these words?”

3. Slot Contention

All words of the same length compete for the same set of slots. The solver does not “reserve” slots. If multiple words have length 10, the first one in the sorted list gets the first pick of the length-10 slots.

Future Improvements

Permutation Search: To be truly exhaustive, the solver could try different permutations of the word order if the initial sorted order fails. This would be factorial complexity O(N!) but feasible for small N (theme sets are rarely > 5-6 words).
Better Constraints: The algorithm currently prioritizes slots closest to the center, which results in a symmetric heuristic in practice. However, the solver could be significantly improved through the implementation of more robust constraints during the search.
Word Order: We sort the words to start to make it more deterministic. Theme word order can matter in crosswords: we should try to preserve it if possible.