# 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](word-solver.md), 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:

1. **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.

2. **Sorting & Determinism:**
    * The theme words are sorted by length (descending) and then
      alphabetically to enforce a deterministic run.

3. **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.
