🧩 CS50AI Project 4: Crossword Solver

An Artificial Intelligence agent that automatically solves crossword puzzles by modeling puzzle generation as a Constraint Satisfaction Problem (CSP) using AC-3 Arc Consistency and Backtracking Search. Built as part of CS50's Introduction to Artificial Intelligence with Python.

📌 Overview

This project generates solutions for crossword puzzles given a grid structure and a vocabulary list of words.

By formulating the puzzle as a Constraint Satisfaction Problem (CSP), the AI agent treats each sequence of blank spaces as a variable and assigns words from the vocabulary to variables such that all unary constraints (word lengths) and binary constraints (overlapping character intersections between intersecting words) are satisfied.

📁 Project Structure

📦 crossword-solver
┣ 📂 assets/
┣ 📂 data/             # Text files defining puzzle grid structures and word lists.
┃ ┣ 📜 structure0.txt
┃ ┣ 📜 structure1.txt
┃ ┣ 📜 structure2.txt
┃ ┣ 📜 words0.txt
┃ ┣ 📜 words1.txt
┃ ┗ 📜 words2.txt
┣ 📜 crossword.py      # Data structures for Variable and Crossword board representations.
┣ 📜 generate.py       # Core CSP solver, AC-3 algorithm, and Backtracking implementation.
┣ 📜 LICENSE
┗ 📜 README.md

🧠 AI & Constraint Satisfaction Concepts

The agent treats crossword generation as a CSP defined by variables, domains, and constraints:

• Variables: Represented by Variable objects defined by direction (across or down), word length and starting row and column.
• Domains: The initial set of all words from the vocabulary list.
• Unary Constraints: A word assigned to a variable must match its exact length.
• Binary Constraints: Intersecting variables must share the exact same character at their point of intersection.

  Variable A (Across, length 4):  _  _  [C]  _
                                        │
  Variable B (Down, length 3):         [C]
                                        _
                                        _

Core Algorithms & Optimization Heuristics (generate.py)

1. Node Consistency (enforce_node_consistency): Removes any word from a variable's domain that does not match the required variable length.
2. Arc Consistency (ac3 & revise): Maintains binary constraints across all variable pairs. If a word in Variable $X$'s domain has no possible matching word in intersecting Variable $Y$'s domain, that word is pruned from $X$'s domain.
3. Backtracking Search (backtrack): Executes a depth-first search to assign words to unassigned variables, maintaining constraint consistency at each step and backtracking when dead ends are reached.
4. Variable Selection Heuristics (select_unassigned_variable):
   • Minimum Remaining Values (MRV): Selects the unassigned variable with the fewest remaining words in its domain.
   • Degree Heuristic: Breaks ties in MRV by selecting the variable with the highest number of overlapping neighbors.
5. Value Ordering Heuristic (order_domain_values):
   • Least-Constraining Value (LCV): Orders candidate words by how few choices they eliminate from the domains of neighboring variables.

🚀 Getting Started

Prerequisites

• Python 3.10+

Installation

1. Clone the repository:

git clone https://github.com/fresnicoff/crossword-solver.git
cd crossword-solver

2. (Optional) Create and activate a virtual environment:

python3 -m venv .venv
source .venv/bin/activate

🎮 Usage

To solve a crossword puzzle, run generate.py by providing a structure file and a word list file. Optionally, specify an output image file name (e.g., output.png):

python generate.py data/structure1.txt data/words1.txt output.png

Example Output

██████████████
███████M████R█
█INTELLIGENCE█
█N█████N████S█
█F██LOGIC███O█
█E█████M████L█
█R███SEARCH█V█
███████X████E█
██████████████

When an output image path is supplied, the program generates an image file visualizing the filled grid layout.