Page 2 of 62 MCM 2008 Team #3780 Contents 5.3.4 Uniqueness Testing 17 5.4 Complexity Analysis 1 Introduction 5.4.1 Parameterization .18 1.1 Statement of problem 3 5.4.2 Complexity of C 1.2 Relevance of sudoku 3 Puzzle generation 3 1.4 Rules of sudoku 5.4.3 Complexity of Uniqueness 3 Testing and Random Filling. 18 1.5 Terminology and Notation 3 5.4.4 Profiling Method 1.6 Indexing 5.4.5 WNEF vs Running Time 1.7 Formal Rules of sudoku 5 5.5 Testing 1.8 Example Puzzles 5 5.5.1 WNEF as a function of de- 2 Background 5 2.1 Common Solving Techniqu 5.5.2 Hypothesis Testing 2.1.1 Naked Pair 6 Strengths and Weaknesses 2.1.2 Naked Triplet 5 2.1.3 Hidden pair 67 Conclusions 21 2.1.4 Hidden Triplet 2.1.5 Multi-Line 6 References 21 2.2 Previous Works 7 2.2.1 Sudokuexplainer 7 1 Source Code 2.2.2 QQWing 2.2.3 GNOME Sudoku 7 2 Screenshots of Puzzle Generator 3 Metric Design 10 3.1 Overview 3.2 Assumptions 10 List of Figures 3.3 Mathematical basis for WneF 10 3.3.1 Complexit 10 1 Demonstration of indexing schemes. 6 2 Puzzle generated by WebSudoku 4 Metric Calibration and Testing ( ranked as“Easy”) 6 4.1 Control Puzzle sources 118 Top 1465 Number 77 4.2 Testing Method 4 An example of a hand-made Nikoli 4.2.1 Defining Difficulty Ranges.. 12 puzzle. 4.2.2 Information collection 12 5 Example of the Naked Pair rule 4.2.3 Statistical Analysis of Con- 6 Example of the Naked Triplet rule. 8 trol puzzles 7 Example of the Hidden Pair rule 8 4.3 Choice of Weight Function. 12 8 Example of the Hidden Triplet rule. 9 9 Example of the Multi-Line rul 5 Generator Algorithm 12 10 Examples of choice histograms 11 5.1 Overview 1 WNEF for control puzzles by diffi- 5.2 Detailed Description cul 5.2.1 Completed Puzzle Generation 14 12 WNEF correlations for various 5.2.2 Cell removal 14 weighting functions 5.2.3 Uniqueness 15 13 Running time as a function of the 5.3 Pseudocode 15 obtained wef 5.3.1 Completed Board Generation 15 14 WNEF as a function of allowed fail- 5.3.2 Random Masking ures 5.3.3 Tuned Masking 17 15 Screenshots of puzzle generator.Page 2 of 62 MCM 2008 Team #3780 Contents 1 Introduction 3 1.1 Statement of Problem . . . . . . . . . 3 1.2 Relevance of Sudoku . . . . . . . . . 3 1.3 Goals . . . . . . . . . . . . . . . . . . 3 1.4 Rules of Sudoku . . . . . . . . . . . . 3 1.5 Terminology and Notation . . . . . . 3 1.6 Indexing . . . . . . . . . . . . . . . . 4 1.7 Formal Rules of Sudoku . . . . . . . 5 1.8 Example Puzzles . . . . . . . . . . . 5 2 Background 5 2.1 Common Solving Techniques . . . . 5 2.1.1 Naked Pair . . . . . . . . . . 5 2.1.2 Naked Triplet . . . . . . . . . 5 2.1.3 Hidden Pair . . . . . . . . . . 6 2.1.4 Hidden Triplet . . . . . . . . . 6 2.1.5 Multi-Line . . . . . . . . . . . 6 2.2 Previous Works . . . . . . . . . . . . 7 2.2.1 SudokuExplainer . . . . . . . 7 2.2.2 QQWing . . . . . . . . . . . . 7 2.2.3 GNOME Sudoku . . . . . . . 7 3 Metric Design 10 3.1 Overview . . . . . . . . . . . . . . . . 10 3.2 Assumptions . . . . . . . . . . . . . . 10 3.3 Mathematical Basis for WNEF . . . 10 3.3.1 Complexity . . . . . . . . . . . 10 4 Metric Calibration and Testing 11 4.1 Control Puzzle Sources . . . . . . . . 11 4.2 Testing Method . . . . . . . . . . . . 12 4.2.1 Defining Difficulty Ranges . . 12 4.2.2 Information Collection . . . . 12 4.2.3 Statistical Analysis of Con￾trol Puzzles . . . . . . . . . . . 12 4.3 Choice of Weight Function. . . . . . . 12 5 Generator Algorithm 12 5.1 Overview . . . . . . . . . . . . . . . . 12 5.2 Detailed Description . . . . . . . . . 14 5.2.1 Completed Puzzle Generation 14 5.2.2 Cell Removal . . . . . . . . . . 14 5.2.3 Uniqueness Testing . . . . . . 15 5.3 Pseudocode . . . . . . . . . . . . . . . 15 5.3.1 Completed Board Generation 15 5.3.2 Random Masking . . . . . . . 16 5.3.3 Tuned Masking . . . . . . . . 17 5.3.4 Uniqueness Testing . . . . . . 17 5.4 Complexity Analysis . . . . . . . . . 18 5.4.1 Parameterization . . . . . . . 18 5.4.2 Complexity of Completed Puzzle Generation . . . . . . . 18 5.4.3 Complexity of Uniqueness Testing and Random Filling . 18 5.4.4 Profiling Method . . . . . . . 18 5.4.5 WNEF vs Running Time . . . 19 5.5 Testing . . . . . . . . . . . . . . . . . 19 5.5.1 WNEF as a Function of De￾sign Choices . . . . . . . . . . 19 5.5.2 Hypothesis Testing . . . . . . 19 6 Strengths and Weaknesses 19 7 Conclusions 21 References 21 1 Source Code 23 2 Screenshots of Puzzle Generator 62 List of Figures 1 Demonstration of indexing schemes. 6 2 Puzzle generated by WebSudoku (ranked as “Easy”). . . . . . . . . . . 6 3 Top 1465 Number 77. . . . . . . . . . 7 4 An example of a hand-made Nikoli puzzle. . . . . . . . . . . . . . . . . . 7 5 Example of the Naked Pair rule. . . 8 6 Example of the Naked Triplet rule. . 8 7 Example of the Hidden Pair rule. . . 8 8 Example of the Hidden Triplet rule. 9 9 Example of the Multi-Line rule. . . . 9 10 Examples of choice histograms. . . . 11 11 WNEF for control puzzles by diffi- culty. . . . . . . . . . . . . . . . . . . 13 12 WNEF correlations for various weighting functions. . . . . . . . . . . 13 13 Running time as a function of the obtained WNEF. . . . . . . . . . . . . 20 14 WNEF as a function of allowed fail￾ures. . . . . . . . . . . . . . . . . . . . 20 15 Screenshots of puzzle generator. . . . 62