Automation of the Solution of Kakuro Puzzles

Paul Roach, Stephanie Perkins, Ryan P. Davies

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

1140 Downloads (Pure)

Abstract

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.
Original languageEnglish
Title of host publicationResearch and Development in Intelligent Systems XXV
Subtitle of host publicationProceedings of AI-2008, the Twenty-eighth SGAI International Conference on Innovative Techniques and Applications of Artificial Intelligence
EditorsMax Bramer, Miltos Petridis, Francis Coenen
Place of PublicationLondon
PublisherSpringer
Pages219-234
ISBN (Electronic)978-1-84882-171-2
ISBN (Print)978-1-84882-170-5
DOIs
Publication statusPublished - 11 Dec 2008
Event Research and Development in Intelligent Systems XXV: Proceedings of AI-2008, the Twenty-eighth SGAI International Conference on Artificial Intelligence - Cambridge
Duration: 9 Dec 20089 Dec 2008

Conference

Conference Research and Development in Intelligent Systems XXV: Proceedings of AI-2008, the Twenty-eighth SGAI International Conference on Artificial Intelligence
Period9/12/089/12/08

Keywords

  • intelligent systems engineering and design methodologies
  • industrial applications of artificial intelligence
  • evaluation of ai systems

Fingerprint

Dive into the research topics of 'Automation of the Solution of Kakuro Puzzles'. Together they form a unique fingerprint.

Cite this