数独问题的生成与求解算法的研究  

Study On Generation and Solution Algorithm of Sudoku Problem

作　　者：曲海平[1] 岳峻[1] 王飞[2] 

机构地区：[1]鲁东大学信息与电气工程学院,烟台264025 [2]中国科学院电子学研究所,北京100190

出　　处：《科技通报》2017年第6期14-17,共4页Bulletin of Science and Technology

基　　金：国家自然科学基金青年项目(61204045);山东省科技重点研发项目(2015GGX101014);烟台市科技发展计划项目(2015ZH060)

摘　　要：针对数独问题的初盘生成与求解,对传统方法进行了改进。从数独初盘本身具有的性质出发,将生成有唯一解初盘的算法分为两步:首先基于规则生成终盘,再利用权重进行筛选确定生成初盘的解的唯一性;而初盘的求解,采用多叉树遍历算法框架,结合最小候选数的计算实现初盘的求解。实验结果实证改良后的算法极大地减少了搜索分支,达到了修枝限界的效果。In the paper,Sudoku problem is divided into two independent and related sub-problems :generating and solving original layout. Starting with the very nature of Sudoku's original layout,generating original layout which has a unique solution is divided into two steps:first,solvable original layout is generated based on rules, and then,desired layout is selected by weight calculation. To solve original layout, multi-tree search architecture based on minimum candidate number is purposed. The improved algorithm reduces search branches vastly and reaches the effect of pruning.

关 键 词：数独 初盘规则 最小候选数 

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