🧩 Constraint Solving POTD:Problem of the Day: Crossword Puzzle Solving

[github-actions[bot]]

Problem Statement

Crossword puzzle solving is the problem of filling a grid with letters such that:

• Horizontal clues are satisfied by words placed in rows
• Vertical clues are satisfied by words placed in columns
• Intersecting words must share compatible letters at their crossing points

Concrete Instance

Consider a simple 3×3 crossword:

  1 2 3
1 [ ][ ][ ]
2 [ ][ ][ ]
3 [ ][ ][ ]

Clues:

• Across: 1-Across: "A feline" (3 letters); 2-Across: "Past tense of eat" (3 letters)
• Down: 1-Down: "Possessive pronoun" (3 letters); 2-Down: "Metal container" (3 letters)

Solution:

  1 2 3
1 C A T
2 A T E
3 T E N

(CAT, ATE, CAT, TEN satisfy the clues with compatible intersections.)

Input/Output Specification

Input:

• Grid dimensions (rows × columns)
• List of clues with positions, directions (Across/Down), and word definitions
• A dictionary/word list

Output:

• Completed grid with letters placed such that:
  • All Across and Down entries form valid words from the dictionary
  • All clues are satisfied

---

Why It Matters

Puzzle entertainment & linguistics: Crosswords are enjoyed by millions worldwide; automated solving enables hint generation and puzzle validation.

Information extraction: Analyzing clue-word relationships improves natural language understanding and semantic modeling.

Constraint satisfaction benchmark: Crossword solving is a well-studied CSP with large variable domains, global constraints, and practical solver competition.

---

Modeling Approaches

Approach 1: Constraint Satisfaction Problem (CSP)

Paradigm: Classical Constraint Programming (Backtracking + Constraint Propagation)

Decision Variables:

• x_{i,j} ∈ {A, B, ..., Z} for each cell (i, j) in the grid

Constraints:

1. Domain constraints: Each cell variable is restricted to letters or blank
2. Word constraints: For each clue (position, direction, clue_text):
   • The sequence of variables along that clue must form a valid word from the dictionary
   • Use a table/domain constraint or in_set() global constraint
3. Intersection constraints: If cell (i, j) appears in both an Across and Down clue, the letter must be identical

Trade-offs:

• ✅ Strengths: Natural encoding, strong propagation via table constraints, supports partial solutions
• ❌ Weaknesses: Large domain per cell; naive search explores many invalid combinations

---

Approach 2: Constraint Logic Programming (CLP) with Word Lists

Paradigm: Logic Programming (Prolog-style) with constraints

Model Sketch:

solve_crossword(Grid) :-
    across_clues(AcrossClues),
    down_clues(DownClues),
    dictionary(Dict),
    
    % For each Across clue, pick a word from the dictionary
    maplist(pick_word(Dict), AcrossClues, AcrossWords),
    
    % For each Down clue, pick a word
    maplist(pick_word(Dict), DownClues, DownWords),
    
    % Check intersection compatibility
    check_intersections(AcrossWords, DownWords, Grid),
    
    % Constraint propagation
    labeling(Grid).

Trade-offs:

• ✅ Strengths: Declarative, modular clue handling, integrates lexicon naturally
• ❌ Weaknesses: Less efficient word filtering for dense grids; relies on backtracking

---

Approach 3: Mixed Integer Programming (MIP) with Word Encoding

Paradigm: Integer Programming (Column Generation / Set Covering)

Idea:

• Binary variables y_{w,c}: word w is placed at clue-slot c
• Binary variables z_{i,j,l}: cell (i, j) contains letter l

Constraints:

1. Clue-assignment: ∑_w y_{w,c} = 1 for each clue-slot (pick exactly one word)
2. Cell-letter: ∑_l z_{i,j,l} = 1 for each cell (pick exactly one letter)
3. Consistency: If word w is assigned to clue c and letter l is at position p in word w, then z_{i,j,l} = 1 for the corresponding cell

Trade-offs:

• ✅ Strengths: Leverages mature MIP solvers (CPLEX, Gurobi), handles optimization (maximize coverage)
• ❌ Weaknesses: Requires enumerating all valid words; can be memory-intensive for large grids

---

Example Model (Pseudo-code)

% Simple CSP model in a pseudo-declarative style

model crossword(grid_size, across_clues, down_clues, dictionary):
  variables:
    cell[i][j] ∈ {A..Z} for all i ∈ [1..rows], j ∈ [1..cols]
  
  constraints:
    % For each across clue
    for each (pos, len, clue) in across_clues:
      cells = [cell[pos.row][pos.col + k] for k in 0..len-1]
      cells in_dictionary(dictionary, clue)
    
    % For each down clue
    for each (pos, len, clue) in down_clues:
      cells = [cell[pos.row + k][pos.col] for k in 0..len-1]
      cells in_dictionary(dictionary, clue)
    
    % Intersection compatibility (implicit via cell variables)
  
  search:
    % Variable ordering heuristic: prioritize cells with fewest possible words
    for each cell in order_by_most_constrained():
      try_value_in domain(cell)
      propagate()
      backtrack_if_inconsistent()

---

Key Techniques

1. Word-List Prefiltering & Domain Reduction

Before search begins, for each clue-slot, precompute the set of valid words from the dictionary that:

• Match the known letters (if any)
• Have the correct length

This dramatically reduces the search space. Use techniques like:

• Trie-based lookup: O(length) word validation
• Pattern matching: Filter words by known letter positions (e.g., "C_T" matches "CAT")

2. Arc Consistency (AC-3) on Intersection Constraints

Maintain arc consistency between Across and Down clue-slots:

• If two clues intersect at a cell, their word domains must have a compatible letter at that position
• Remove words that violate intersection constraints
• Repeat until a fixed point (often solves small puzzles entirely without search)

3. Variable Ordering & Backtracking

• Most-Constrained-Variable (MCV) heuristic: Prioritize clue-slots with fewer valid words
• Most-Constraining-Variable (MCV): Choose clues that eliminate the most options for neighbors
• Intelligent backtracking: Upon conflict, backtrack to the source constraint rather than the most recent choice (Backjumping, Constraint-Guided Search)

---

Challenge Corner

Question 1: How would you extend this model to handle optional cells (cells that can remain blank) and multi-word clues (where a single clue describes multiple non-contiguous word slots)?

Question 2: In a large cryptic crossword with 100+ clues, how would you design a hybrid approach combining local search (random word swaps) with constraint propagation to escape from local minima faster than pure backtracking?

Question 3: Can you model crossword solving as a graph coloring problem where clues are nodes and edges represent intersection constraints? What would be the implications for solver efficiency?

---

References

1. Rossi, F., van Beek, P., & Walsh, T. (2006). Handbook of Constraint Programming. Elsevier. — Comprehensive coverage of CSP modeling and solving techniques.

2. Haralick, R. M., & Elliott, G. L. (1980). "Increasing Tree Search Efficiency for Constraint Satisfaction Problems." Artificial Intelligence, 14(3), 263–313. — Classic work on search strategies and backtracking.

3. Gottlob, G., Leone, N., & Scarcello, F. (2000). "A Comparison of Structural CSP Decomposition Methods." Artificial Intelligence, 124(2), 243–282. — Decomposition strategies for complex constraint graphs.

4. Khatib, L., Morris, P., Morris, R. A., & Rossi, F. (2001). "Temporal Constraint Reasoning with Preferences." Proceedings of IJCAI-01. — Extensions to classical CSP with preferences (relevant for clue ranking and prioritization).

---

Happy solving! 🧩

Generated by 🧩 Constraint Solving — Problem of the Day · copilot · haiku45 · 10.5 AIC · ⌖ 7.07 AIC · ⊞ 6.5K · ◷

• expires on Oct 25, 2026, 3:34 AM UTC-08:00

[github-actions[bot]]

This discussion has been marked as outdated by Constraint Solving — Problem of the Day.

A newer discussion is available at Discussion #70235.