cw_gen lets you generate crossword puzzles by specifying a word list and a grid to fill in.
The unix binary is already included as cw_gen. To re-build, run the build script:
sh build.sh
./cw_gen [OPTIONS]| Option | Description | Type | Default |
|---|---|---|---|
-s |
Dimensions of the crossword to be generated, in the format columns,rows. Size must be greater than 1x1. Large sizes may take several minutes or more to solve, especially if a large dictionary is used, or if difficult or no grid contents are specified. |
int,int | 4,4 |
| Option | Description | Type | Default |
|---|---|---|---|
-c |
Crossword grid to fill in, from top left to bottom right by row, and contained within quotes. Each char represents one tile and must be a set letter (a-z), wildcard (?), or black tile (single space). Total length must equal rows * columns. If left unspecified, all tiles are set to wildcards. |
string | none |
| Option | Description | Type | Default |
|---|---|---|---|
-d |
Word list to use. Possible options from smallest to largest are small, medium, large, xlarge, giant, and all. Larger dictionaries are more effective for finding solutions for larger puzzles at the cost of likely increased runtime and possibly more unfamiliar words chosen. |
string | xlarge |
| Option | Description | Type | Default |
|---|---|---|---|
-e |
Preset example crossword generation params, overriding size, contents, and dictionary if specified. Possible options are empty, cross, bridge, stairs, donut, crosshair1, and crosshair2. |
string | none |
| Option | Description | Type | Default |
|---|---|---|---|
-v |
Minimum verbosity for print statements. Possible options in decreasing level are fatal, error, warning, info, and debug. |
string | fatal |
| Option | Description | Type | Default |
|---|---|---|---|
-p |
Enables progress bar; useful when generating larger crossword puzzles with longer runtimes. Disabled by default unless specified. | none | none |
| Option | Description | Type | Default |
|---|---|---|---|
-h |
Print usage to display a summary of all options, their usage, and descriptions. | none | none |
Since generation is done purely via heuristics without randomness, re-generating a crossword with the same parameters is likely to return the same output, especially if not many valid solutions for those parameters exist. Also please note that if used, the grid contents string length must match the puzzle size or the default 4x4 puzzle size if none is specified.
This project uses the Catch2 v2.x testing framework to test each module. To run the test suite, navigate to the test/ directory and run the test script:
cd test
sh test.shAfter parsing the crossword parameters, cw_gen constructs a constraint satisfaction problem (CSP) that represents the crossword. CSP variables symbolize words, and their domains are initially set to all the words from the user-specified dictionary that fit in that slot. CSP constraints occur when any two variables intersect in the crossword; those two letters in each of the word variables must be equal.
Using a combination of the AC-3 algorithm and backtracking, the CSP iteratively assigns values to variables until a valid solution is found or the search space is exhausted.
- Incorporate word frequency or other scoring heuristics into word selection to create minimize unfamiliar words used and speed up generation
- Explore alternatives to arc consistency such as path consistency to improve CSP simplification performance
- Investigate different CSP solving options in addition to backtracking like the VLNS method, local search, and/or linear programming
- Upgrade CSPs to be dynamic CSPs to allow insertion of black tiles to complete crosswords. This will minimize user effort required to avoid impossible crossword grid patterns
- Clue generation/lookup