Automation of the Solution of Kakuro Puzzles

Kakuro puzzles, also called cross sum puzzles, are grids containing clues to the completion of numerical ‘words’. Being structured in a similar way to crossword puzzles, Kakuro grids contain overlapping continuous runs that are exclusively ei-ther horizontal or vertical. The ‘clues’ take the form of specified run totals, and a puzzle is solved by placing a value in each cell such that every run sums to its specified total, and no run contains duplicate values. While most puzzles have only a single solution, longer runs may be satisfied using many arrangements of values, leading to the puzzle having a deceptively large search space. The associ-ated, popular Sudoku puzzle has been linked with important real-world applica-tions including timetabling and conflict free wavelength routing, and more re-cently, coding theory due to its potential usefulness in the construction of erasure correction codes. It is possible that Kakuro puzzles will have similar applications, particularly in the construction of codes, where run totals may form a generalised type of parity check. A project has begun to investigate the properties of the Ka-kuro puzzles, and thereby establish its potential usefulness to real-world applica-tions including coding theory. This paper reports some early findings from that project, specifically concerning puzzle complexity and the appropriateness of heu-ristic approaches for its automated solution. It highlights the use of heuristics to guide search by a backtracking solver, in preference to local search optimisation, and reports on the effectiveness of two heuristics and a pruning technique for re-ducing solution time. The authors believe this to be the first published work in the use of heuristics, in combination with pruning, for the automated solution of Ka-kuro puzzles.