An investigation into the solution to, and evaluation of, Kakuro puzzles

Abstract

Kakuro puzzles, also known as Cross-Sum puzzles, are similar in structure to standard Crossword puzzles. They consist of grids, containing overlapping continuous runs that are exclusively
either horizontal or vertical, with “clues” to the completion of numerical “words”. The numerical clues take the form of specified run-totals, and a puzzle is solved by placing a value from a given valid range (usually 1, . . . , 9) into each cell. A valid solution is reached when 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 different
arrangements of values, leading to the puzzle having a deceptively large search space. The associated, popular Sudoku puzzle has been linked with important real-world applications
including conflict free wavelength routing and timetabling, and more recently, 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 error check. This thesis presents an investigation into the properties of Kakuro puzzles, and considers the potential usefulness of Kakuro to real-world applications. Specifically, this thesis determines bounds on the number of valid grid arrangements, a partial enumeration of Kakuro puzzles and compares methods of automating the solution of Kakuro puzzles that incorporate, where possible, puzzle domain information.

Date of Award	2009
Original language	English