hsolve: A Difficulty Metric and Puzzle generator for Sudoku MCM Team #2858: Christopher Chang, Zhou Fan, and Yi Sun February 19, 2008
hsolve: A Difficulty Metric and Puzzle Generator for Sudoku MCM Team #2858: Christopher Chang, Zhou Fan, and Yi Sun February 19, 2008
abstract Creating and rating the difficulty 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 difficulties 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 difficulty of different strategies. Our method was chosen for its relative independence from external views on the relative difficulties of strategies Upon validation of our metric with a sample of 800 externally rated puzzles with 8 gra dations of difficulty, we found a Goodman-Kruskal y coefficient of 0.82, indicating significant correlation. An independent evaluation of 1000 typical puzzles produced a difficulty distri- bution similar to the distribution of solve times empirically created by millions of users at www.websudoku.com Based upon this difficulty metric, we created two separate puzzle generators. One gen- erates mostly easy to medium puzzles; when run with 4 difficulty levels, it creates boards of levels 1, 2, 3, and 4 in 0.25, 3.1, 4.7, and 30 minutes, respectively. The other modifies difficult boards to create boards of similar difficulty; when tested on a board of difficulty 8122, it was able to create 20 boards with average difficulty 711l in 3 minutes
Abstract Creating and rating the difficulty of Sudoku puzzles is currently a hard computational problem. In particular, most current approaches require the use of somewhat arbitrary choices for the relative difficulties 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 difficulty of different strategies. Our method was chosen for its relative independence from external views on the relative difficulties of strategies. Upon validation of our metric with a sample of 800 externally rated puzzles with 8 gradations of difficulty, we found a Goodman-Kruskal γ coefficient of 0.82, indicating significant correlation. An independent evaluation of 1000 typical puzzles produced a difficulty distribution similar to the distribution of solve times empirically created by millions of users at www.websudoku.com. Based upon this difficulty metric, we created two separate puzzle generators. One generates mostly easy to medium puzzles; when run with 4 difficulty levels, it creates boards of levels 1, 2, 3, and 4 in 0.25, 3.1, 4.7, and 30 minutes, respectively. The other modifies difficult boards to create boards of similar difficulty; when tested on a board of difficulty 8122, it was able to create 20 boards with average difficulty 7111 in 3 minutes
Page 1 of 24 Control #2858 Contents 1 Introduction 1.1 Notatio 1.2 Problem background 2 Problem Setup 2.1 Difficulty Metric 2.2 Puzzle generation 3 A Difficulty Metric 3. 1 Assumptions and Metric Development 3.2 solve and Metric Calculation 223444556788 3.3 Analysis 3.3.1 Validation Against Existing Difficulty Ratings 3.3.2 Validation of Difficulty Distribution 3.3.3 Runtime 4 Generator 10 4.1 Standard Generator 10 4.1.1 Guaranteeing a Unique Solution with Standard Generator 4.2 Pseudo-Generator 4.2.1 Differences From Standard Generator 4.2.2 Pseudo-Generator Puzzle variability 4.3 Results and Analysis 4.3.1 Difficulty Concerns 4.3.2 Generating Puzzles with a Specific Difficulty 4.3.3 Standard Generator Runtime BB44 4.3.4 Using Pseudo-Generator to Generate Difficult Puzzles 5 Conclusion 5.1 Strengths 15 5.2 Weaknesses 5.3 Alternative Approaches and Future Work 16 a Sudoku strategies B Source code for solve
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 Difficulty Metric . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.2 Puzzle Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 3 A Difficulty 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 Difficulty Ratings . . . . . . . . . . . . . 8 3.3.2 Validation of Difficulty 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 Differences From Standard Generator . . . . . . . . . . . . . . . . . . 12 4.2.2 Pseudo-Generator Puzzle Variability . . . . . . . . . . . . . . . . . . 12 4.3 Results and Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 4.3.1 Difficulty Concerns . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 4.3.2 Generating Puzzles with a Specific Difficulty . . . . . . . . . . . . . . 13 4.3.3 Standard Generator Runtime . . . . . . . . . . . . . . . . . . . . . . 14 4.3.4 Using Pseudo-Generator to Generate Difficult 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
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 x9 grid divided into nine 3 x 3 regions. Some of the 81 cells of the grid are initially filled 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 Each cell contains a digit between 1 and 9 2. Each row, column, and 3 x3 region contains exactly one copy of the digits (1, 2,..., 91 A Sudoku puzzle consists of such a grid together with an initial collection of digits that guarantees a unique final configuration. Call this final configuration a solution to the puzzle The goal of Sudoku is to find this unique solution from the initial board Below is an example of a Sudoku puzzle and solution from the February 16th, 2008 editio of the London Times [18 218971563|4 山8[67534192 9|34682517 526819473 8|9山|43|5268|9 s|9437265 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 1. 1 Notation We first introduce some notation. Number the rows and columns from 1 to 9. beginning at the top and left, respectively, and number each 3 x 3 region of the board as follows:
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 filled 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 final configuration. Call this final configuration a solution to the puzzle. The goal of Sudoku is to find 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. 1.1 Notation We first introduce some notation. Number the rows and columns from 1 to 9, beginning at the top and left, respectively, and number each 3 × 3 region of the board as follows: 1 2 3 4 5 6 7 8 9 2
Page 3 of 24 Control #2858 We will refer to a cell by an ordered pair(i,j), where i is its row and j its column, and the term group will collectively denote a row, column, or region. Given a Sudoku board B, define the Sudoku Solution Graph(SSG)s(B) of b to be th structure that associates to each cell in b the set of the digits that are currently thought to be possible candidates for the cell. For example, in the first Sudoku puzzle presented, cell 9, 9)cannot take the values 1, 3, 4, 7, 8, 9 because it shares a group with cells with these values. Therefore, this cell has values ( 2, 5, 6) in the corresponding SSG To solve a Sudoku board, a player generally applies a number of different strategies, or patterns of logical deduction. These range from fairly obvious to extremely complicated, and a list of Sudoku strategies used in this paper is provided in Appendix A. In this paper, we assume the SSg has been evaluated for every cell on the Sudoku board before applying any strategies 1.2 Problem Background Since its recent rise in popularity, Sudoku has been the focus of increased academic and recreational study. Most of the efforts directed at Sudoku have been directed at solving Sudoku puzzles or analyzing the computational complexity of resolving Sudoku as done 13],4],and[14] via a reduction to an exact cover problem and an application of Knuth's Algorithm X given in [11], and solving the n2 x n2 generalization of Sudoku is known to be NP-complete as a consequence of results given by Yato in 22 o. However, a perhaps deeper and more difficult issue involves rating the difficulty of and nerating Sudoku puzzles. This problem encompasses the following two questi 1. Given a specific Sudoku puzzle, how does one define and determine its difficulty 2. Given a specified difficulty, how does one generate a Sudoku puzzle of this difficulty? While generating a valid Sudoku puzzle is not too complex, the non-local and unclear rocess of deduction makes determining or specifying a difficulty much more complicated Traditional approaches to difficulty rating involve rating a puzzle by the strategies neces- sary to find the solution, while some other approaches have been proposed in 1] and 3. In particular, a genetic algorithms approach taken by Mantere et. al. in [15] found some corre- lation with human-rated difficulties, and Simonis presents some interesting similar findings with a constraint-based rating 17. However, in both cases, the correlation is not completely clear Puzzle generation seems to be an even more difficult issue. Most existing generators use complete search algorithms to systematically add numbers to cells in a grid until a unique solution is found. To generate a puzzle of a given difficulty, this process is repeated until the desired difficulty is achieved. This is the approach found in [15], while [17 posits both this and a similar method based upon removal of cells from a completed board. In 5 Felgenhauer et. al. has enumerated the total possible number of valid Sudoku puzzles In this paper, we present a new approach to rating and generating puzzle create hsolve, a program to simulate the way a human solver approaches a sudoku puzzle in order to present a new solver-based difficulty metric based upon hsolve's simulation of human
Page 3 of 24 Control #2858 We will refer to a cell by an ordered pair (i, j), where i is its row and j its column, and the term group will collectively denote a row, column, or region. Given a Sudoku board B, define the Sudoku Solution Graph (SSG) S(B) of B to be the structure that associates to each cell in B the set of the digits that are currently thought to be possible candidates for the cell. For example, in the first Sudoku puzzle presented, cell (9, 9) cannot take the values {1, 3, 4, 7, 8, 9} because it shares a group with cells with these values. Therefore, this cell has values {2, 5, 6} in the corresponding SSG. To solve a Sudoku board, a player generally applies a number of different strategies, or patterns of logical deduction. These range from fairly obvious to extremely complicated, and a list of Sudoku strategies used in this paper is provided in Appendix A. In this paper, we assume the SSG has been evaluated for every cell on the Sudoku board before applying any strategies. 1.2 Problem Background Since its recent rise in popularity, Sudoku has been the focus of increased academic and recreational study. Most of the efforts directed at Sudoku have been directed at solving Sudoku puzzles or analyzing the computational complexity of resolving Sudoku as done in [13], [4], and [14]. Most notably, Sudoku can now be solved extremely quickly via a reduction to an exact cover problem and an application of Knuth’s Algorithm X given in [11], and solving the n 2 × n 2 generalization of Sudoku is known to be NP-complete as a consequence of results given by Yato in [22]. However, a perhaps deeper and more difficult issue involves rating the difficulty of and generating Sudoku puzzles. This problem encompasses the following two questions: 1. Given a specific Sudoku puzzle, how does one define and determine its difficulty? 2. Given a specified difficulty, how does one generate a Sudoku puzzle of this difficulty? While generating a valid Sudoku puzzle is not too complex, the non-local and unclear process of deduction makes determining or specifying a difficulty much more complicated. Traditional approaches to difficulty rating involve rating a puzzle by the strategies necessary to find the solution, while some other approaches have been proposed in [1] and [3]. In particular, a genetic algorithms approach taken by Mantere et. al. in [15] found some correlation with human-rated difficulties, and Simonis presents some interesting similar findings with a constraint-based rating [17]. However, in both cases, the correlation is not completely clear. Puzzle generation seems to be an even more difficult issue. Most existing generators use complete search algorithms to systematically add numbers to cells in a grid until a unique solution is found. To generate a puzzle of a given difficulty, this process is repeated until the desired difficulty is achieved. This is the approach found in [15], while [17] posits both this and a similar method based upon removal of cells from a completed board. In [5], Felgenhauer et. al. has enumerated the total possible number of valid Sudoku puzzles. In this paper, we present a new approach to rating and generating puzzles. We create hsolve, a program to simulate the way a human solver approaches a Sudoku puzzle in order to present a new solver-based difficulty metric based upon hsolve’s simulation of human 3