Please use this identifier to cite or link to this item:
Title: SudokuSat - A tool for analyzing difficult sudoku puzzles
Authors: Henz, M. 
Truong, H.-M.
Issue Date: 2009
Citation: Henz, M.,Truong, H.-M. (2009). SudokuSat - A tool for analyzing difficult sudoku puzzles. Studies in Computational Intelligence 166 : 25-35. ScholarBank@NUS Repository.
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
ISBN: 9783540880684
ISSN: 1860949X
DOI: 10.1007/978-3-540-88069-1_3
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.


checked on Apr 2, 2020

Page view(s)

checked on Mar 31, 2020

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.