2008 Sudoku puzzles

PROBLEM B: Creating Sudoku Puzzles

Develop an algorithm to construct Sudoku puzzles of varying difficulty. Develop metrics to define a difficulty level. The algorithm and metrics should be extensible to a varying number of difficulty levels. You should illustrate the algorithm with at least 4 difficulty levels. Your algorithm should guarantee a unique solution. Analyze the complexity of your algorithm. Your objective should be to minimize the complexity of the algorithm and meet the above requirements.

Abstract:Targeting the unique numerical Rubik’s cube – Sudoku, we have studied a variety of heuristic intelligence algorithm, metrics of difficulty levels, a variety of Sudoku derivative algorithm as well as a range of principles that are sufficient to ensure the unique solution of Sudoku puzzles. Finally, we established a highly efficient randomized Sudoku puzzle generator.

First of all, we developed a computer backtracking algorithm of relatively high efficiency (see 4.5) which can quickly resolve all Sudoku puzzles(including those with multiple solutions) and developed basic metrics for mechanically assessing the difficulty degrees of Sudoku puzzles. On the basis of that, we created a heuristic intelligence algorithm system (see section 4) with multi-level self-detective mechanism targeting real Sudoku puzzles that have unique solutions. Such intelligence algorithm system can, in addition, stimulate manual puzzle-solving steps and record each step.

Next, we considered comprehensively the pros and cons of the long term development of Sudoku games and defined metrics of five difficulty levels with vague boundary standards. Within the levels we established, we have provided numerical and quantitative descriptions for the difficulties of the puzzles in the same level.

We believe, to generate a real Sudoku puzzle, uniqueness of solution is crucial. Therefore, it is the main and strict constraint of creating algorithm. In 5.2, we have listed the three principles that have to be followed to ensure the uniqueness of the solution.

Another key point of our considerations is to generate Sudoku puzzles of diversity, and we believe the diversity of the puzzles we generate bare direct influence to the market outlook for the algorithm. Therefore, regarding the diversity of the puzzles generated, we have provided up to 8 different transformed and derived methods (see 5.1), which will meet the diversity requirements of Sudoku puzzles.

Based on the above studies, the algorithm we have established can generate a variety of Sudoku puzzles with different difficulty levels subject to individual requirements of players. Our algorithm can also be used as a Sudoku puzzle generator.

Finally, we have, through the establishment of the optimal model (see 6.2), studied the complexity of the puzzle generating system and the changing value of the corresponding parameter setting at different degrees of difficulty.

Keywords: Numerical Rubik’s cube, Heuristic intelligence algorithm, Derivatives,

Backtracking algorithm, Self-detective mechanism, Optimal model

下载原稿(适合学习，但请务必自己先练习后看本文，否则将事倍功半)： 【Download】

附2008全美大学生数学建模大赛获奖名单： 【Download】

注：作者保留一切权利，转帖请注明出处，不得用于商业用途。*已出版论文禁止转载。