Detailed Information on Publication Record
2011
Difficulty Rating of Sudoku Puzzles by a Computational Model
PELÁNEK, RadekBasic information
Original name
Difficulty Rating of Sudoku Puzzles by a Computational Model
Name in Czech
Hodnocení obtížnosti Sudoku pomocí výpočetního modelu
Authors
PELÁNEK, Radek (203 Czech Republic, guarantor, belonging to the institution)
Edition
USA, Twenty-Fourth International Florida Artificial Intelligence Research Society Conference, p. 434-439, 6 pp. 2011
Publisher
Association for the Advancement of Artificial Intelligence (AAAI)
Other information
Language
English
Type of outcome
Stať ve sborníku
Field of Study
10201 Computer sciences, information science, bioinformatics
Country of publisher
United States of America
Confidentiality degree
není předmětem státního či obchodního tajemství
RIV identification code
RIV/00216224:14330/11:00049812
Organization unit
Faculty of Informatics
ISBN
978-1-57735-501-4
Keywords (in Czech)
výpočetní model; řešení problémů; Sudoku; obtížnost; experimentální vyhodnocení
Keywords in English
computational model; human problem solving; Sudoku; difficulty; evaluation
Tags
International impact, Reviewed
Změněno: 8/6/2012 10:31, doc. Mgr. Radek Pelánek, Ph.D.
Abstract
V originále
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 (logic operations) 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 that the approach should be applicable to difficulty rating of other constraint satisfaction problems.
Links
GAP202/10/0334, research and development project |
| ||
1M0545, research and development project |
|