Difficulty Rating of Sudoku Puzzles by a Computational Model

D 2011

Difficulty Rating of Sudoku Puzzles by a Computational Model

PELÁNEK, Radek

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

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

Změněno: 8. 6. 2012 10:31, doc. Mgr. Radek Pelánek, Ph.D.

Anotace

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.

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

Citovat

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.

@inproceedings{941345,
   author = {Pelánek, Radek},
   address = {USA},
   booktitle = {Twenty-Fourth International Florida Artificial Intelligence Research Society Conference},
   editor = {Philip M. McCarthy, R. Charles Murray},
   keywords = {computational model; human problem solving; Sudoku; difficulty; evaluation},
   language = {eng},
   location = {USA},
   isbn = {978-1-57735-501-4},
   pages = {434-439},
   publisher = {Association for the Advancement of Artificial Intelligence (AAAI)},
   title = {Difficulty Rating of Sudoku Puzzles by a Computational Model},
   year = {2011}
}

TY  - JOUR
ID  - 941345
AU  - Pelánek, Radek
PY  - 2011
TI  - Difficulty Rating of Sudoku Puzzles by a Computational Model
PB  - Association for the Advancement of Artificial Intelligence (AAAI)
CY  - USA
SN  - 9781577355014
KW  - computational model
KW  - human problem solving
KW  - Sudoku
KW  - difficulty
KW  - evaluation
N2  - 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.
ER  -

PELÁNEK, Radek. Difficulty Rating of Sudoku Puzzles by a Computational Model. In Philip M. McCarthy, R. Charles Murray. \textit{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.

Podrobný výpis o publikaci