Please use this identifier to cite or link to this item: https://doi.org/10.1007/978-3-540-88069-1_3
Title: SudokuSat - A tool for analyzing difficult sudoku puzzles
Authors: Henz, M. 
Truong, H.-M.
Issue Date: 2009
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
URI: http://scholarbank.nus.edu.sg/handle/10635/39299
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.

SCOPUSTM   
Citations

4
checked on Dec 13, 2017

Page view(s)

66
checked on Dec 15, 2017

Google ScholarTM

Check

Altmetric


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