Automation of the Solution of Kakuro Puzzles

Paul Roach, Stephanie Perkins, Ryan P. Davies

Allbwn ymchwil: Pennod mewn Llyfr/Adroddiad/Trafodion CynhadleddCyfraniad i gynhadleddadolygiad gan gymheiriaid

1556 Wedi eu Llwytho i Lawr (Pure)

Crynodeb

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.
Iaith wreiddiolSaesneg
TeitlResearch and Development in Intelligent Systems XXV
Is-deitlProceedings of AI-2008, the Twenty-eighth SGAI International Conference on Innovative Techniques and Applications of Artificial Intelligence
GolygyddionMax Bramer, Miltos Petridis, Francis Coenen
Man cyhoeddiLondon
CyhoeddwrSpringer
Tudalennau219-234
ISBN (Electronig)978-1-84882-171-2
ISBN (Argraffiad)978-1-84882-170-5
Dynodwyr Gwrthrych Digidol (DOIs)
StatwsCyhoeddwyd - 11 Rhag 2008
Digwyddiad Research and Development in Intelligent Systems XXV: Proceedings of AI-2008, the Twenty-eighth SGAI International Conference on Artificial Intelligence - Cambridge
Hyd: 9 Rhag 20089 Rhag 2008

Cynhadledd

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

Ôl bys

Gweld gwybodaeth am bynciau ymchwil 'Automation of the Solution of Kakuro Puzzles'. Gyda’i gilydd, maen nhw’n ffurfio ôl bys unigryw.

Dyfynnu hyn