java回溯算法解数独问题

本文实例为大家分享了java回溯算法解数独问题,供大家参考,具体内容如下

下面来详细讲一下如何用回溯算法来解数独问题。

下图是一个数独题,也是号称世界上最难的数独。当然了,对于计算机程序来说,只要算法是对的,难不难就不知道了,反正计算机又不累。回溯算法基本上就是穷举,解这种数独类的问题逻辑比较简单。

不管算法懂不懂,先把类建出来,变量定义好,那放大学试卷上就是可以拿两分了。

package shudu;

/**
 * Created by wolf on 2016/3/17.
 */
public class Sudoku {
 private int[][] matrix;
 public Sudoku(int[][] matrix) {
  this.matrix = matrix;
 }

 public static void main(String[] args) {
  // 号称世界上最难数独
  int[][] sudoku = {
    {8, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 3, 6, 0, 0, 0, 0, 0},
    {0, 7, 0, 0, 9, 0, 2, 0, 0},
    {0, 5, 0, 0, 0, 7, 0, 0, 0},
    {0, 0, 0, 0, 4, 5, 7, 0, 0},
    {0, 0, 0, 1, 0, 0, 0, 3, 0},
    {0, 0, 1, 0, 0, 0, 0, 6, 8},
    {0, 0, 8, 5, 0, 0, 0, 1, 0},
    {0, 9, 0, 0, 0, 0, 4, 0, 0}};
  Sudoku s = new Sudoku(sudoku);
  s.backTrace(0, 0);
 }

 /**
  * 数独算法
  * @param i
  * 行号
  * @param j
  * 列号
  */
 private void backTrace(int i, int j) {

 }
}

用一个二维数组来存储这个矩阵,然后定义一个方法来计算。方法里有两个属性——行号和列号。

我们的原理就是从第0行0列开始,依次往里面填入1-9之间的数字,然后判断填入的这个数字是否能放进去(该行该列和它所在的小九宫格是否有重复数字)。如果能放进去,那么就继续用1-9去试该行的下一列。一直到该行的最后一列,然后换行继续重复上面的步骤(也就是执行backTrace方法)。一直执行到最后一个空格,也就是i=8,j=8的时候,且最后这个空格所放的值也完全符合规则,那么此时就算完成,不用再继续调用backTrace方法了,输出正确解即可。

所以回溯法样子看起来是这样的。给第一个空格填1-9中任何一个,开始判断,如果OK,然后进入下一层,如果不OK,就断掉了。下一层还是从1-9开始试,然后OK,不OK……当最终目标达到时,空格已填满又满足条件,那么中断该分支,输出结果。

继续我们的程序。

由于有些位置已经有数字了,所以我们需要判断,如果该坑已经有人蹲了,那么就把列号j加1,进入下一列。如果到第8列了,就换行。

修改程序如下:

package shudu;

/**
 * Created by wolf on 2016/3/17.
 */
public class Sudoku {
 private int[][] matrix;

 public Sudoku(int[][] matrix) {
  this.matrix = matrix;
 }

 public static void main(String[] args) {
  // 号称世界上最难数独
  int[][] sudoku = {
    {8, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 3, 6, 0, 0, 0, 0, 0},
    {0, 7, 0, 0, 9, 0, 2, 0, 0},
    {0, 5, 0, 0, 0, 7, 0, 0, 0},
    {0, 0, 0, 0, 4, 5, 7, 0, 0},
    {0, 0, 0, 1, 0, 0, 0, 3, 0},
    {0, 0, 1, 0, 0, 0, 0, 6, 8},
    {0, 0, 8, 5, 0, 0, 0, 1, 0},
    {0, 9, 0, 0, 0, 0, 4, 0, 0}};
  Sudoku s = new Sudoku(sudoku);
  s.backTrace(0, 0);
 }

 /**
  * 数独算法
  *
  * @param i 行号
  * @param j 列号
  */
 private void backTrace(int i, int j) {
  //如果i行j列是空格,那么才进入给空格填值的逻辑
  if (matrix[i][j] == 0) {
   for (int k = 1; k <= 9; k++) {
    //判断给i行j列放1-9中的任意一个数是否能满足规则
    if (check(i, j, k)) {
     //将该值赋给该空格,然后进入下一个空格
     matrix[i][j] = k;
     backTrace(i, j + 1);
    }
   }
  } else {
   //如果该位置已经有值了,就进入下一个空格进行计算
   backTrace(i, j + 1);
  }
 }

 /**
  * 判断给某行某列赋值是否符合规则
  *
  * @param row 被赋值的行号
  * @param line 被赋值的列号
  * @param number 赋的值
  * @return
  */
 private boolean check(int row, int line, int number) {
  //判断该行该列是否有重复数字
  for (int i = 0; i < 9; i++) {
   if (matrix[row][i] == number || matrix[i][line] == number) {
    return false;
   }
  }
  //判断小九宫格是否有重复
  int tempRow = row / 3;
  int tempLine = line / 3;
  for (int i = 0; i < 3; i++) {
   for (int j = 0; j < 3; j++) {
    if (matrix[tempRow * 3 + i][tempLine * 3 + j] == number) {
     return false;
    }
   }
  }

  return true;
 }
}

此时已经写好了判断某行某列赋某个值是否ok的方法,通过该方法就能校验出数字是否能放到该位置。
还缺少的是边界值的判断,就是当已经到最后一列了,还没到最后一行时,需要对行号加1,然后恢复列号为0。

修改一下backTrace方法,增加边界值判断。

package shudu;

/**
 * Created by wolf on 2016/3/17.
 */
public class Sudoku {
 private int[][] matrix;

 public Sudoku(int[][] matrix) {
  this.matrix = matrix;
 }

 public static void main(String[] args) {
  // 号称世界上最难数独
  int[][] sudoku = {
    {8, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 3, 6, 0, 0, 0, 0, 0},
    {0, 7, 0, 0, 9, 0, 2, 0, 0},
    {0, 5, 0, 0, 0, 7, 0, 0, 0},
    {0, 0, 0, 0, 4, 5, 7, 0, 0},
    {0, 0, 0, 1, 0, 0, 0, 3, 0},
    {0, 0, 1, 0, 0, 0, 0, 6, 8},
    {0, 0, 8, 5, 0, 0, 0, 1, 0},
    {0, 9, 0, 0, 0, 0, 4, 0, 0}};
  Sudoku s = new Sudoku(sudoku);
  s.backTrace(0, 0);
 }

 /**
  * 数独算法
  *
  * @param i 行号
  * @param j 列号
  */
 private void backTrace(int i, int j) {
  if (i == 8 && j == 9) {
   //已经成功了,打印数组即可
   System.out.println("获取正确解");
   printArray();
   return;
  }

  //已经到了列末尾了,还没到行尾,就换行
  if (j == 9) {
   i++;
   j = 0;
  }

  //如果i行j列是空格,那么才进入给空格填值的逻辑
  if (matrix[i][j] == 0) {
   for (int k = 1; k <= 9; k++) {
    //判断给i行j列放1-9中的任意一个数是否能满足规则
    if (check(i, j, k)) {
     //将该值赋给该空格,然后进入下一个空格
     matrix[i][j] = k;
     backTrace(i, j + 1);
    }
   }
  } else {
   //如果该位置已经有值了,就进入下一个空格进行计算
   backTrace(i, j + 1);
  }
 }

 /**
  * 判断给某行某列赋值是否符合规则
  *
  * @param row 被赋值的行号
  * @param line 被赋值的列号
  * @param number 赋的值
  * @return
  */
 private boolean check(int row, int line, int number) {
  //判断该行该列是否有重复数字
  for (int i = 0; i < 9; i++) {
   if (matrix[row][i] == number || matrix[i][line] == number) {
    return false;
   }
  }
  //判断小九宫格是否有重复
  int tempRow = row / 3;
  int tempLine = line / 3;
  for (int i = 0; i < 3; i++) {
   for (int j = 0; j < 3; j++) {
    if (matrix[tempRow * 3 + i][tempLine * 3 + j] == number) {
     return false;
    }
   }
  }

  return true;
 }

 /**
  * 打印矩阵
  */
 public void printArray() {
  for (int i = 0; i < 9; i++) {
   for (int j = 0; j < 9; j++) {
    System.out.print(matrix[i][j] + " ");
   }
   System.out.println();
  }
  System.out.println();
 }
}

可以看到,判断成功的标志是行号为8,且列号为9时,认为找到了正确解。为什么是9呢,因为在check(i,j,k)那一步,通过了的话,将值K赋给最后一个空格,此时并没有中断程序,而且进入了下一层循环backTrace(i,j + 1),所以i为8j为9时才是终解。程序到这里,运行一下看看,发现并没有任何输出值,并没有找到正确解,why?

下面要讲的就是该程序最关键的地方,也是比较难以理解的地方,就是对根节点的初始化。回溯算法讲究的是一条道走到黑,不撞南墙不回头,并且把所有的道都走完。

我们把问题简单化,譬如一共只有两个空格,只能放0和1,正确答案是00和11.我们给第一个空格放了0,此时我们不知道是否放了0之后,后面是否能完全正确的走完全程。就像走迷宫一样,你选择了第一个岔道,此时有可能第一个岔道就是错的,后面无论怎么走都对了不了,也有可能有多条道可以走。那么我们的做法是先第一步放0,发现没问题(符合只能放0和1的规则),然后走第二步,第二步如果走对了,那就直接走出去了,获得了一次正确的解(00)。如果第二步是个死胡同(01),那就要回头了,就是要回到原点,把第一步初始化一下,然后第一步走1,然后再继续后面的步骤。所以无论怎么样,你都需要在第二步走完之后,把第一步走的值给清掉,回归到原点。这样才能找到所有的正确路线。

问题放大一下,有N步(N未知),第一步有1-9共9种情况,第一步放了1,后面还有未知的步,那无论后面成功与否,你肯定都要去试第一步放2-9之间的数字。

看第51行for循环那里,第一次将数字1赋给第一个空格。然后判断是否OK,如果OK了,就进入第二个空格去了,后面具体走多少步我们就不管了,我们只需要在后面的走完之后,初始化第一个空格就行了。那要是不OK呢,不OK当然就不用管他了,这一层走完就没下文了,等于该分支就断了。所以我们要在第55行后面加一句初始化的操作matrix[i][j]=0.

完整代码如下:

package shudu;

/**
 * Created by wolf on 2016/3/17.
 */
public class Sudoku {
 private int[][] matrix;

 public Sudoku(int[][] matrix) {
  this.matrix = matrix;
 }

 public static void main(String[] args) {
  // 号称世界上最难数独
  int[][] sudoku = {
    {8, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 3, 6, 0, 0, 0, 0, 0},
    {0, 7, 0, 0, 9, 0, 2, 0, 0},
    {0, 5, 0, 0, 0, 7, 0, 0, 0},
    {0, 0, 0, 0, 4, 5, 7, 0, 0},
    {0, 0, 0, 1, 0, 0, 0, 3, 0},
    {0, 0, 1, 0, 0, 0, 0, 6, 8},
    {0, 0, 8, 5, 0, 0, 0, 1, 0},
    {0, 9, 0, 0, 0, 0, 4, 0, 0}};
  Sudoku s = new Sudoku(sudoku);
  s.backTrace(0, 0);
 }

 /**
  * 数独算法
  *
  * @param i 行号
  * @param j 列号
  */
 private void backTrace(int i, int j) {
  if (i == 8 && j == 9) {
   //已经成功了,打印数组即可
   System.out.println("获取正确解");
   printArray();
   return;
  }

  //已经到了列末尾了,还没到行尾,就换行
  if (j == 9) {
   i++;
   j = 0;
  }

  //如果i行j列是空格,那么才进入给空格填值的逻辑
  if (matrix[i][j] == 0) {
   for (int k = 1; k <= 9; k++) {
    //判断给i行j列放1-9中的任意一个数是否能满足规则
    if (check(i, j, k)) {
     //将该值赋给该空格,然后进入下一个空格
     matrix[i][j] = k;
     backTrace(i, j + 1);
     //初始化该空格
     matrix[i][j] = 0;
    }
   }
  } else {
   //如果该位置已经有值了,就进入下一个空格进行计算
   backTrace(i, j + 1);
  }
 }

 /**
  * 判断给某行某列赋值是否符合规则
  *
  * @param row 被赋值的行号
  * @param line 被赋值的列号
  * @param number 赋的值
  * @return
  */
 private boolean check(int row, int line, int number) {
  //判断该行该列是否有重复数字
  for (int i = 0; i < 9; i++) {
   if (matrix[row][i] == number || matrix[i][line] == number) {
    return false;
   }
  }
  //判断小九宫格是否有重复
  int tempRow = row / 3;
  int tempLine = line / 3;
  for (int i = 0; i < 3; i++) {
   for (int j = 0; j < 3; j++) {
    if (matrix[tempRow * 3 + i][tempLine * 3 + j] == number) {
     return false;
    }
   }
  }

  return true;
 }

 /**
  * 打印矩阵
  */
 public void printArray() {
  for (int i = 0; i < 9; i++) {
   for (int j = 0; j < 9; j++) {
    System.out.print(matrix[i][j] + " ");
   }
   System.out.println();
  }
  System.out.println();
 }
}

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

(0)

相关推荐

  • java使用回溯法求解数独示例

    复制代码 代码如下: import java.util.Calendar;import java.util.Date; public class Matrix { private int matrix[][]; private long timeAfter=0;  private long timeBefore =0; public Matrix(int m[][]) {  matrix = new int[9][9];  for (int i=0; i<9 ; i++)   for(int j

  • 简单实现java数独游戏

    本文实例为大家分享了java数独游戏的具体代码,供大家参考,具体内容如下 打算把javaFx需要的组件装好以后直接用javaFx的,但似乎eclipse的版本不对,安装了也不能用... 数独代码是在之前寒假受命写的,学了一个月java的成果,现在看来有些不足但毕竟是第一个程序,就直接放上来,数独终盘的实现直接用了暴力,时间复杂度有点高,懒得改了直接放代码 终盘实现: import java.util.Random; public class SudokuPuzzleGenerator { pri

  • java版数独游戏核心算法(一)

    之前学习javascript时用javascript写过一个数独游戏,最近看了一点java的内容,于是就心血来潮想搞一个java版的数独游戏. 现在将全部代码分享出来和大家学习交流,当然代码中有着各种各样的问题和不足之处,望各位朋友批评指点. 以下是生成数独地图的核心算法,算法不是很好,也是之前参考过网上的一些思想: package hlc.shudu.src; /* * 数独的帮助类,里面提供数据所需的所有算法 */ public class ShuduHelper { //数独地图数组 pr

  • java数独游戏完整版分享

    本文实例为大家分享了java数独游戏的具体代码,供大家参考,具体内容如下 自己写的数独游戏,共9关,代码如下: 1.DoShudu类用于产生数独数组 import java.util.Random; public class DoShudu { /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub int[][] cells=newshudu(); //ce

  • python实现数独游戏 java简单实现数独游戏

    使用python和java实现数独游戏,有比较才有收获哦. 1.Python版 #--coding:utf-8-- import random import itertools from copy import deepcopy def make_board(m=3): numbers = list(range(1,m**2+1)) #可能出现的数字为1-9 board = None #board是数度二维列表 while board is None: board = get_board(m,n

  • Java基于二维数组实现的数独问题示例

    本文实例讲述了Java基于二维数组实现的数独问题.分享给大家供大家参考,具体如下: 这里利用Java二维数组实现数独问题. (1)生成简易数独 (2)生成数独问题** 代码 import java.util.Random; import java.util.ArrayList; public class Suduku { /** *打印二维数组,数独矩阵 */ public static void printArray(int a[][]) { for (int i = 0; i < 9; i+

  • java版数独游戏界面实现(二)

    本文实例为大家分享了java版数独游戏界面实现的具体代码,供大家参考,具体内容如下 实现效果图: 这里写图片描述 主函数用于启动程序: package hlc.shudu.app; import hlc.shudu.src.ShuduHelper; import hlc.shudu.ui.ShuduMainFrame; public class AppStart { public static void main(String[] args) { ShuduMainFrame mainFrame

  • Java实现解数独的小程序

    前言 数独相信很多人都玩过,趣味性很强,十分的耐玩.可有没有程序员想过玩实现一个数独布局的算法呢?算法是个很有意思,很神奇的东西. 算法如下,需要预先给出几个固定的值,目前解决的一个最难的数独是大概26个已知值的情况,理论上应该能解决任意已知值的数独,不过不知道会不会迭代栈溢出--因为在26个已知值的情况下就迭代了3000多次了,囧~~~ 结果显示如下: 这是已知值: 1 1 2 1 4 8 1 5 5 1 6 1 1 7 7 1 8 3 2 1 1 2 2 6 2 4 4 3 5 9 3 7

  • java回溯算法解数独问题

    本文实例为大家分享了java回溯算法解数独问题,供大家参考,具体内容如下 下面来详细讲一下如何用回溯算法来解数独问题. 下图是一个数独题,也是号称世界上最难的数独.当然了,对于计算机程序来说,只要算法是对的,难不难就不知道了,反正计算机又不累.回溯算法基本上就是穷举,解这种数独类的问题逻辑比较简单. 不管算法懂不懂,先把类建出来,变量定义好,那放大学试卷上就是可以拿两分了. package shudu; /** * Created by wolf on 2016/3/17. */ public

  • 教你怎么用Java回溯算法解数独

    一.题干 输入一个9*9二维数组表示数独,已经填入的数字用1-9表示,待填入的数字用0表示,试写一个算法解出数独并输出. 二.思路 容易想到回溯法,即以人的思维的解数独,遍历数组,如果是空白就从1-9依次选一个数判断本行.列.3*3宫格内是否有重复,如果有就进行下一个数字的选择:如果该数暂时满足条件,那么进行下一个格子的选择,递归的终止条件是遍历完所有格子. 三.代码分段演示 输入数组 Scanner sc = new Scanner(System.in); int[][] board = ne

  • 浅谈Java实现回溯算法之八皇后问题

    目录 一.前言 二.浅谈递归 三.回溯算法 四.八皇后问题 五.八皇后变种 六.总结 一.前言 说起八皇后问题,它是一道回溯算法类的经典问题,也可能是我们大部分人在上数据结构或者算法课上遇到过的最难的一道题-- 二.浅谈递归 对于递归算法,我觉得掌握递归是入门数据结构与算法的关键,因为后面学习很多操作涉及到递归,例如链表的一些操作.树的遍历和一些操作.图的dfs.快排.归并排序等等. 递归的实质还是借助栈实现一些操作,利用递归能够完成的操作使用栈都能够完成,并且利用栈的话可以很好的控制停止,效率

  • java 实现迷宫回溯算法示例详解

    用一个7 x 7的矩形表示迷宫,0和1分别表示的是通路和障碍.通过设计编写程序找到蓝色小球达到蓝色旗子的路线 思路: 构建一个迷宫(用二维数组)实现找通路的方法findRoad() 构建二维数组不难,我们主要是要实现findRoad()这个方法,在实现这个方法前,我们需要约定好一下几个点:小球的位置当作入口(1,1),小旗的位置当作出口(5,5)数组里数的含义分别为(0没有走过).(1障碍).(2走过且为正确的路线).(3走过且为错误的路线)将我们每一步的走法称为策略:下 -> 右 -> 上

  • Java随机数算法原理与实现方法实例详解

    本文实例讲述了Java随机数算法.分享给大家供大家参考,具体如下: 软件实现的算法都是伪随机算法,随机种子一般是系统时间 在数论中,线性同余方程是最基本的同余方程,"线性"表示方程的未知数次数是一次,即形如: ax≡b (mod n)的方程.此方程有解当且仅当 b 能够被 a 与 n 的最大公约数整除(记作 gcd(a,n) | b).这时,如果 x0 是方程的一个解,那么所有的解可以表示为: {x0+kn/d|(k∈z)} 其中 d 是a 与 n 的最大公约数.在模 n 的完全剩余系

  • Java 归并排序算法、堆排序算法实例详解

    基本思想: 归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的.然后再把有序子序列合并为整体有序序列. 归并排序示例: 合并方法: 设r[i-n]由两个有序子表r[i-m]和r[m+1-n]组成,两个子表长度分别为n-i +1.n-m. j=m+1:k=i:i=i; //置两个子表的起始下标及辅助数组的起始下标 若i>m 或j>n,转⑷ //其中一个子表已合并完,比较选取结束 //选取r[i]和r[j]较小的存入辅助数组

  • java数组算法例题代码详解(冒泡排序,选择排序,找最大值、最小值,添加、删除元素等)

    数组算法例题 1.数组逆序 第一个和最后一个互换,第二个和倒数第二个互换,就相当于把数组想下图一样,进行对折互换,如果数组个数为奇数,则中间保持不变其余元素互换即可 import java.util.Arrays; class Demo12 { public static void main (String[] args) { int[] arr = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; System.out.println(Arrays.toString(arr));

  • Java DFA算法案例详解

    1.背景 项目中需要对敏感词做一个过滤,首先有几个方案可以选择: 直接将敏感词组织成String后,利用indexOf方法来查询. 传统的敏感词入库后SQL查询. 利用Lucene建立分词索引来查询. 利用DFA算法来进行. 首先,项目收集到的敏感词有几千条,使用a方案肯定不行.其次,为了方便以后的扩展性尽量减少对数据库的依赖,所以放弃b方案.然后Lucene本身作为本地索引,敏感词增加后需要触发更新索引,并且这里本着轻量原则不想引入更多的库,所以放弃c方案.于是我们选定d方案为研究目标. 2.

  • C语言回溯法解八皇后问题(八皇后算法)

    八皇后问题(N皇后问题)的回溯法求解 一.问题描述 在一个国际象棋棋盘上放置八个皇后,使得任何两个皇后之间不相互攻击,求出所有的布棋方法,并推广到N皇后情况. 二.参考资料 啥文字都不用看,B站上有个非常详细的动画视频解说,上链接!!! Click Here! 三.源代码 #include<iostream> #include<vector> #include<string> using namespace std; void put_queen(int x, int

  • 详解Java Bellman-Ford算法原理及实现

    目录 一 点睛 二 算法步骤 三 算法实现 四 测试 一 点睛 如果遇到负权边,则在没有负环(回路的权值之和为负)存在时,可以采用 Bellman-Ford 算法求解最短路径.该算法的优点是变的权值可以是负数.实现简单,缺点是时间复杂度过高.但是该算法可以进行若干种优化,以提高效率. Bellman-Ford 算法与 Dijkstra 算法类似,都是以松弛操作作为基础.Dijkstra 算法以贪心法选取未被处理的具有最小权值的节点,然后对其进行松弛操作:而 Bellman-Ford 算法对所有边

随机推荐