Difficulty Rating of Sudoku Puzzles by a Computational Model

PELÁNEK, Radek. Difficulty Rating of Sudoku Puzzles by a Computational Model. In Philip M. McCarthy, R. Charles Murray. Twenty-Fourth International Florida Artificial Intelligence Research Society Conference. USA: Association for the Advancement of Artificial Intelligence (AAAI), 2011, p. 434-439. ISBN 978-1-57735-501-4.

Basic 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

• Original language: English
• Type of outcome: Proceedings paper
• Field of Study: 10201 Computer sciences, information science, bioinformatics
• Country of publisher: United States of America
• Confidentiality degree: is not subject to a state or trade secret
• 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

Abstract

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: Name: Řešení obtížných dobře strukturovaných problémů: spolupráce člověka a počítače

Investor: Czech Science Foundation

• 1M0545, research and development project: Name: Institut Teoretické Informatiky

Investor: Ministry of Education, Youth and Sports of the CR, Institute for Theoretical Computer Science