Transcript GPW 2004 Presentation

Analysis of the Behavior of People
Solving Sudoku Puzzles
Reijer Grimbergen
School of Computer Science, Tokyo University of Technology
Akihiro Nakamura
Department of Informatics, Yamagata University
2009/11/14
GPW2009
1
Outline
Why Sudoku?
Sudoku rules
Sudoku solving behavior
Recording human behavior
Rule extraction
Computer simulation
Simulation vs. Human
behavior
Rule set and comparison
Conclusions and future
work
2009/11/14
GPW2009
2
Why Sudoku?
Our goal is to implement
Marvin Minsky’s Society of
Mind theory for two-player
games like shogi
First analyze the behavior of
humans solving puzzles
Advantage: No interaction with
other players
Sudoku is a popular puzzle that
has not been used for cognitive
modeling before
2009/11/14
GPW2009
3
Sudoku rules
99 grid with nine 3 3
subgrids
Fill each row, column
and subgrid with the
numbers from 1 to 9
No row, column or
subgrid should have a
number more than once
2009/11/14
GPW2009
1
5
8
2
4
6
4
9
3
5
3
6
4
8
9
7
7
3
5
4
5
1
4
7
6
6
4
7
4
8
9
3
6
2
6
2
3
1
9
8
9
4
4
2
Sudoku Solving Behavior
Steps in analyzing the behavior
of humans
A number of subjects were asked
to solve a Sudoku puzzle and
explain their decisions
The output of the subjects was
used to extract a number of rules
The rules were implemented in a
computer program
The output of the program was
compared with the original output
of the subjects
2009/11/14
GPW2009
5
Recording human behavior
Five subjects in their early twenties
Two Sudoku puzzles
For each step P in a Sudoku puzzle, a
number NP has to be penciled on square SP
Explain the reason for selecting NP and SP
2009/11/14
GPW2009
6
Rule Extraction
The written protocols were analyzed to find
rules guiding problem solving behavior
Example rule
If there is only one empty square on a row or
column, fill it with the missing number
Too specific, so we used more general rules
2009/11/14
GPW2009
7
Computer Simulation
Input: A Sudoku position P
Output: A set of squares {SP1,…, SPn} that were
selected based on the our rules
Note: No actual numbers were suggested
7
3
6
8
1
1
2
2
4
6
9
3
2
5
3
1
5
8
6
3
8
9
1
1
2
2
4
9
8
7
4
6
8
6
1
3
4
2
7
6
8
2009/11/14
7
8
8
4
6
4
6
5
1
3
9
1
GPW2009
4
9
6
8
8
1
5
4
1
6
8
9
Simulation vs. Human Behavior
Compare the output of the program to the
output of the subjects
Output ratio
A measure of how many unnecessary candidates
are produced by the rules
Should be as small as possible (1 is ideal)
Cover ratio
Number of positions where a square selected by the
human solver was generated by the program
Should be as close to 100% as possible
2009/11/14
GPW2009
9
Simulation vs. Human Behavior
Output ratio
Single position
CP
OP 
100
BP
CP is the total number of candidate squares, BP is the
total number of blank squares
n
Whole puzzle
O
C
P 1
n
B
P 1
2009/11/14
GPW2009
P
100
P
10
Simulation vs. Human Behavior
Cover Ratio
Rc
C  100
S
here Rc is the number of times the square selected
by the human solver was part of the generated
candidates, S is the number of positions in the
Sudoku puzzle
2009/11/14
GPW2009
11
Rule Set and Comparison
Likely strategies of human subjects
Give priority to rows and columns with three
empty squares or less
Try to fill subgrids, rows and columns with few
empty squares
Explore subgrids, rows and columns with only
2 or 3 empty squares
2009/11/14
GPW2009
12
Rule Set and Comparison
Rule 1
Generate all squares with corresponding subgrid,
row or column having less than T1 empty squares
Rule 2
Generate all squares in a subgrid with less than T2
empty squares
Rule 3
Generate all squares in a row or column with less
than T3 empty squares
2009/11/14
GPW2009
13
Results for Sudoku Puzzle 1
Individual rule results
Rule
Threshold Output ratio Cover ratio
1
9
54.6%
96.8%
2
4
54.0%
94.7%
3
3
52.8%
95.8%
1
5
8
2
4
6
4
9
3
5
3
6
4
8
9
7
7
3
5
4
5
Ordered rule results
1. Rule 1 with T1 = 2
2. Rule 2 with T2 = 1
3. Rule 3 with T3 = 3
2009/11/14
GPW2009
1
4
7
6
6
4
7
4
8
9
3
6
2
6
2
3
1
9
8
9
4
2
Output ratio: 40.0%
Cover ratio: 92.1%
14
Results for Sudoku Puzzle 2
Individual rule results
Rule
7
6
8
Threshold Output ratio Cover ratio
1
12
66.8%
97.1%
2
8
46.7%
91.8%
3
5
99.9%
98.0%
3
1. Rule 2 with T2 = 1
2. Rule 1 with T1 = 2
2009/11/14
GPW2009
1
2
2
4
9
8
7
4
6
8
6
9
3
2
5
3
Ordered rule results
1
1
6
8
8
1
5
4
4
1
6
9
Output ratio: 20.8%
Cover ratio: 98.4%
15
Conclusions and Future Work
Conclusions
The rules suggest that human Sudoku solvers
prefer rows and columns over subgrids
General rules that can be applied to all puzzles are
hard to find
Future work
Look at more complex rules
Include search to decide between multiple
candidates
Add suggestions for numbers to pencil in
2009/11/14
GPW2009
16