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, s. 434-439. ISBN 978-1-57735-501-4.

Základní údaje

• Originální název: Difficulty Rating of Sudoku Puzzles by a Computational Model
• Název česky: Hodnocení obtížnosti Sudoku pomocí výpočetního modelu
• Autoři: PELÁNEK, Radek (203 Česká republika, garant, domácí).
• Vydání: USA, Twenty-Fourth International Florida Artificial Intelligence Research Society Conference, od s. 434-439, 6 s. 2011.
• Nakladatel: Association for the Advancement of Artificial Intelligence (AAAI)

Další údaje

• Originální jazyk: angličtina
• Typ výsledku: Stať ve sborníku
• Obor: 10201 Computer sciences, information science, bioinformatics
• Stát vydavatele: Spojené státy
• Utajení: není předmětem státního či obchodního tajemství
• Kód RIV: RIV/00216224:14330/11:00049812
• Organizační jednotka: Fakulta informatiky
• ISBN: 978-1-57735-501-4
• Klíčová slova česky: výpočetní model; řešení problémů; Sudoku; obtížnost; experimentální vyhodnocení
• Klíčová slova anglicky: computational model; human problem solving; Sudoku; difficulty; evaluation
• Příznaky: Mezinárodní význam, Recenzováno

Anotace

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.

Návaznosti

• GAP202/10/0334, projekt VaV: Název: Řešení obtížných dobře strukturovaných problémů: spolupráce člověka a počítače

Investor: Grantová agentura ČR, Řešení obtížných dobře strukturovaných problémů: spolupráce člověka a počítače

• 1M0545, projekt VaV: Název: Institut Teoretické Informatiky

Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Institut Teoretické Informatiky