# Solving Kakuro puzzles

There exist
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
general problem:
*
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
for `tango.`
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