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