Solving Kakuro puzzles
programs in CWEB by Don Knuth that solve Sudoku puzzles by transforming
them to generalized exact cover problems.
It is possible to solve Kakuro puzzles this way too, but it is horribly
tricky to design a valid input file for Knuth's program dance.
I have therefore modified dance to solve the following more
Given a matrix whose elements are nonnegative integers,
find all subsets of its rows whose sum is at most a specified target value
in all columns and exactly the target in all ``primary'' columns.
The program tango which solves the above problem.
2010-08-04: revised to allow empty lines and comments in input files.
The program kakuro which transforms a
file describing a Kakuro puzzle in a user-friendly way, to an input
file for tango.
The program jigsaw, an enhancement
of Knuth's Sudoku program, which
solves standard as well as jigsaw Sudokus by generating input suitable
A sample Kakuro, tough but
known to have a unique solution. Unlike human
solvers, the program is not allowed to rely on the uniqueness!
A sample jigsaw Sudoku.
Tango input file for finding all solutions of a Tetris cube. Read the comments in the file.
You can convert the programs to C by ctangle and obtain
reasonably good documentation of the code and algorithms by cweave.
Both of these are supplied with any recent