This project is a Python-based crossword puzzle generator that models the crossword as a constraint satisfaction problem (CSP). It takes a structured grid and a list of words, and fills the grid with the words by choosing which words should go in each vertical or horizontal sequence of squares while satisfying all constraints.
- Constraint Satisfaction: Implements CSP to fill crossword puzzles.
- Node Consistency: Ensures all words in a variable's domain match the variable's length.
- Arc Consistency: Ensures that for every pair of neighboring variables, each value in the domain of one variable has a corresponding value in the domain of the other variable.
- Backtracking Search: Employs backtracking to find a complete, satisfactory assignment of variables to values.
The project is divided into two main Python files:
crossword.py: DefinesVariableandCrosswordclasses to represent the puzzle structure.generate.py: Contains theCrosswordCreatorclass with methods to generate the puzzle.
- Reads puzzle structure and word list files.
- Stores puzzle dimensions, structure, word list, variables, and overlaps.
- Provides functionality to determine neighbors for a given variable.
- Represents a sequence of squares in the crossword puzzle.
- Defined by its starting row (
i), starting column (j), direction (ACROSSorDOWN), and length.
- Holds a
crosswordobject and manages domains for each variable. - Implements functions to enforce consistency and generate the puzzle.
To use the crossword puzzle generator:
- Ensure you have Python 3.6 or higher installed.
- Clone the repository or download the source code.
- Install the Pillow library to handle image creation:
pip3 install pillow - Run the
generate.pyscript with the structure file, word list file, and optional output file name:python generator.py data/structure1.txt data/words1.txt output.png
The entry point of the crossword puzzle generator is in the generate.py script, which you can run as a command-line tool as shown in the Getting Started section.