Project
Constraint-Based Crossword Solver
A Python solver that models crossword generation as a constraint satisfaction problem using node consistency, arc consistency, backtracking search, and heuristics.
Overview
This project implements a crossword generation solver by treating crossword slots as variables and candidate words as domains. It originated from CS50AI coursework and is presented here as a focused implementation of classical AI search techniques in Python.
The solver works with a crossword structure and word list, then searches for an assignment that satisfies slot lengths and overlapping-letter constraints. It demonstrates how a structured problem can be modeled explicitly before applying search.
Problem
Crossword generation requires assigning words to grid slots while satisfying length constraints and shared-letter overlaps. A brute-force search can become expensive quickly as the word list grows and the crossword structure becomes more constrained.
Approach
The solver first enforces node consistency by removing words that do not match slot lengths, then applies arc consistency to reduce domains based on overlaps between neighboring slots. It uses backtracking search with variable and value ordering heuristics to find valid assignments more efficiently than naive enumeration.
Outcome
The project demonstrates how classical AI techniques can solve structured search problems by combining constraint propagation with recursive search. It produces valid crossword assignments when the provided structure and word list admit a solution.
Tradeoffs
This project reinforced the value of modeling a problem before coding the search. It also showed how pruning, constraint propagation, and heuristic choices can make a reasoning-heavy Python program clearer and more effective.