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 solvePage 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