Next / Previous / Contents / Shipman's homepage

3.1. Performance notes

The script uses two techniques to solve the puzzle. In the first phase, it makes one or more passes through puzzle using a technique called “cyclic reduction;”, repeating these passes until the puzzle is solved or until this technique makes no more progress. During this phase you will see messages that look like this:

=== Cyclic reduction: 135 choices for 82 slots
=== Cyclic reduction: 82 choices for 82 slots

These example lines came from a puzzle with 82 words; only two passes of cyclic reduction were necessary to find the solution.

Most puzzles are solved in less than a second in the cyclic reduction phase. For uncommonly difficult puzzles, the script goes into a second phase using a recursive algorithm that will, given sufficient time, find solutions to any puzzle. The only puzzle the author has tried that took more than a few seconds was a 21×21 puzzle with 56 slots, all with six letters. On a 3.6GHz 64-bit Intel processor this puzzle took over forty hours to find two solutions. The puzzle was symmetric about its main diagonal, so the two solutions are also symmetric.