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

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<br/>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<br/>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<br/>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.

Name dc:type.qualificationname

Master's Thesis

Level dc:type.qualificationlevel

Student thesis

Year dc:date.issued

2009

Author dc:creator

• Davies, Ryan P.

Advisors dc:contributor.advisor

• Roach, Paul
• Perkins, Stephanie

• Kakuro
• Mathematical recreations

Language dc:language

eng

Identifier

oai:pure.atira.dk:studenttheses/3dd743bb-271b-49b2-8910-871150e373b4

OAI identifier oai:identifier

oai:pure.atira.dk:studenttheses/3dd743bb-271b-49b2-8910-871150e373b4