数独问题高效算法探究和实现

《数独问题高效算法探究和实现》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数独问题高效算法探究和实现摘要：数独益智游戏(Sudoku)是近年来全球流行的一种智力游戏。本文通过分析数据结构、"非循环判断"预处理算法和回溯算法，深入探讨了数独问题的解决方案，并给出了该方案的实现算法，实验证明该算法是正确髙效的。关键词：数独；非循环判断；算法；回溯法中图分类号：TP302“数独”益智游戏(Sudoku)是瑞士数学家欧拉发明的,目前在国内外非常流行。游戏在99的单元表格中进行，单元表格不仅被分为9行、9列，也被分为33个九宫格。单元表格中已存在若干数字，其余为空格。游戏规则要求玩家在每个空格中填入1〜9之间的数字，

2、使每个数字在每行、每列、每个九宫格仅出现一次。国内许多论文对数独游戏的教学意义做了深入讨论，但研究其求解算法的论文不多［1］,用计算机进行快速求解的算法更少，参考文献［2］使用“有限递推”预处理提高了算法的执行速度，但其本身每次都要处理候选数字也耗时不少；参考文献［3］提出了效率较高的算法，但其冲突检测还可提高效率。本文对“数独”游戏进行深入研究后用C语言设计出一种基于“非循环判断”预处理的回溯算法，然后用参考文献［2］中的三个实例及号称世界上迄今难度最大的数独游戏[4](芬兰数学家因卡拉花费3个月时间设计的)进行测试，实践证明该算法

3、正确且高效。1数据结构与回溯法简介1.1数据结构精心设计的数据结构可让算法更加高效[5]。主要的数据结构是5个整型数组，其中2个一维数组，3个二维数组:(1)intaResult[81],该数组的用途是接收题目(空白处则初始值为0)以及保存最终结果(所有的99个数字按序存储在该数组中)；(2)intaEmpty[81],该数组记载空白单元表格的序号和试填数字(前2位表示序号，第3位表示数字)，这样既可减少搜索空间又方便下一次试填数字(原试填数字+1);(3)intaRow[9][9],该数组标识某行某个数字是否存在，减少判断时间；(4

4、)intaCol[9][9],该数组标识某列某个数字是否存在，减少判断时间；(5)intaNine[9][9],该数组标识某九宫格某个数字是否存在，减少判断时间。1.2回溯法简介回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。探索到某一步，发现原先选择并不优或达不到目标时，就退回一步重新选择[6]。2预处理算法在读取数独问题时用特定数组记载空白单元表格的序号，过滤掉已填数字表格，减少搜索空间；判断某一空格能否填入某一数字时本文采用“非循环判断”预处理算法(一般采用循环判断[2][3]),该算法思想是：按序扫描问题时,对原有数字

5、进行预处理，即根据该格序号及数字对aRow、aCol和aNine数组进行相应标记，如：第9格(下标从0开始)的数字为5,预处理时该格行号为1、列号为0、九宫格序号为0,结果为：aRow[l][4]=1,aCol[0][4]=1,aNine[0][4]二1,则表明第1行、第0列和第0九宫格不能填数字5O3算法设计(1)读入数独问题。(2)给数组aEmpty、aResult、aRow、aCol和aNine赋初值。(3)按序扫描问题，把未填数字的空格序号乘以10后存入aEmpty数组，把已填数字或0按序号存入aResult数组，同时根据序号

6、及已经填的数字给aRow、aCol和aNine数组进行预处理。(4)如果aEmpty数组中存在未填写数字的空格序号，则从aEmpty数组中取出一个未填写数字的空格序号，否则执行(11)。(5)把取出的空格序号进行行号、列号及九宫格序号分解。(1)从数字1开始直到数字9尝试填写，并对其行、列及九宫格进行冲突判断，若尝试成功执行(7),否则执行(8)o(2)执行相应标识处理后转到(4)o(3)退回到上一个填数序号，若该填数序号存在则执行相应标识处理后执行(9),否则执行(12)。(4)如果原来填写数字的下一个数字存在，对原来填写数字的下一

7、个数字尝试填写。(5)下一个数字尝试填写成功执行(7),否则执行(8)。(6)成功找到1个解，退出。(7)无解，退出。//关键源代码voidgetAnswer(inttx){//tx表示未填空格数wh订e(no//bnum表示小格试填数字for(num=bnum+1；num