2008 B A Difficulty Metric and Puzzle Generator for Sudoku

杨利霞

2008 B  A Difficulty Metric and Puzzle Generator for Sudoku

学中国
www.
madio.net
本内容由645617861l同学与工作人员共同整理，恭喜同学成功完成数学中国第一期威客项目
数学中国：www.madio.net，最专业的数学建模平台
备战美赛，美赛资料下载：http://www.madio.net/forum-108-1.html

Abstract
Creating and rating the diffiffifficulty of Sudoku puzzles is currently a hard computational prob
lem. In particular, most current approaches require the use of somewhat arbitrary choices for
the relative diffiffifficulties of Sudoku strategies. We present here a novel solver-based solution
to this problem by framing Sudoku as a search problem and using the expected search time
to determine the diffiffifficulty of difffferent strategies. Our method was chosen for its relative
independence from external views on the relative diffiffifficulties of strategies.
Upon validation of our metric with a sample of 800 externally rated puzzles with 8 gra
dations of diffiffifficulty, we found a Goodman-Kruskal γ coeffiffifficient of 0.82, indicating signifificant
correlation. An independent evaluation of 1000 typical puzzles produced a diffiffifficulty distri
bution similar to the distribution of solve times empirically created by millions of users at
www.websudoku.com.
Based upon this diffiffifficulty metric, we created two separate puzzle generators. One gen
erates mostly easy to medium puzzles; when run with 4 diffiffifficulty levels, it creates boards
of levels 1, 2, 3, and 4 in 0.25, 3.1, 4.7, and 30 minutes, respectively. The other modififies
diffiffifficult boards to create boards of similar diffiffifficulty; when tested on a board of diffiffifficulty
8122, it was able to create 20 boards with average diffiffifficulty 7111 in 3 minutes.数学中国
www.
madio.net
本内容由645617861l同学与工作人员共同整理，恭喜同学成功完成数学中国第一期威客项目
数学中国：www.madio.net，最专业的数学建模平台
备战美赛，美赛资料下载：http://www.madio.net/forum-108-1.html

Page 1 of 24 Control #2858
Contents
1 Introduction 2
1.1 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Problem Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2 Problem Setup 4
2.1 Diffiffifficulty Metric . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2 Puzzle Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
3 A Diffiffifficulty Metric 5
3.1 Assumptions and Metric Development . . . . . . . . . . . . . . . . . . . . . 5
3.2 hsolve and Metric Calculation . . . . . . . . . . . . . . . . . . . . . . . . . 6
3.3 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.3.1 Validation Against Existing Diffiffifficulty Ratings . . . . . . . . . . . . . 8
3.3.2 Validation of Diffiffifficulty Distribution . . . . . . . . . . . . . . . . . . . 8
3.3.3 Runtime . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
4 Generator 10
4.1 Standard Generator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
4.1.1 Guaranteeing a Unique Solution with Standard Generator . . . . . . 11
4.2 Pseudo-Generator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
4.2.1 Difffferences From Standard Generator . . . . . . . . . . . . . . . . . . 12
4.2.2 Pseudo-Generator Puzzle Variability . . . . . . . . . . . . . . . . . . 12
4.3 Results and Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
4.3.1 Diffiffifficulty Concerns . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
4.3.2 Generating Puzzles with a Specifific Diffiffifficulty . . . . . . . . . . . . . . 13
4.3.3 Standard Generator Runtime . . . . . . . . . . . . . . . . . . . . . . 14
4.3.4 Using Pseudo-Generator to Generate Diffiffifficult Puzzles . . . . . . . . . 14
5 Conclusion 15
5.1 Strengths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
5.2 Weaknesses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
5.3 Alternative Approaches and Future Work . . . . . . . . . . . . . . . . . . . . 16
A Sudoku Strategies 17
B Source Code for hsolve 22
1数学中国
www.
madio.net
本内容由645617861l同学与工作人员共同整理，恭喜同学成功完成数学中国第一期威客项目
数学中国：www.madio.net，最专业的数学建模平台
备战美赛，美赛资料下载：http://www.madio.net/forum-108-1.html
美赛讨论加入群：2017美赛官方群287336869
Page 2 of 24 Control #2858
1 Introduction
Sudoku is a logic puzzle that has recently become extremely popular. In Sudoku, a player is
presented with a 9 × 9 grid divided into nine 3 × 3 regions. Some of the 81 cells of the grid
are initially fifilled with digits between 1 and 9 such that there is a unique way to complete
the rest of the grid while satisfying the following rules:
1. Each cell contains a digit between 1 and 9
2. Each row, column, and 3×3 region contains exactly one copy of the digits {1, 2, . . . , 9}.
A Sudoku puzzle consists of such a grid together with an initial collection of digits that
guarantees a unique fifinal confifiguration. Call this fifinal confifiguration a solution to the puzzle.
The goal of Sudoku is to fifind this unique solution from the initial board.
Below is an example of a Sudoku puzzle and solution from the February 16th, 2008 edition
of the London Times [18]:
7 9 5
3 5 2 8 4
8
1 7 4
6 3 1 8
9 8 1
2
4 5 8 9 1
8 3 7
8 6 1 7 9 4 3 5 2
3 5 2 1 6 8 7 4 9
4 9 7 2 5 3 1 8 6
2 1 8 9 7 5 6 3 4
6 7 5 3 4 1 9 2 8
9 3 4 6 8 2 5 1 7
5 2 6 8 1 9 4 7 3
7 4 3 5 2 6 8 9 1
1 8 9 4 3 7 2 6 5
In this particular example, we cannot have the numbers 8, 3, or 7 appear anywhere else on
the bottom row, since each number can only show up in the bottommost row once. Similarly,
the number 8 cannot appear in any of the empty squares in the lower-left-hand region.