The DLX library solves instances of the exact cover problem, using Dancing Links (Knuth’s Algorithm X).

Also included are programs that use the library:

• Suds: a sudoku solver that represents a sudoku puzzle as an exact cover problem instance.

• Grizzly: a "logic grid puzzle" solver. Requires my BLT library.

The following should work:

Consider the following table, where the last column is optional:

Since covering the last column is optional, there are two solutions:

1. Rows 0 and 2.

2. Row 3 by itself.

The following program should confirm this.

Suds reads from standard input and ignores all characters except for the digits and ".". Nonzero digits represent themsleves and "0" or "." represents an unknown digit.

Shows step-by-step reasoning when run with -v.

See platinum.sud for an example input.

We view a logic grid puzzle as follows. Given a MxN table of distinct symbols and some constraints, for each row except the first, we are to permute its entries so that the table satisfies the constraints.

Grizzly reads a logic grid puzzle from standard input and prints all its solutions. If run with --alg=brute, Grizzly employs brute force instead of Dancing Links.

The input should begin with M lines of N space-delimited fields, terminated by "%%" on a single line by itself. This should be followed by the constraints. Each constraint is described by a single line containing space-delimited fields. The first field is the constraint type, and the remainder are symbols.

An example 2x3 puzzle:

The meaning of each constraint type is as follows:

Thus in the above example, the original logic puzzle might have stipulated that "Carol does not play the kazoo." and "Alice plays the theremin."

Grizzly prints the transpose of the solution, possibly out of order. In other words, the symbols in the same row in the input are instead in the same column in the output, and the first symbols of the rows in the output may be in a different order than the symbols in the first row of the input.

See zebra.gr, which encodes the Zebra Puzzle.

I’m still working on the constraint language. I chose one-character commands for easy typing and parsing.

Originally, "=" meant that one column contained at least 2 of the given symbols. This is easy to check in the brute force solver, and allows some puzzles to be encoded with fewer types of rules, but it is a troublesome constraint for the Dancing Links solver so I changed the meaning to the above.

The "p" constraint (I chose "p" for "pairs") can be rewritten as two "i" constraints plus one "!" constraint, but numerous puzzles contained clues describing equalities between sets of size 2, such as: "Of Jack and Jill, one is wearing mukluks and the other was born in Timbuktu."

I found no puzzles depended on the order of the input symbols in any row apart from the first, so I shelved my original plans to support this. Puzzles only seem to care about the order of the symbols in the first row.

The "X" constraint functions as a catch-all to handle constraints that seem tricky to otherwise describe.

See COPYING for details.

This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA