主页 > 案例大全 > 论文案例大全-基于不同算法设计的数独问题

论文案例大全-基于不同算法设计的数独问题

2021-03-25 03:48:12

  数独是一种以数字排列为基础的填空游戏,游戏规则是根据9x9方格中已知的数字,推理出所有剩余空格的数字,而随着科学技术的进步,我们可以用算法设计来解决数独问题。本文主要介绍了经典数独游戏,通过随机方法来生成数独终盘,再用“挖洞法”生成数独问题。在求解数独的过程中,以最经典的回溯法和舞蹈链算法(Dancing Links X)两种算法为研究对象,探寻在解决经典数独问题时,运用不同算法进行求解有何不同,另外还研究了应用于数独的高技巧解法—候选数法。最后还研究了拉斯维加斯算法在数独问题上的拓展。本课题采用Intellij IDEA工具进行开发,利用Java语言进行编写,以此来对数独游戏进行算法研究。研究不同算法如何应用于数独游戏,通过Java代码实现了基于Dancing Links X算法求解数独问题,基于回溯法求解数独问题。

  1.1课题研究背景

  算法是计算机科学领域的最重要的基石之一,而如何学习算法、了解算法并运用算法对于我们学习也是一件非常重要的事。本课题通过研究回溯法和舞蹈链算法在解决数独游戏方面是如何应用的,从而来进行算法研究。在日常生活中,解决问题的步骤一般为:1)认识问题;2)处理问题;3)解决问题,而在计算机领域中,最抽象的解决问题的思路为:1)输入数据;2)处理数据);3)输出数据,由此看来,处理数据为最核心的部分,而作为处理数据最中心的算法设计就显得格外重要。同一问题可以用不同算法解决,但一个算法的质量优劣对于解决问题以及实现问题所花费的时间和效率有着很重要的意义。

  算法分析的目的在于如何选择合适算法和如何不断的改进算法,主要从时间复杂度和空间复杂度两个方面来对算法进行评价。时间复杂度是指该算法的运行时间,一般来说,将计算机算法视为问题规模n的函数f(n),故算法的时间复杂度记做T(n)=Ο(f(n)),从公式表示看来,算法执行的时间的增长率与f(n)的增长率正相关,称作渐进时间复杂度(Asymptotic Time Complexity)。空间复杂度是指算法需要消耗的内存空间,其计算和表示方法与时间复杂度类似,一般都用复杂度的渐近性来表示。同样,研究数独游戏的算法也需要从这两个方面去考虑,算法还需要满足可读性、正确性和容错性这三个特性。

  本课题是以经典数独游戏为研究背景的。数独是源自于18世纪瑞士的一种数学游戏,起源于18世纪初瑞士数学家欧拉等人研究的拉丁方阵(Latin Square),是指在9x9的方格中随机挖出一些空,根据方格中的其他已知数字,推理出剩余所有数字,使得每一行的数字、每一列的数字、同时粗线格(3x3)里面的数字均为1-9,且都不重复,其9x9的方格用粗线格(3x3)划分为九宫,故又称九宫格。数独游戏因其直观简洁的玩法,可玩性高,十分受大众欢迎。随着科学技术的发展,通过算法设计可以将数独游戏的难度升高,使其更具有可玩性,这个要求也需要通过算法设计来计算如何挖空来提高游戏难度,而本课题通过挖空法随机生成数独,同时运用回溯法和Dancing Links X两种算法来完成数独游戏,并比较两种算法的区别。通过探寻不同算法如何应用于具体对象中的不同来达到对于算法设计更深刻的认识。本课题运用IDEA工具进行开发,因为IDEA是一个十分全面且强大的集成环境,而且本课题运用Java语言开发,易操作易懂。

  1.2课题研究的目的和意义

  数独游戏风靡至今,通过人们许多年的研究,发现了许多解题的技巧,其中有入门技巧、进阶技巧和高级技巧,而如何将这些技巧运用到解题当中去是其中一个目的。数独游戏越来越受到广大人们的喜欢,如何通过计算机增加游戏的难度,如何在更短的时间里生成更多的数独题,来更好的满足人们的需要,也是本课题研究的目的。生成数独盘之后,怎样求解能够更好的减少运行压力,能够更快的解出题目,也是本课题研究的目的之一。运用回溯法+剪枝经典算法和Dancing Link算法来求解数独游戏才是本课题最重要的目的。

  通过研究不同算法如何运用到具体实例,以及了解它们之间的区别和优缺点,能够使开发者更好的了解算法,能够产生更加深刻的认识,通过不断优化算法,在同一个问题中使用不同的算法来达到目的,并且区分优劣,能够在以后的更加复杂更加具体的问题中更好的解决问题。

  2相关算法介绍

  2.1 Dancing Links X算法介绍

  X算法是高德纳提出的解决精确覆盖问题的算法,而Dancing Links X算法是一种交叉十字循环双向链,用来优化X算法,所以叫DLX算法。而Dancing Links X实际上并不是一种算法,而是一种数据结构。这种数据结构在缓存和回溯的过程有着十分惊人的效率,不需要额外的空间,以及几乎线性的时间,而在整个求解的过程中,指针在数据之间跳跃着,故又很形象的被称为舞蹈链。Dancing Lines X对于每一个元素,包括它左边的第一个,右边的第一个,上面的和下面的,都连上双向指针,如果左边没有,就循环着连到最右边,右边上下同理,并且对于每一列会设立一个头元素,头元素置于列的最上方,那么删除一列的时候,直接删除头元素的左右指针,删除一行的时候,也删除每个元素的上下指针。

  X算法是一个深度优先的不确定性回溯算法,用由0和1组成的矩阵A来表示精确覆盖问题,目标是选出矩阵的若干行,使得其中的1在所有列中出现且仅出现一次。

  解x算法的步骤如下:

  1)如果矩阵A为空(没有任何列),则当前局部解即为问题的一个解,返回成功;否则继续。

  2)根据一定方法选择第c列。如果某一列中没有1,则返回失败,并去除当前局部解中最新加入的行。

  3)选择第r行,使得A[r,c](该步是不确定的)。

  4)将第r行加入当前局部解中。

  5)对于满足A[r,j]=1的每一列j,从矩阵A中删除所有满足A[i,j]=1的行,最后在删除第j列。

  6)对所得比A小的新矩阵递归地执行此算法。

  而DLX最大的优点就是删除列,我们知道删除列不是一个简单的操作,还需要把它所覆盖的行也删除,DLX算法所用到的数据结构在删除列方面表现十分优秀,它用到了双向循环十字链表,因此删除和恢复会比一般的算法要高效一些。

  删除操作主要为:

  L[R[x]]=L[x];

  R[L[x]]=R[x];

  恢复操作为:

  L[R[x]]=x;

  R[L[x]]=x;

  2.2回溯法介绍

  回溯法是一种选优搜索法,又称为试探法,它是一种系统地搜索问题的解的方法。主要思想就是在解决问题时,往前走一步进行计算,如果达不到目标解或者这个目标解不是最优选择,那么就返回上一层重新计算,这种走不通就退回再走的算法称为回溯法,而满足退一步条件的点称为“回溯点”。回溯法和穷举法有一些联系,这两种算法都是基于试探的,用回溯法生成解的过程是逐步生成的,而穷举法是将所有的解全部生成后,才去检查是否满足条件。回溯法的优点在于其程序结构明确,可读性强,容易理解,是一种内在程序和结构非常有条理的、能避免不必要重复搜索的穷举式搜索算法。当我们遇到一类问题,而这个问题可以分解,但是又不能得出明确的动态规划或者是递归解法时,那么这时候就可以考虑运用回溯法来解决问题。而我们通常会使用两种策略来避免无效搜索,一:用约束函数在回溯点处首先剪去不满足约束条件的子树,二:用限界函数剪去得不到问题的解或最优解的子树,约束函数和限界函数统称为剪枝函数。

  基于回溯法的数独解法问题主要要分为两种,一种是递归算法,一种是非递归算法,两种算法各有不同;

  递归回溯算法:

  void Backtrack(int t)

  {

  if(t>n)

  Output(x);

  else

  for(int i=f(n,t);i<=(g,t);i++)

  {

  x[t]=h(i);

  if(Constraint(t)&&Bound(t))

  Backtrack(t+1);

  }

  }

  非递归回溯算法:

  int x[n];

  void backTrack(int n)

  {

  int i=1;

  while(i>=1)

  {

  if(ExistNode(t))//当前节点存在(没有搜索过的!!!)子节点

  {

  for(j=下界;j<=上界;j++)//对于子集树,j从0到1循环

  {

  x取一个可能的取值;

  if(constraint(i)&&bound(i))//x满足约束条件和界限函数

  {

  if(x是个可行解)

  输出x;

  else//进入下一层

  i++;

  }

  }

  }

  else

  i--;//回溯(不存在子节点,返回上一层)

  }

  }

  递归算法和非递归算法都有其优缺点,递归算法结构清晰,可读性强,而且它会给调试程序带来很大方便,但如果需要处理的数据量比较大的时候,使用递归算法就会导致系统运行效率很低,在计算问题上耗费的时间和占用的内存空间都要比非递归算法要多。而非递归算法在处理大数据量的问题时就要比递归算法有效率得多,它的缺点就是代码可读性差。

  3两种基本算法的设计与实现

  3.1数独问题的分析

  3.1.1问题简介

  数独游戏一直深受广大人们的喜爱,能让公众在闲暇之余,发散思维,提高记忆力。而随着时间的经过,人们对数独有了不同的认识,人们发现,影响数独难度的因素有很多,就题目本身而言,包括不同阶层的技巧、各种技巧所用次数、是否有隐藏及隐藏的深度及广度的技巧组合、当前盘面可运用逻辑推导出的个数等等,在大众看来,如果数独盘面的提示数少,那么题目就会相对难,提示数多则会简单,这是一般人判断难易的思维模式,但实际并不然,数独谜题提示数的多少与难度并无绝对关系,如何通过算法研究来增加难度是一个需要研究的课题。

  在数独游戏中,共有9*9=81个空格,根据数独游戏的难度不同,数独盘里面的已知数字数量也会有所不同。候选数法解题的过程是先根据游戏规则,即每一行、每一列以及每一宫的数字均为1-9,且都不重复,逐渐排除不合适的候选数的过程,当某个宫格的候选数排除到只剩一个数的时候,那么这个数就是该宫格唯一的一个候选数,此时这个候选数就解开了。

  候选数法又分为隐式候选数法和显式候选数法。显式候选数法,顾名思义就是根据规则,很容易就判断出来,该空格的数值就为该数字,而隐式候选数法则有很多技巧,可以运用各种技巧或者各种技巧叠加的方式,进行选择。

  例如:如图3.1,根据游戏规则,我们知道,每一个宫里必须包含数字1-9,第1宫以及第3宫中都包含数字9,并且第1宫的9位位于第3行,第3宫的9位于第2行,这也就是说第2宫的9不能在第2行和第3行,所以第2宫的9只能放在e1中。

  图3.1数独示意图

  3.1.2解法技巧介绍

  单数链结构——双强链。所谓双强链是指如果在数独盘中,我们找到关于某个候选数的两条强链,且这两条强链的一侧在同一单元(行、列、宫)内,皇后问题,成为base,另一侧有共同作用格,成为cover。Base侧两端点之间不是矛盾关系就是上反对关系,他们之间必然可以是弱链。很明显这是个典型的强弱强链,其两端互为强关系,必有一真,据此可以删去cover侧两端点共同作用格内的候选数。

  在此介绍三种方法

  1.摩天楼(Skyscraper)

  图3.2摩天楼示意图

  数字A分别在某两行、列只能出现在两个可能的位置(这样就保证了数字A在该行、列的两个候选数构成强链),且其中一侧处于同一列、行(base)时,则可删去另一侧(cover)两个端点共同作用格(黄色区域)内的数字A。

  2.双线风筝(2-String Kite)

  图3.3双线风筝示意图

  当数字A在一行、一列均只能出现在2个可能位置(保证是强链),且该行和列的一个端点同处于同一宫(base),则可以删除另两个端点(cover)的共同作用格(黄色区域)内的候选数A。

  3.多宝鱼(Turbot Fish)

  图3.3双线风筝示意图

  多宝鱼结构在数字A在一行(列)和一宫中只能出现在2个可能的位置,且行(列)的一个端点和宫的一个端点位于同一行(列)(base),则可以删除另外两个端点(cover)共同作用格的候选数A。

  3.2生成数独

  随机生成数独第一行,其余补0,将此打乱转为稀疏矩阵求解并返回其中一个全覆盖矩阵作为数独答案,随机取其稀疏矩阵并验证作为数独问题。

  public List<Matrix>init(){

  //返回初始化level 1

  return init(1);

  }

  public List<Matrix>init(int level){

  int clue=getClue(level);

  //随机数独第一行

  puzzle=new Matrix(9,9);

  List<Integer>firstRow=new ArrayList<Integer>(Arrays.asList(1,2,3,4,5,6,7,8,9));

  Collections.shuffle(firstRow);

  for(int i=0;i<9;i++){

  puzzle.set(0,i,firstRow.get(i));

  }

  根据数独问题,创建稀疏矩阵,将数独问题转为精确度覆盖问题。有四个约束条件:

  *每格有且只有一个数字(0-80)index=i*9+j

  *每行九个数字不重复(81-161)index=i*9+x-1+81

  *每列九个数字不重复(162-242)index=j*9+x-1+162

  *每块九个数字不重复(243-323)index=n*9+x-1+243

  转换后,每行有4*9*9=324个元素行数最多有9*9*9=729,理论上有9+72×9=707行

  ?核心代码如下:

  public Matrix createSparseMatrix(Matrix puzzle){

  List<int[]>lines=new ArrayList<int[]>();

  for(int i=0;i<9;i++){

  for(int j=0;j<9;j++){

  if(puzzle.get(i,j)!=0){

  int[]line=new int[9*9*4];

  line[9*i+j]=1;

  line[9*i+puzzle.get(i,j)-1+9*9]=1;

  line[9*j+puzzle.get(i,j)-1+9*9*2]=1;

  line[9*getBlock(i,j)+puzzle.get(i,j)-1+9*9*3]=1;

  lines.add(line);

  }else{

  for(int k=1;k<=9;k++){

  int[]line=new int[9*9*4];

  line[9*i+j]=1;

  line[9*i+k-1+9*9]=1;

  line[9*j+k-1+9*9*2]=1;

  line[9*getBlock(i,j)+k-1+9*9*3]=1;

  lines.add(line);

  }

  }

  }

  }

  Matrix sparseMatrix=new Matrix(lines.toArray(new int[lines.size()][]));

  return sparseMatrix;

  }

  public Matrix coverMatrixToSudoku(Matrix coverMatrix){

  Matrix sudoku=new Matrix(9,9);

  for(int i=0;i<coverMatrix.length;i++){

  int row=0,col=0,num=0;

  for(int j=0;j<coverMatrix.get(0).length;j++){

  if(coverMatrix.get(i,j)==1){

  if(j>=81&&j<162){

  row=(j-81)/9;

  num=j%9+1;

  }else if(j>=162&&j<243){

  col=(j-162)/9;

  }

  }

  }

  sudoku.set(row,col,num);

  }

  return sudoku;

  }

  3.3基于Dancing Links X算法的数独问题

  3.3.1算法设计

  用Dancing Links X算法来解决数独问题,首先我们需要考虑的是精确覆盖问题,我们将其建成一个RxN的0 1矩阵,第i行第j列为1表示第i个集合里有元素j。

  X算法解决精确覆盖问题做法是这样的:

  在矩阵中找一个还有1的列,然后将这一列中的1遍历一遍,对于每一个遍历到的1,我们假设这一次选它所在的那一行。

  1.因为要求每一列恰好只能有一个1,所以我们要将与这一行的1的同一列的1给找出来,然后将找出来的1们与所在的那些行一起删掉。(因为如果一个集合中有一个数不能选,那么整个集合都是不能选的)

  2.再将选中的那一行删掉,并且将这一行的1们所在的列给删掉,表示这一列我已经找到一个1了。

  3.判断结果:

  (1)如果此时全部列都已经被删除了,那么就是找到了一种答案,然后返回;

  (2)如果列还没有被删除,那么就重复以上操作,如果任何一列中不包含1,那么就是没有找到合适方案,然后返回。

  可以看出,此做法虽然简单,但是会花费大量的空间和时间,代码复杂度也会很高。此时便有人提出了Dancing Links X算法,因为在X算法中每一次都需要寻找一列进行遍历,而Dancing Links X算法便提出每一列需要有一个带头的,所以就在矩阵上方就增加了一行,这一行称为c数组,其用来引领每一列,此外,Dancing Links X算法还提出还需要加一个head,放在c数组的前面,这个head与c数组之间也可以用双向循环链表连接,再运用X算法进行遍历,如果遍历到不正确的数,那么c数组中的元素会随着搜索列的删除而一起被删除,而最后当head的指向右边的指针指向head时,遍历成功,算法结束,即head.right=head,head=head.left。

  图3.4 Dancing Links X算法示意图

  3.3.2算法框架

  ?DLX的算法用递归过程用search(k)描述如下,k初始化为0

  If R[h]=h,print the current solution and return.

  otherwise choose a column object c

  cover column c

  for each r=D[c],D[D[c]],....,while r<>c

  set ok=r

  for each j=R[r],R[R[r]],...,while j<>r

  cover column j

  search(k+1)

  for each j=L[r],L[L[r]],...,while j<>r

  uncover column j

  uncover column c

  此外还定义了Node类,用来辅助DLX算法解决精确度覆盖问题。Node类一般包含上下左右行列及header七个属性,第一行辅助元素为特殊Node,即ColumnNode(可用继承实现),另包含size属性,表示所在列中1的个数。每个Node的header属性指向所在列的第一行辅助元素ColumnNode,ColumnNode指向自身。

  ?核心代码如下:

  class Node{

  int size=0;

  int row,col;//col for debug

  Node up,down,left,right,header;

  Node(int row,int col){

  this.row=row;

  this.col=col;

  }

  Node(Node header,int row,int col){

  this(row,col);

  this.header=header;

  }

  }

  3.2.3算法实现

  对于基于Dancing Links X算法,在数独问题上的具体算法实现如下:

  ?sparseMatrix:建立稀疏矩阵

  ?Ans():Ans数组,在求解的过程中保留当前的答案,以供最后输出答案用。

  ?header:求解的辅助元素,在求解的过程中,当判断出Head.Right=Head(也可以是Head.Left=Head)时,求解结束,输出答案(Head元素只有两个分量有用。其余的分量对求解没啥用)

  ?row:定义矩阵的行

  ?col:定义矩阵的列

  ?核心代码如下

  private void createDancingLinks(Matrix sparseMatrix){

  //root&&header

  root=new Node(0,0);//定义行和列

  Node header=root;//从root开始

  for(int i=0;i<sparseMatrix.get(0).length;i++){

  header.right=new Node(0,i+1);

  header.right.left=header;

  header.header=header;

  header=header.right;

  }

  header.right=root;

  header.right.left=header;

  //sparse matrix

  for(int row=0;row<sparseMatrix.length;row++){

  header=root.right;

  Node first=null;

  Node last=null;

  for(int col=0;col<sparseMatrix.get(0).length;col++){

  if(sparseMatrix.get(row,col)==1){

  Node node=header;

  while(node.down!=null){

  node=node.down;

  }

  node.down=new Node(header,row+1,col+1);

  node.down.up=node;

  if(first==null){

  first=node.down;

  }

  node.down.left=last;

  if(last!=null){

  node.down.left.right=node.down;

  }

  last=node.down;

  header.size++;

  }

  header=header.right;

  }

  if(last!=null){

  first.left=last;

  first.left.right=first;

  }

  }

  header=root.right;

  for(int col=0;col<sparseMatrix.get(0).length;col++){

  Node node=header;

  while(node.down!=null){

  node=node.down;

  }

  node.down=header;

  node.down.up=node;☆

  header=header.right;

  }

  }

  3.4基于回溯算法的解数独问题

  3.4.1算法设计

  回溯发的基本概念是采用深度优先的方式进行遍历,对于任一解的生成,回溯法都会采用扩大的方式,即在此解所在的位置进行扩大,以这个结点为中心开始搜索,这个结点成为当前部分解的扩展结点。在当前扩展节点处,开始向前进行搜索,探索一步,如若下一步可继续探索,此步的节点也成为当前的扩展结点,直至不能再向前探索为止,此时,该程序就会自动往回退一步,回到上一步的扩展结点,再进行不同的搜索,直至找到最后的解或者状态空间树没有节点为止。

  运用回溯法解数独,原理就是从第0行0列开始,依次往里面填入1-9之间的数字,然后判断填入的这个数字是否能放进去(该行该列和它所在的小九宫格是否有重复数字)。如果能放进去,那么就继续用1-9去试该行的下一列。一直到该行的最后一列,然后换行继续重复上面的步骤

  (也就是执行backTrace方法)。一直执行到最后一个空格,也就是i=8,j=8的时候,且最后这空

  格所放的值也完全符合规则,那么此时就算完成,不用再继续调用backTrace方法了,输出正

  确解即可。

  运用回溯法解题的思路如下:

  遍历已生成的数独二维数组,得出空白格子的数目。

  从第一个空白格子开始,利用数独的规范,对比同一列,同一行,以及同一个九宫格的数字,找出其所有可行解,存入数组(利用整形变量的位运算,会有更高的效率)。利用最后一个可行解,进行下一步运算。

  对剩下的格子进行同样的操作。

  如遇到无解的情况,则进行回溯操作。继续重复上述运算。

  当所有空白格子填满,所得结果,即为数独的解。

  3.4.2算法框架

  回溯法的基本思想为:

  (1)针对所给问题,定义问题的解空间

  (2)确定易于搜索的解空间结构

  (3)以深度优先方式搜索解空间,并在搜索过程中用剪枝函数避免无效搜索。

  下面介绍回溯法的实现框架:

  bool finished=FALSE;/*是否获得全部解?*/

  backtrack(int a[],int k,data input)

  {

  int c[MAXCANDIDATES];/*这次搜索的候选*/

  int ncandidates;/*候选数目*/

  int i;/*counter*/

  if(is_a_solution(a,k,input))

  process_solution(a,k,input);

  else{

  k=k+1;

  Construct_candidates(a,k,input,c,&ncandidates);

  for(i=0;i<ncandidates;i++){

  a[k]=c;

  make_move(a,k,input);

  backtrack(a,k,input);

  unmake_move(a,k,input);

  if(finished)

  return;/*如果符合终止条件就提前退出*/

  }

  }

  }

  对于其中的函数和变量,解释如下:

  a[]表示当前获得的部份解;

  k表示搜索深度;

  input表示用于传递的更多的参数;

  is_a_solution(a,k,input)判断当前的部分解向量a[1...k]是否是一个符合条件的解

  construst_candidates(a,k,input,c,ncandidates)根据目前状态,构造这一步可能的选择,存入c[]数组,其长度存入ncandidates

  process_solution(a,k,input)对于符合条件的解进行处理,通常是输出、计数等

  make_move(a,k,input)和unmake_move(a,k,input)前者将采取的选择更新到原始数据结构上,后者把这一行为撤销

  3.4.3算法实现

  对于基于递归的回溯算法,在解数独问题上的具体算法实现如下:

  声明变量:

  ?flag:一个二维数组,代表数独在初始状态中空白的区域

  ?rule:一个三维数组,代表三个规则:用于存储每行、每列及每宫的数字占用情况。当值为0表示未占用,1表示已占用

  ?sudoku:一个二维数组,用于存储数独的数字分布状态

  ?核心代码如下

  int rule[3][9][9],sudoku[9][9],flag[9][9];

  int findSmallIndex(int rowIndex,int colIndex){

  return(3*(rowIndex/3)+(colIndex/3));

  }

  int findNextValue(int rowIndex,int colIndex,int start){

  int index=findSmallIndex(rowIndex,colIndex);

  for(int i=start;i<9;i++){

  if(rule[0][rowIndex])continue;

  if(rule[1][colIndex])continue;

  if(rule[2][index])continue;

  return i;

  }

  return-1;

  }

  void changeRule(int rowIndex,int colIndex,int style){

  int index=findSmallIndex(rowIndex,colIndex);

  int value=sudoku[rowIndex][colIndex];

  rule[0][rowIndex][value]=style;

  rule[1][colIndex][value]=style;

  rule[2][index][value]=style;

  }

  void initSudoku(){

  for(int i=0;i<9;i++){

  for(int j=0;j<9;j++){

  sudoku[j]=getchar()-'0'-1;

  flag[j]=~sudoku[j]?0:1;

  if(!flag[j])changeRule(i,j,1);

  }

  getchar();

  }

  }

  void show(){

  for(int i=0;i<9;i++){

  string line="";

  for(int j=0;j<9;j++){

  line+='0'+sudoku[j]+1;

  }

  cout<<line<<endl;

  }

  }

  void solve(int rowIndex,int colIndex){

  if(colIndex==9){rowIndex++;colIndex=0;}

  while(rowIndex<=8&&!flag[rowIndex][colIndex]){

  colIndex++;if(colIndex==9){rowIndex++;colIndex=0;}

  }

  if(rowIndex>8){show();return;}

  while(~(sudoku[rowIndex][colIndex]=findNextValue(rowIndex,colIndex,sudoku[rowIndex][colIndex]+1))){

  changeRule(rowIndex,colIndex,1);

  solve(rowIndex,colIndex+1);

  changeRule(rowIndex,colIndex,0);

  }

  }

  int main(){

  long time1,time2;

  initSudoku();

  time1=clock();

  solve(0,0);//从(0,0)位置开始填数

  time2=clock();

  cout<<"求解过程共用"<<time2-time1<<"毫秒"<<endl;

  return 0;

  }

  3.4两种基本算法比较

  通过前面Dancing Links X算法和回溯法在数独问题上的应用,其实Dancing Links X算法是回溯法的一种,但是它拥有更好的数据结构来解决数独问题,而且它也是目前跑的最快的处理数独问题的算法,而回溯法被成为“五大算法”之一,有可读性高,易于理解的优点。

  Dancing Links X算法之所以更适用与解决数独问题,是因为它既有回溯法的基本思想,而且它运用的交叉十字循环双向链,即回溯法的基础上,增加了一组数组,并用一个head来引领整个数组,在删除列的问题上有着显著的优势,数独问题是一个很好的稀疏矩阵,DLX中的每一个元素都有6个分量,分别指向左边的元素、右边的元素、上面的元素、下面的元素、行标元素和列表元素,这样能很好的减少空间和时间的运算,比回溯法要方便许多。

  4拉斯维加斯算法在数独问题中的拓展

  4.1拉斯维加斯算法设计

  拉斯维加斯算法又称Les Vegas算法,拉斯维加斯算法是一个一定会找到正确的解的算法,字面意思就是一旦运用拉斯维加斯算法找到一个解,那么这个解一定是一个正确的解,随着采样次数的增多,算法得到的解是正确结果的概率逐渐增加的,虽然一定是正确的解,但是拉斯维加斯算法可能找不到解。数独游戏的总个数为9!x722x27x27704267971=6670903752021072936960(约6.67x10的21次方)种组合,组合数量巨大,所以我们可以运用拉斯维加斯算法生成一个数独终盘。

  具体做法为:用拉斯维加斯算法随机生成一个数独终盘,再用挖空法生成数独游戏盘,并且可以用通过挖空法来对数独游戏的难度进行控制,然后再用算法来对数独是否有唯一解进行计算。

  4.2算法代码

  用拉斯维加斯算法来随机生成一个数独终盘

  ?public static boolean lasVegas(int n){

  int i,j,k,value;

  Random random=new Random();

  //初始化

  for(i=0;i<9;i++){

  for(j=0;j<9;j++){

  field[j]=0;

  rows[j+1]=false;

  cols[j+1]=false;

  blocks[j+1]=false;

  }

  }

  //随机填入数字

  while(n>0){

  i=random.nextInt(9);

  j=random.nextInt(9);

  if(field[j]==0){

  k=i/3*3+j/3;

  value=random.nextInt(9)+1;

  if(!rows[value]&&!cols[j][value]&&!blocks[k][value]){

  field[j]=value;

  rows[value]=true;

  cols[j][value]=true;

  blocks[k][value]=true;

  n--;

  }

  }

  }

  //检查并且生成一个数组解

  if(dfs(field,rows,cols,blocks))

  return true;

  else

  return false;

  }

  ?用挖空法来生成一个数独问题

  public static void generateByDigMethod(int level){

  //从上到下从左到右的顺序挖洞

  for(int i=0;i<9;i++)

  for(int j=0;j<9;j++)

  if(checkUnique(i,j)){

  int k=i/3*3+j/3;

  rows[field[j]]=false;

  cols[j][field[j]]=false;

  blocks[k][field[j]]=false;

  field[j]=0;

  level++;

  if(81==level)

  break;

  }

  }

  ?来判断是否有唯一解

  public static boolean checkUnique(int r,int c){

  //挖掉第一个位置一定有唯一解

  if(r==0&&c==0)

  return true;

  int k=r/3*3+c/3;

  boolean[][]trows=new boolean[9][10];

  boolean[][]tcols=new boolean[9][10];

  boolean[][]tblocks=new boolean[9][10];

  int[][]tfield=new int[9][9];

  //临时数组

  for(int i=0;i<9;i++){

  for(int j=0;j<9;j++){

  trows[j+1]=rows[j+1];

  tcols[j+1]=cols[j+1];

  tblocks[j+1]=blocks[j+1];

  tfield[j]=field[j];

  }

  }

  //假设挖掉这个数字

  trows[r][field[r][c]]=false;

  tcols[c][field[r][c]]=false;

  tblocks[k][field[r][c]]=false;

  for(int i=1;i<10;i++)

  if(i!=field[r][c]){

  tfield[r][c]=i;

  if(!trows[r]&&!tcols[c]&&!tblocks[k]){

  trows[r]=true;

  tcols[c]=true;

  tblocks[k]=true;

  //更换一个数字之后检查是否还有另一解

  if(dfs(tfield,trows,tcols,tblocks))

  return false;

  trows[r]=false;

  tcols[c]=false;

  tblocks[k]=false;

  }

  }

  //已尝试所有其他数字发现无解即只有唯一解

  return true;

  }  

  1970属蛇女56岁后命运