优化搜索原则创建数独模型  

An Optimized Searching Model of Creating Sudoku Puzzles

作　　者：康劲[1] 粱嘉熹 李乐敏[1] 徐厚宝[1] 

机构地区：[1]北京理工大学数学系,北京100081

出　　处：《数学的实践与认识》2010年第2期97-102,共6页Mathematics in Practice and Theory

基　　金：北京理工大学教改项目

摘　　要：针对目前流行的数独游戏,建立数学模型,给出了创建不同难度的数独游戏的算法.首先,模型创造性地利用了数独游戏的解题算法的逆过程来创建一个完整的终盘.在此基础上,进一步优化创建终盘的搜索法则,保证了所采用的算法复杂度最小.最后,移去已有终盘上的一些格子以得到一道数独题的初盘,并在此过程中始终保证该问题有且只有唯一解.同时,基于人性化的原则,我们通过玩家使用的解题技巧和频率来划分难度.根据划分的难度等级,依次创建不同难度的数独游戏.A mathematical model is developed to create Sudoku puzzles with different difficulty levels. We first creatively utilize the puzzle-solving techniques to create a complete Sudoku grid which greatly reduce its complexity. Based on the reduction rules of the solving methods, we optimize the search in the process of constructing a complete Sudoku grid. Then some numbers of a complete Sudoku grid must be removed to create a puzzle. In the process, the puzzles-solving methods can guarantee the puzzle has unique solution. Based on the principle of human first, we reasonably rate the difficulty level of a puzzle by the solving methods people used frequently. According to the rating system, puzzle of different difficulty levels are developed.

关 键 词：数独 优化搜索 难度定义 

分 类 号：O229[理学—运筹学与控制论]