A Knowledge-Rich Approach to the Rapid Enumeration of Quasi-Magic Sudoku Search Spaces

Sian-Kathryn Jones, Paul Roach, Stephanie Perkins, Ian J. Grimstead

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

58 Wedi eu Llwytho i Lawr (Pure)

Crynodeb

The popular logic puzzle, Sudoku, consists of placing the digits 1,...,9 into a 9×9 grid, such that each digit appears only once in each row, column, and subdivided ‘mini-grid’ of size 3×3. Uniqueness of solution of a puzzle is ensured by the positioning of a number of given values. Quasi-Magic Sudoku adds the further constraint that within each mini-grid, every row, column and diagonal must sum to 15±?, where ? is chosen to take a value between 2 and 8. Recently Sudoku has been shown to have potential for the generation of erasure correction codes. The additional quasi-magic constraint results in far fewer given values being required to ensure uniqueness of solution, raising the prospect of improved usefulness in code generation. Recent work has highlighted useful domain knowledge concerning cell interrelationships in Quasi-Magic Sudoku for the case ? = 2, providing pruning conditions to reduce the size of search space that need be examined to ensure uniqueness of solution. This paper examines the usefulness of the identified rich knowledge in restricting search space size. The knowledge is implemented as pruning conditions in a backtracking implementation of a Quasi-Magic Sudoku solver, with a further cell ordering heuristic. Analysis of the improvement in processing time, and thereby of the potential usefulness of Quasi-Magic Sudoku for code generation, is provided.
Iaith wreiddiolSaesneg
TeitlICAART 2009 - Proceedings of the International Conference on Agents and Artificial Intelligence, Porto, Portugal, January 19 - 21, 2009
CyhoeddwrSpringer
ISBN (Argraffiad)978-3-642-11818-0
StatwsCyhoeddwyd - 19 Ion 2009
Digwyddiad Proceedings of ICAART 2009, the 1st International Conference on Agents and Artificial Intelligence - Porto, Portugal, INSTICC Press (Filipe, J., Fred, A. and Sharp, B. Eds.)
Hyd: 19 Jan 200919 Jan 2009

Cyfres gyhoeddiadau

EnwCommunications in Computer and Information Science
CyhoeddwrSpringer
Rhif296
Cyfrol67
ISSN (Argraffiad)1865-0929

Cynhadledd

Cynhadledd Proceedings of ICAART 2009, the 1st International Conference on Agents and Artificial Intelligence
Cyfnod19/01/0919/01/09

Ôl bys

Gweld gwybodaeth am bynciau ymchwil 'A Knowledge-Rich Approach to the Rapid Enumeration of Quasi-Magic Sudoku Search Spaces'. Gyda’i gilydd, maen nhw’n ffurfio ôl bys unigryw.

Dyfynnu hyn