Difficulty Rating of Sudoku Puzzles by a Computational Model
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F11%3A00049812" target="_blank" >RIV/00216224:14330/11:00049812 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
Difficulty Rating of Sudoku Puzzles by a Computational Model
Original language description
We discuss and evaluate metrics for difficulty rating of Sudoku puzzles. The correlation coefficient with human performance for our best metric is 0.95. The data on human performance were obtained from three web portals and they comprise thousands of hours of human solving over 2000 problems. We provide a simple computational model of human solving activity and evaluate it over collected data. Using the model we show that there are two sources of problem difficulty: complexity of individual steps (logicoperations) and structure of dependency among steps. Beside providing a very good Sudoku-tuned metric, we also discuss a metric with few Sudoku-specific details, which still provides good results (correlation coefficient is 0.88). Hence we believe thatthe approach should be applicable to difficulty rating of other constraint satisfaction problems.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2011
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Twenty-Fourth International Florida Artificial Intelligence Research Society Conference
ISBN
978-1-57735-501-4
ISSN
—
e-ISSN
—
Number of pages
6
Pages from-to
434-439
Publisher name
Association for the Advancement of Artificial Intelligence (AAAI)
Place of publication
USA
Event location
Palm Beach, Florida, USA
Event date
Jan 1, 2011
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—