关于数独问题的算法的设计与实现
本栏目责任编辑:谢媛媛
开发研究与设计技术
雷蕾,沈富可
(华东师范大学计算机科学技术系,上海200062)
关于数独问题的算法的设计与实现
摘要:数独问题(Sudoku)是十八世纪瑞士数学家欧拉提出的、近年来风靡全球的一种智力游戏。本文通过分析数据结构、函数、以及预处理算法和回溯算法,深入探讨了数独问题的解决方案,并给出了该方案的具体实现。“有限递推”
关键词:Sudoku;算法;回溯法中图分类号:TP312
文献标识码:A
文章编号:1009-3044(2007)02-10481-02
TheDesignandImplementationoftheAlgorithmaboutSudoku
LEILei,SHENFu-ke
(EastChinaNormalUniversity,Shanghai200062,China)
Abstract:TheproblemofSudokuisinventedbyaSwissmathematicianwhonamedEuler,anditbecomesmoreandmorepopularinthewholeglobe.Inthispaper,theauthorintroducedhowtodesigndatastructandalgorithmstosolvethemathematicproblem.Attheend,theau-thorimplementthealgorithmwithC++language.
Keywords:Sudoku;Algorithm;

Backtracking
1引言
是十八世纪瑞士数学家欧拉发明的。2004年“数独sudoku”
游戏登上了的版面,很快,作为该《泰晤士报》11月12日,“数独”
报每日内容的游戏就风靡了英美!规则很简单:有9ד数独”9共81个方格(即依次有9个九宫格,详细图可参见第4节内容),在其中填入1到9的数字,让每个数字在每一行、每一列及每一个九宫格里都只出现一次。谜题中会预先填入若干数字,其它方格为空白,玩家得依谜题中的数字分布状况,逻辑推敲出剩下的空格里是什么数字。由于规则简单,在推敲之中完全不必用到数学计算,只需运用逻辑推理能力,所以无论男女老幼,人人都可以玩,而且容易上手、容易入迷。世界各地有很多数独俱乐部,还有的国家如法国等专门举行过数独比赛,其风靡程度可见一斑。
本文就是试图通过计算机程序来快速破解数独难题。
范围设计成82而不是81,是为了程序的易读性,使得数组元素的最大下标可达81,下同。
(2)intfix[82];
该数组的用途是:若sd数组中某位置的数字不为0,则fix数组相应位置的元素值记录为1,否则记录为0。即fix数组是用来记录哪些位置的数字是已经确定下来的。
(3)intpossible[82][10];
该数组的用途是记录所有未确定数字的所有可能性。可能性的记录方法是:possible数组各元素的值在初始化时被初始化为与其第二维的下标一致,即0-9(其中0是不会用到的);中间计算过程中,若发现第一维某位置的某种可能性已不复存在,则将第一维下标是该位置而第二维下标是该不再可能的数字的元素值改为-1。
2程序架构设计
程序可以考虑使用人工智能的算法。所谓人工智能的算法,应当是算法设计者对该游戏的特性有较深入了解,依据其内在联系设计出的和人类思维相似的解决算法。这似乎太过复杂。所以笔者准备主要采用回溯法解决这个问题。实践证明,回溯法解决数独问题,可以有着极快的效果(参见第4节),没有必要使用人工智能的算法。然而在采用回溯法之前,还可以利用一点小小的技巧以缩短回溯法的时间,甚至可将回溯法时间缩短为0。这个小技巧可称为“有限递推”。下面先给出整个程序的简单框架,再分别介绍数据结构以及算法的详细内容。
程序框架:
(4)intstack[82];
该数组的用途类似于栈,在核心回溯过程中起到至关重要的作用。回溯之前,要把所有fix数组中值为0的位置依次存放进
stack数组;回溯中,由低到高依次逐渐确定这些位置的数值,无法
确定者(即1-9的数字都不适合者)则应当回退到前一个位置,修改其假设值,以此类推,直至stack数组所存放的所有位置的值都
能确定,或回退到最初点的前一个位置。
3.2三个重要函数
下面介绍几个在预处理和回溯过程中会用到的“有限递推”三个重要函数,以便在后面看代码的过程中更易理解。另外还有一些诸如题目合法性判断、行列九宫位置判断、打印、写文件等较易理解的函数就不再列出。
(1)voidsetPb();
该函数是用来修订possible数组的。其具体功能是:对于fix
3数据结构与函数的介绍
3.1数据结构
最主要的数据结构是4个整型数组,其中3个被设计成一维数组,还有1个二维数组。
数组中每一个值为0的位置(即对于每一个没有确定下数字的位置),考察其可能的数字是哪些,记录下来(记录的方法参见3.1节
possible数组的介绍)。考察的方法是:在1-9这些数字中除去当
前行、列、九宫中已有的数字。
(1)intsd[82];
该数组的用途是接收题目以及保存最终结果。所有的9×9个数字被依次存储在该数组中,空白处则初始化为0。之所以把数组
收稿日期:2006-10-13
(2)boolfixAll();
该函数是用来修订fix数组和possible数组的,其返回值表示了在此次运行该函数过程中是否执行了修订。其具体功能是:对
作者简介:雷蕾(1982-),男,安徽省芜湖市人,华东师范大学计算机科学技术系硕士研究生;沈富可(1966-),男,山东高密人,华东师范大学网络中心主任,硕士生导师,主要从事计算机网络方向的研究工作。
481
数独求解算法的设计与实现_工学_高等教育_教育专区。数独是一项非常有意思的...( 01): 1 20 ; 3 王琼, 邹晟 数独问题的求解、 评价 与生成算法 的...
数独求解算法的设计与实现易 琚朱静文曹东1(广东药学院医药信息工程学院,广州...王琼.邹晟.Wang Qiong.Zou Sheng 数独问题的求解、评价与生成算法的研究[期刊...
龙源期刊网 http://www.qikan.com.cn 数独问题高效算法的研究与实现 作者:姜华林 来源:《计算机光盘软件与应用》2013 年第 12 期 摘要:数独益智游戏(Sudoku)是...
数独问题高效算法的研究与实现_互联网_IT/计算机_专业资料。 今日推荐 ... 2013年注会设计统考真题及答案67份文档 九妖笑话 2014年笑话大全之让你笑个够...
基于判定树结构 , 给出了生成有唯一解的初盘的算法 . [参考文献 ] ( References) [ 1 ] 雷蕾 ,沈富可 . 关于数独问题的算法的设计与实现 [ J ]. 电脑...
数独游戏的难度划分及创建算法设计_计算机软件及应用_IT/计算机_专业资料。龙源...“数独”智力游戏的难度划分与创建问题分解为建立终盘和初盘、难度评分、游戏 ...
数独问题高效算法研究与实现_互联网_IT/计算机_专业资料。数独问题高效算法的研究与实现 摘要:数独益智游戏(sudoku)是近年来全球流行的一种智力 游戏。本文通过...
关于数独问题的算法的设计与实现[ J]. 电脑知识与技术, 2007, 2( 2): 481-482. [2] 李盘荣. / 数独0游戏的算法研究与实现[ J]. 电脑知识与技术, ...
关于数独问题的算法的设计与实现[J]. 电脑知识与技术, 2007(2) :481-482. [3] 王琼,邹晟. 数独问题的求解、评价与生成算法的研究[J]. 南京师范大 学...
热门文档