关于数独问题的算法的设计与实现

《关于数独问题的算法的设计与实现》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、ei,SHENFu-ke(EastChinaNormalUniversity,Shanghai200062,China)Abstract:TheproblemofSudokuisinventedbyaSwissmathematicianwhonamedEuler,anditbecomesmoreandmorepopularinthewholeglobe.Inthispaper,theauthorintroducedhowtodesigndatastructandalgorithmstosolvethemathematicproblem.Attheend,theau-thorimpl

3、ementthealgorithmwithC++language.Keywords:Sudoku;Algorithm;Backtracking1引言范围设计成82而不是81,是为了程序的易读性,使得数组元素的“数独sudoku”是十八世纪瑞士数学家欧拉发明的。2004年最大下标可达81,下同。11月12日,“数独”游戏登上了《泰晤士报》的版面,很快,作为该(2)intfix[82];报每日内容的“数独”游戏就风靡了英美!规则很简单:有9×9共该数组的用途是:若sd数组中某位置的数字不为0,则fix数81个方格(即依次有9个九宫格,详细图可参见第4节内容),在组相应位置的元素值记录为

4、1,否则记录为0。即fix数组是用来其中填入1到9的数字,让每个数字在每一行、每一列及每一个记录哪些位置的数字是已经确定下来的。九宫格里都只出现一次。谜题中会预先填入若干数字,其它方格(3)intpossible[82][10];为空白,玩家得依谜题中的数字分布状况,逻辑推敲出剩下的空该数组的用途是记录所有未确定数字的所有可能性。可能性格里是什么数字。由于规则简单,在推敲之中完全不必用到数学的记录方法是:possible数组各元素的值在初始化时被初始化为计算,只需运用逻辑推理能力,所以无论男女老幼,人人都可以与其第二维的下标一致,即0-9(其中0是不会用到的);中间计算玩,而且容易

5、上手、容易入迷。世界各地有很多数独俱乐部,还有过程中,若发现第一维某位置的某种可能性已不复存在,则将第的国家如法国等专门举行过数独比赛,其风靡程度可见一斑。一维下标是该位置而第二维下标是该不再可能的数字的元素值本文就是试图通过计算机程序来快速破解数独难题。改为-1。2程序架构设计(4)intstack[82];程序可以考虑使用人工智能的算法。所谓人工智能的算法,该数组的用途类似于栈,在核心回溯过程中起到至关重要的应当是算法设计者对该游戏的特性有较深入了解,依据其内在联作用。回溯之前,要把所有fix数组中值为0的位置依次存放进系设计出的和人类思维相似的解决算法。这似乎太过复杂。所以s

6、tack数组;回溯中,由低到高依次逐渐确定这些位置的数值,无法笔者准备主要采用回溯法解决这个问题。实践证明,回溯法解决确定者(即1-9的数字都不适合者)则应当回退到前一个位置,修数独问题,可以有着极快的效果(参见第4节),没有必要使用人改其假设值,以此类推,直至stack数组所存放的所有位置的值都工智能的算法。然而在采用回溯法之前,还可以利用一点小小的能确定,或回退到最初点的前一个位置。技巧以缩短回溯法的时间,甚至可将回溯法时间缩短为0。这个小3.2三个重要函数技巧可称为“有限递推”。下面先给出整个程序的简单框架,再分下面介绍几个在“有限递推”预处理和回溯过程中会用到的别介绍数据结

7、构以及算法的详细内容。三个重要函数,以便在后面看代码的过程中更易理解。另外还有程序框架:一些诸如题目合法性判断、行列九宫位置判断、打印、写文件等较易理解的函数就不再列出。(1)voidsetPb();该函数是用来修订possible数组的。其具体功能是:对于fix数组中每一个值为0的位置(即对于每一个没有确定下数字的位3数据结构与函数的介绍置),考察其可能的数字是哪些,记录下来(记录的方法参见3.1节3.1数据结构possible数组的介绍)。考察的方法是:在1-9这