The Electric Puppet Crossword Generator

Prompted by T. Campbell's invention of the cruciverbacomic, we are pleased to present the Electric Puppet Crossword Generator, a free program for automatically generating crossword puzzles from a starting grid and a dictionary.

Here's what it looks like in action:

$ cat > tcampbell.grid << EOF
...@.....
...@.....
...@.....
......@@@
@@@......
.....@...
.....@...
.....@...
EOF

$ ./eptcross.py tcampbell.grid
ave@farsi
com@omaha
elm@ripen
stakes@@@
@@@lahore
attar@did
nahum@dog
abyss@sty

Read on for instructions on:

Installing on:
Running the program
Performance benchmarks
Getting pre-generated crosswords if you don't want to download the program
License notes

Any updates to the program will be posted on our nifty news feed. Please send any questions, comments, or patches to markv [at] eptcomic.com

Installing

Linux

Download the tarball: eptcross.0.1.tar.gz (e.g. to your home directory)
Open a terminal window and cd to the directory with the tarball
```
tar -zxvf eptcross.0.1.tar.gz
```
```
cd eptcross
```
If you don't have a python interpreter, install Python2.7 from python.org or through your package manager (e.g.,
```
apt-get install python
```
). Most Linux distributions come with Python pre-installed. You can check if you have it with
```
which python
```

Try out the program on a simple 4x4 grid:

./eptcross.py 4blank.grid --dictionary words

If you have a system dictionary in /usr/share/dict/words, you can try this instead:
```
./eptcross.py 4blank.grid
```
See below for more tips on runnning the program, or type
```
./eptcross.py --help
```
for a summary of the command-line options.

OS X

Download the tarball: eptcross.0.1.tar.gz to your home directory (e.g., /Users/markv/)
Open a terminal window (Look under Applications->Utilities in the Finder)
```
tar -zxvf eptcross.0.1.tar.gz
```
```
cd eptcross
```

Try out the program on a simple 4x4 grid:

./eptcross.py 4blank.grid --dictionary words

See below for more tips on runnning the program, or type
```
./eptcross.py --help
```
for a summary of the command-line options.

Windows

Download the zip archive: eptcross-0-1.zip and unzip it.
If you don't have a python interpreter, install Python2.7 from python.org.
Open a command prompt and cd to the unzipped directory

Try out the program on a simple 4x4 grid:

python.exe eptcross.py 4blank.grid --dictionary words

See below for more tips on runnning the program, or type
```
python.exe eptcross.py --help
```
for a summary of the command-line options.

Running the Program

Usage: eptcross.py [options] grid.txt

eptcross.py generates a crossword by filling in a grid with words from
a user- provided or system-default dictionary.  Input and output grids
are formatted as text: each line gives a row of the crossword, '.'
indicates empty spaces, '@' indicates black squares, and all other
characters indicate filled squares (whitespace is ignored). 

E.g.:

     ..w..@...
     cross@...
     ..r@.....
     ..d@.....

Any words in a partially-filled input grid must be present in the
dictionary (this can be ensured by using the --dictionary option twice
to concatenate the system dictionary with a custom dictionary).  All
rows must be the same length.

Options:
  -h, --help            show this help message and exit
  -D FILENAME, --dictionary=FILENAME
                        Load words from FILENAME.  You may give this option
                        multiple times to concatenate multiple dictionaries.
  -s SEED, --seed=SEED  Seed the random number generator with SEED.  A given
                        SEED will always generate the same solution for a
                        given problem. If SEED is not given, the default
                        system seeding will be used.
  -d, --debug           Turn on verbose debugging messages.
  -n NODES, --maxnodes=NODES
                        Explore at most NODES nodes of the search tree before
                        giving up.  Larger values will solve more puzzles, but
                        will increase the maximum possible run time. Set NODES
                        to 0 for unbounded searches.
  -c, --showclues       Print a clue list with the solution.  (Default is to
                        only print the solved grid).

Benchmarks

The tarball and zip archives come with several sample grid files that can be used as input to the program. Here are box plots of the run time distributions for 100 runs on each grid. The six runs where the grid was not solved after exploring the default 100000 nodes are marked with red x's. Most of the grids are solved in under a second, while the 5x5 blank and 9x9 slotted grids take 5 to 10 seconds. For a small number of runs on the larger grids, an unfortunate choice of seed can result in a much longer run time or failure to solve the grid.

Extending the largest sample grids (e.g., to a 6x6 blank grid) leads to much longer run times due to combinatorial expansion (although adding strategic black squares can ameliorate this). We hope to improve this in future versions with more aggressive pruning. Fortunately, the run times for the T. Campbell grid (far right) are well behaved, so the current version is ready for all of your cruciverbacomic needs.

Pre-generated Crosswords

Here are some pre-filled grids for people who would prefer not to download the program. Disclamer: these crosswords were automatically generated by eptcross.py from our system dictionary and have not been screened for naughty or offensive words. Caveat emptor. Each linked text file has the 97 to 100 solutions from the corresponding benchmark run.

License

The Electric Puppet Crossword Generator is free software, distributed under the GNU General Public License (eptcross.py is both the executable and the source code). The tarball and zip archives include the "words" dictionary file from the Debian dictionaries-common package, which is also distributed under the GNU General Public License.