Properties of, and Solutions to, Kakuro and Related Puzzles.

Kakuro is a logic puzzle that has strong connections with crosswords. Within an nm grid, a number of initially empty cells make up overlapping continuous runs, each being horizontal or vertical. A total is associated with each of these runs, and the puzzle is solved by entering digits into the cells so that each run sums to the specified total, and no digit is repeated in any run. Published puzzles have unique solutions that may be determined through the use of game constraints and the exercising of reasoning and strategy. However, more generalised Kakuro and associated cross-sum puzzles are not well-formed and possess multiple solutions, requiring other methods such as search techniques for their solution; further, combinatorial methods are required for an analysis of the number of solutions possible. In this paper, we examine problem size and complexity by investigating the numbers of ways in which the cells of runs might be filled with the available digits. This examination reveals important problem features. We then present three different approaches for the automatic solution of Kakuro
puzzles that exploit these problem features. Finally, an analysis of the effectiveness and efficiency of each approach is presented, and suggestions for the future direction of work are
offered.