Please use this identifier to cite or link to this item:
|Title:||SudokuSat - A tool for analyzing difficult sudoku puzzles|
|Authors:||Henz, M. |
|Source:||Henz, M.,Truong, H.-M. (2009). SudokuSat - A tool for analyzing difficult sudoku puzzles. Studies in Computational Intelligence 166 : 25-35. ScholarBank@NUS Repository. https://doi.org/10.1007/978-3-540-88069-1_3|
|Abstract:||Sudoku puzzles enjoy world-wide popularity, and a large community of puzzlers is hoping for ever more difficult puzzles. A crucial step for generating difficult Sudoku puzzles is the fast assessment of the difficulty of a puzzle. In a study in 2006, it has been shown that SAT solving provides a way to efficiently differentiate between Sudoku puzzles according to their difficulty, by analyzing which resolution technique solves a given puzzle. This paper shows that one of these techniques - unit resolution with failed literal propagation - does not solve a recently published Sudoku puzzle called AI Escargot, claimed to be the world's most difficult. The technique is also unable to solve any of a list of difficult puzzles published after AI Escargot, whereas it solves all previously studied Sudoku puzzles. We show that the technique can serve as an efficient and reliable computational method for distinguishing the most difficult Sudoku puzzles. As a proof-of-concept for an efficient difficulty checker, we present the tool SudokuSat that categorizes Sudoku puzzles with respect to the resolution technique required for solving them. © 2009 Springer-Verlag Berlin Heidelberg.|
|Source Title:||Studies in Computational Intelligence|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Dec 13, 2017
checked on Dec 15, 2017
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.