数学建模社区-数学中国

标题: 发一本08年B题的参考书 [打印本页]

作者: glenn1986 时间: 2009-1-22 11:19
标题: 发一本08年B题的参考书
培训时做08B题Sudoku 的时候找到的一本参考书。Programming Sudoku

Contents
■CHAPTER 1 What Is Sudoku? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
Rules of Sudoku . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
Sudoku Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
It’s Just Logic! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
Variants of Sudoku . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
Let’s Play Sudoku! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
■CHAPTER 2 Creating the Sudoku Application . . . . . . . . . . . . . . . . . . . . . . . . . 11
Creating the Sudoku Project . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
Creating the User Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
Declaring the Member Variables. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
Representing Values in the Grid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
Generating the Grid Dynamically. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
Starting a New Game . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
Selecting the Numbers to Insert . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
Handling Click Events on the Label Controls . . . . . . . . . . . . . . . . . . . 30
Undoing and Redoing a Move . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
Saving a Game . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
Opening a Saved Game . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
Ending the Game . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
Testing the Application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
■CHAPTER 3 Basic Sudoku Solving Technique . . . . . . . . . . . . . . . . . . . . . . . . . 47
Elimination Technique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
Column, Row, and Minigrid Elimination . . . . . . . . . . . . . . . . . . . . . . . 48
Usefulness of the CRME Technique . . . . . . . . . . . . . . . . . . . . . . . . . . 54
Exception Scenarios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
Implementing the CRME Technique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
Adding Member Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
Modifying the SetCell() Subroutine . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
Adding a ToolTip Control . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
Calculating the Possible Values for a Cell . . . . . . . . . . . . . . . . . . . . . 61
Scanning the Grid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
Wiring the Controls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
Testing It Out . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
■CHAPTER 4 Intermediate Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
Lone Rangers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
Lone Rangers in a Minigrid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
Lone Rangers in a Row . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
Lone Rangers in a Column. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
Implementing the Technique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
Looking for Lone Rangers in Minigrids. . . . . . . . . . . . . . . . . . . . . . . . 77
Looking for Lone Rangers in Rows . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
Looking for Lone Rangers in Columns . . . . . . . . . . . . . . . . . . . . . . . . 81
Modifying the SolvePuzzle() Function. . . . . . . . . . . . . . . . . . . . . . . . . 83
Testing Out the Lone Ranger Technique . . . . . . . . . . . . . . . . . . . . . . . . . . 86
Example 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
Example 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
■CHAPTER 5 Advanced Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
Looking for Twins . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
Looking for Triplets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
Variants of Triplets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
Brute-Force Elimination . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
Implementing the Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
Looking for Twins in Minigrids . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
Looking for Twins in Rows. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
Looking for Twins in Columns. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
Looking for Triplets in Minigrids . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
Looking for Triplets in Rows . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
Looking for Triplets in Columns . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
Modifying the SolvePuzzle() Function. . . . . . . . . . . . . . . . . . . . . . . . 127
Using Brute-Force Elimination. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
Modifying the Code Behind for the Solve Puzzle Button . . . . . . . . 133
Testing the Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
■CHAPTER 6 Generating Sudoku Puzzles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
Determining the Level of Difficulty . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
Steps to Generate a Sudoku Puzzle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
Determining the Locations of Empty Cells . . . . . . . . . . . . . . . . . . . . 144
Single-Solution Puzzles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
Implementing the Puzzle-Generating Algorithm . . . . . . . . . . . . . . . . . . . 148
Creating the Class. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
Randomizing the List of Possible Values . . . . . . . . . . . . . . . . . . . . . 150
Generating a New Puzzle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
Creating Empty Cells in the Grid . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
Vacating Another Pair of Cells . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
Exposing the GetPuzzle() Function . . . . . . . . . . . . . . . . . . . . . . . . . . 160
Wiring Up the Logic with the User Interface . . . . . . . . . . . . . . . . . . . . . . 162
Testing the Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
Easy Puzzles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
Medium Puzzles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
Difficult Puzzles. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
Extremely Difficult Puzzles. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
■CHAPTER 7 How to Play Kakuro . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
The Rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
Solving a Kakuro Puzzle. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
Tips for Solving Kakuro Puzzles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
■APPENDIX The SudokuPuzzle Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
■INDEX . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207