基于“挖洞”思想的数独游戏生成算法

设计一个算法用以生成各种难度等级的数独题,通过对游戏规则的分析,首先从以下三个方面定义难度等级:已知格总数、已知格的分布和穷举搜索复杂度.本算法采用"挖洞"思想,经过以下两步生成数独题:1)运用拉斯维加斯随机算法生成一个终盘;2)采用以下五个操作"抹去"一部分数字来生成数独题:①根据所需要的难度等级选取一种挖洞顺序;②制定两个约束来控制已知格的分布;③通过深度优先搜索来求解,从而保证"挖去"一个数字后该数独题仍有唯一解;④引入剪枝技术来避免无效的"挖洞"尝试;⑤对"挖"好"洞"的数独题进行等效对称变换,以增加题目的多样性.可以生成游戏者所需要的任意5种难度的数独题.经过对算法时间和空间复杂度的分析,论证了本算法的有效性.对"挖洞法"的研究成果可总结为以下三个方面:1)通过对"挖洞"顺序的大量试探,找到了可生成高难度数独题的"挖洞"顺序;2)采用反证法来判断一个数独题解的唯一性;3)通过避免"回溯"和"重填"来降低算法的运行时间.

Sudoku Puzzles Generating:From Easy to Evil

Sudoku puzzle becomes worldwide popular among many players in different intellectual levels. The task is to devise an algorithm that creates Sudoku puzzles in varying level of difficulty. With the analysis of the game rules, we first define the difficulty level from four aspects as: total given cells, distribution of given cells and complexity of enumerating search. By the guidance from the definition of difficulty level, the algorithm for generating puzzles is developed with the "dig-hole" strategy on a valid grid. Thus, the algorithm developed in two steps: to create a valid grid by Las Vegas algorithm, and then to generating puzzles by erasing some digits using five operators : · Determine a sequence of digging holes according to the desirable difficulty level, · Set two restrictions to guide the distribution of given cells, · Judge whether a puzzle being dug out has a unique solution by a solver built using Depth-First Search, · Add pruning technique to avoid digging an invalid cell, and · Perform propagating at a dug-out puzzle to raise the diversity of the output puzzle. Using our developed algorithm, we generate Sudoku puzzles in any five difficulty levels.The difficulty level of output puzzles can be adjusted by a desirable difficulty value input by players. The complexity of the algorithms in space and time is analyzed to demonstrate the effectiveness of the algorithms. Our main contributions in exploring the "dig-hole" strategy are summarized as following three works: to do a massive research on the sequence of digging holes and how it affects the algorithm to create a evil-level puzzle with minimal given cells, to invent a skill for judging the solution's uniqueness of a puzzle being dug out by the reduction to absurdity, and to reduce the computational time by avoiding backtracking to an explored cell and refilling an empty cell.