数独求解算法（回溯法和唯一解法）java实现

2024-06-02 11:30| 来源: 网络整理| 查看: 265

数独（すうどく，Sudoku）是一种运用纸、笔进行演算的逻辑游戏。玩家需要根据9×9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫内的数字均含1-9，不重复。注：数独的各种知识和解决思路请参考http://www.llang.net/sudoku/

一、DFS深度填数检测+回溯法

参考：blog.csdn.net/hll174/article/details/51090461

1、先把有数字的地方设置标记位为true

2、循环遍历数组中没有标记位true的地方，也就是需要填数的地方，如果当前为0，即a[i][j]==0，判断当前所在的九宫格，然后从

数字1-9依次检测是否在行、列、宫中唯一满足唯一的话，则吧数字赋值给a[i][j]=l+1;然后继续深度遍历为true的话就返回true,否

则回溯a[i][j]==0等，不满足满足唯一则判断下一个数字，直到1-9都判断不满足则返回false,会回溯到上一层如果当前没有0，说

明都已经填满且符合唯一条件，则返回true;结束

代码：

import java.util.Scanner; public class Shudu { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (sc.hasNextInt()) { int[][] a = new int[9][9]; boolean[][] cols = new boolean[9][9]; boolean[][] rows = new boolean[9][9]; boolean[][] blocks = new boolean[9][9];// 九大宫的九个数字 for (int i = 0; i < a.length; i++) { for (int j = 0; j < a.length; j++) { a[i][j] = sc.nextInt(); if (a[i][j] != 0) { int k = i / 3 * 3 + j / 3;// 划分九宫格,这里以行优先，自己也可以列优先 int val = a[i][j] - 1; rows[i][val] = true; cols[j][val] = true; blocks[k][val] = true; } } }// 数据装载完毕 DFS(a, cols, rows, blocks); for (int i = 0; i < 9; i++) { for (int j = 0; j < 8; j++) { System.out.print(a[i][j] + " "); } System.out.println(a[i][8]); } } } public static boolean DFS(int[][] a, boolean[][] cols, boolean[][] rows, boolean[][] blocks) { for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { if (a[i][j] == 0) { int k = i / 3 * 3 + j / 3; for (int l = 0; l < 9; l++) { if (!cols[j][l] && !rows[i][l] && !blocks[k][l]) {// l对于的数字l+1没有在行列块中出现 rows[i][l] = cols[j][l] = blocks[k][l] = true; a[i][j] = 1 + l;// 下标加1 if (DFS(a, cols, rows, blocks)) return true;// 递进则返回true rows[i][l] = cols[j][l] = blocks[k][l] = false;// 递进失败则回溯 a[i][j] = 0; } } return false;// a[i][j]==0时，l发现都不能填进去 }// the end of a[i][j]==0 } } return true;// 没有a[i][j]==0,则返回true } }

二、唯一解法

1、显性唯一解法

如果某行已填数字的单元格达到8个,那么该行剩余单元格能填的数字就只剩下那个还没出现过的数字；同理，如果某列已填数字的单元格达到8个,那么该列剩余单元格能填的数字就只剩下那个还没出现过的数字；如果某九宫格已填数字的单元格达到8个,那么该九宫格剩余单元格能填的数字就只剩下那个还没出现过的数字。

2、隐性唯一解法

顾名思义，隐式唯一候选数法也是唯一候选数法的一种，但它不如显式唯一候选数法那样显而易见。由于1-9这9个数字要在每行、每列和每个九宫格内至少出现一次，所以如果某个数字在某行、某列或是某个九宫格内所有单元格的候选数列表中只出现一次，那么这个数字就应该填入它出现的那个单元格内，并且从该格所在行、所在列和所在九宫格内其它单元格的候选数列表中删除该数字。

解题思路：

1、用排除法求取每个值为0的空格所有可能的候选数；

2、用隐性唯一解法查看是否有值为0的空格是的值可以确定；

3、在1，2过程中当某空格是的值可以确定后则将该值从该格所在行、所在列和所在九宫格内其它单元格的候选数列表中删除该数字；

4、若某空格的候选数发生变动时，应查看候选数是只在一个，以及对与该格所在行、所在列和所在九宫格内其它单元格的候选数集的影响；

代码：

package paichufa; public class Shudu { int[][] sudo = new int[9][9]; // 保存数独数组 int[][][] may = new int[9][9][9];// may[i][j][k]保存sudo[i][j]可能的候选数，sudo[i][j]已确定时may[i][j][k]=0 public static void main(String[] args) { // TODO Auto-generated method stub } private void Way() { // 显式解 for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { if (sudo[i][j] == 0) { this.paichu(i, j); // System.out.println(); if (may[i][j][1] == 0) { sudo[i][j] = may[i][j][0]; may[i][j][0] = 0; this.delete(i, j, sudo[i][j]); } }// End if(sudo[i]==0) } } // 隐式解 for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { if (sudo[i][j] == 0) { boolean influ=this.bijiao(i, j); // System.out.println(); if (influ) { //当获得某一元素的解后对非同行，同列，同九宫的元素的候选数均有影响 i=0; j=0; } }// End if(sudo[i]==0) } } }// End A /** * * @Description: * 填充may[i][j][k]，并遍历与sudo[i][j]同行，同列，同九宫元素，获取sudo[i][j]可能的候选数，填充到may * [i][j]中 * @param @param i * @param @param j * @return void * @throws * @date 2016年9月9日 */ //初始化各空格候选数 private void paichu(int i, int j) { if (may[i][j][0] == 0) { for (int k = 1; k < 10; k++) { may[i][j][k] = k; } } for (int m = i / 3 * 3; m < i / 3 * 3 + 3; m++) {// 同九宫遍历 for (int n = i / 3 * 3; n < i / 3 * 3 + 3; n++) { if (sudo[m][n] != 0 && m != i && n != j) { int r = 0; while (may[i][j][r] != 0) { if (may[i][j][r] == sudo[m][n]) { may[i][j][r] = 0; for (int k = r; k < 8; k++) { int temp = may[i][j][k]; may[i][j][k] = may[i][j][k + 1]; may[i][j][k + 1] = temp; } } r++; } } } } // 同行遍历 for (int n = 0; n < 9; n++) { if (sudo[i][n] != 0 && n != j) { int r = 0; while (may[i][j][r] != 0) { if (may[i][j][r] == sudo[i][n]) { may[i][j][r] = 0; for (int k = r; k < 8; k++) { int temp = may[i][j][k]; may[i][j][k] = may[i][j][k + 1]; may[i][j][k + 1] = temp; } } r++; } } } // 同列遍历 for (int m = 0; m < 9; m++) { if (sudo[m][j] != 0 && m != i) { int r = 0; while (may[i][j][r] != 0) { if (may[i][j][r] == sudo[m][j]) { may[i][j][r] = 0; for (int k = r; k < 8; k++) { int temp = may[i][j][k]; may[i][j][k] = may[i][j][k + 1]; may[i][j][k + 1] = temp; } } r++; } } } } /** * * @Description: 当sudo[i][j]确定时，遍历与sudo[i][j]同行，同列，同九宫各元素的候选数若包含在其中，则从该候选数集中删除， * 并且在删除后候选数集中仅剩唯一解，则可以确定其解，然后以该元素的行，列，解值为参数进行递归调用； * @param @param i * @param @param j * @param @param del 要从各候选数集中删除的值 * @return void * @throws * @author 刘林立 * @date 2016年9月9日 */ private void delete(int i, int j, int del) { // 同九宫遍历 for (int m = i / 3 * 3; m < i / 3 * 3 + 3; m++) { for (int n = i / 3 * 3; n < i / 3 * 3 + 3; n++) { if (may[m][n][0] != 0 && m != i && n != j) { for (int r = 0; r < 8 && may[m][n][r] != 0; r++) { if (may[m][n][r] == del) { may[m][n][r] = 0; while (r < 8 && may[m][n][r] < may[m][n][r + 1]) { int temp = may[m][n][r]; may[m][n][r] = may[m][n][r + 1]; may[m][n][r + 1] = temp; r++; } if (may[m][n][1] == 0) { sudo[m][n] = may[m][n][0]; may[m][n][0] = 0; this.delete(m, n, sudo[m][n]); } } } } } } // 同行遍历 for (int n = 0; n < 9; n++) { if (may[i][n][del - 1] != 0 && n != j) { for (int r = 0; r < 8 && may[i][n][r] != 0; r++) { if (may[i][n][r] == del) { may[i][n][r] = 0; while (r < 8 && may[i][n][r] < may[i][n][r + 1]) { int temp = may[i][n][r]; may[i][n][r] = may[i][n][r + 1]; may[i][n][r + 1] = temp; r++; } if (may[i][n][1] == 0) { sudo[i][n] = may[i][n][0]; may[i][n][0] = 0; this.delete(i, n, sudo[i][n]); } } } } } // 同列遍历 for (int m = 0; m < 9; m++) { if (may[m][j][del - 1] != 0 && m != i) { for (int r = 0; r < 8 && may[m][j][r] != 0; r++) { if (may[m][j][r] == del) { may[m][j][r] = 0; while (r < 8 && may[m][j][r] < may[m][j][r + 1]) { int temp = may[m][j][r]; may[m][j][r] = may[m][j][r + 1]; may[m][j][r + 1] = temp; r++; } if (may[m][j][1] == 0) { sudo[m][j] = may[m][j][0]; may[m][j][0] = 0; this.delete(m, j, sudo[m][j]); } } } } } } /** * * @Description:将may[i][j]中的所有元素（候选数）依次和与sudo[i][j]同行，同列，同九宫各元素的候选数相比较（在比较时，若sudo[i][j]=0，候选数集不能为空）,若某一元素为该候选数集独有，则该元素即为sudo[i][j]的解； * * @param @param i * @param @param j * @param @return * @return boolean * @throws * @author 刘林立 * @date 2016年9月9日 */ private boolean bijiao(int i, int j) { int k = 0; int bijiao = may[i][j][k]; boolean find = true; while (may[i][j][k] != 0 && k < 9) { // 同九宫遍历 for (int m = i / 3 * 3; m < i / 3 * 3 + 3 && find; m++) { for (int n = i / 3 * 3; n < i / 3 * 3 + 3 && find; n++) { if (may[m][n][0] != 0 && m != i && n != j) { for (int r = 0; r < 8 && may[m][n][r] != 0 && find; r++) { if (may[m][n][r] == bijiao) { find = false; } } } } } if (find) { break; } // 同行遍历 for (int n = 0; n < 9 && find; n++) { if (may[i][n][0] != 0 && n != j) { for (int r = 0; r < 8 && may[i][n][r] != 0 && find; r++) { if (may[i][n][r] == bijiao) { find = false; } } } } if (find) { break; } // 同列遍历 for (int m = 0; m < 9 && find; m++) { if (may[m][j][0] != 0 && m != i) { for (int r = 0; r < 8 && may[m][j][r] != 0 && find; r++) { if (may[m][j][r] == bijiao) { find = false; } } } } if (find) { break; } k++; } if (find && may[i][j][k] != 0 && k < 9) { sudo[i][j] = may[i][j][k]; may[i][j][k] = 0; this.delete(i, j, sudo[i][j]); } return find; } }

【本文地址】

公司简介

联系我们