java数独游戏破解工具源代码

一、游戏原理，通过填充空格来完成数独游戏。

数独的解法需遵循如下规则：

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

二、解法思路（递归+回溯）

针对游戏规则，我采用对为空的位置，进行猜测填入除横行竖列以及3x3宫外其他数字。

然后依照上述方式再填入以后的数字。

如果在后续中遇到无数可填情况，证明之前填的数字有错误值，这时我进行回溯，重新填入其他数字，再进行上述方法，知道所有空格都填完。游戏破解

其中需要注意，可以先找出空格周围需要填的集合，进行从小到大排序，这样填错的的可能性小，回溯的次数也会降低，提高程序效率。

三、源代码

1. Game2类（游戏主类）

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;public class Game2 {public static void main(String[] args) {// 开始时间long sTime = System.nanoTime();// 执行时间（1s）char[][] board = {{'5', '3', '.', '.', '7', '.', '.', '.', '.'}, {'6', '.', '.', '1', '9', '5', '.', '.', '.'}, {'.', '9', '8', '.', '.', '.', '.', '6', '.'}, {'8', '.', '.', '.', '6', '.', '.', '.', '3'}, {'4', '.', '.', '8', '.', '3', '.', '.', '1'}, {'7', '.', '.', '.', '2', '.', '.', '.', '6'}, {'.', '6', '.', '.', '.', '.', '2', '8', '.'}, {'.', '.', '.', '4', '1', '9', '.', '.', '5'}, {'.', '.', '.', '.', '8', '.', '.', '7', '9'}};List<EmptyNumberComparable> ListAll = new ArrayList<>();for (int i = 0; i < board.length; i++) {//board[i] 表示第i+1个一维数组for (int j = 0; j < board[i].length; j++) {if (board[i][j] == '.') {//进行填充List<Character> chance = haveOther(board, i, j);ListAll.add(new EmptyNumberComparable(chance, i, j));Collections.sort(ListAll);}}}// 结束时间long eTime1 = System.nanoTime();// 计算执行时间System.out.printf("排序执行时长：%d 纳秒.", (eTime1 - sTime));int resultCode = mainSee(board, ListAll);if (resultCode == 0) {System.out.println("出现大错误");} else {System.out.println("完成");}for (int ii = 0; ii < board.length; ii++) {//board[i] 表示第i+1个一维数组for (int jj = 0; jj < board[ii].length; jj++) {System.out.print(board[ii][jj]);}System.out.println("");}// 结束时间long eTime = System.nanoTime();// 计算执行时间System.out.printf("执行时长：%d 纳秒.", (eTime - sTime));}//主递归程序public static int mainSee(char[][] board, List<EmptyNumberComparable> ListAll) {for (EmptyNumberComparable emptyNumberComparable : ListAll) {int i = emptyNumberComparable.getI();int j = emptyNumberComparable.getJ();if (board[i][j] == '.') {//进行填充// 开始时间long sTime = System.nanoTime();// 执行时间（1s）List<Character> chance = haveOther(board, i, j);// 结束时间long eTime = System.nanoTime();// 计算执行时间System.out.printf("找不同执行时长：%d 纳秒.", (eTime - sTime));// 开始时间long sTime1 = System.nanoTime();// 执行时间（1s）//寻找其他可能集合,如果为0证明某步填错,回退到前面if (chance.size() == 0) {return 0;} else {for (char c : chance) {board[i][j] = c;System.out.println(i + "," + j + "," + c);int resultCode = mainSee(board, ListAll);if (resultCode == 0) {System.out.println("返回" + i + "," + j + "," + c);System.out.println("出现错误" + c);} else {return 1;}}}// 结束时间long eTime1 = System.nanoTime();// 计算执行时间System.out.printf("递归执行时长：%d 纳秒.", (eTime1 - sTime1));System.out.println(i + "," + j + "把他弄成点");board[i][j] = '.';return 0;}}return 1;}//找不同public static List<Character> haveOther(char[][] board, int a, int b) {char[] all9 = {'1', '2', '3', '4', '5', '6', '7', '8', '9'};char[] other = new char[30];//遍历二维数组,找出同行与同列不同的数据int m = 0;for (int i = 0; i < board.length; i++) {if (board[i][b] != '.') {other[m] = board[i][b];m++;}}for (int j = 0; j < board.length; j++) {if (board[a][j] != '.') {other[m] = board[a][j];m++;}}//找身边九宫中的重复数据other = nineOther(board, other, a, b, m);return arrContrast(all9, other);}//九宫中不同值public static char[] nineOther(char[][] board, char[] other, int a, int b, int m) {int leftUp = 0;int leftDown = 0;int rightUp = 0;int rightDown = 0;if (a >= 0 && a <= 2) {if (b >= 0 && b <= 2) {//第1宫leftUp = 0;leftDown = 2;rightUp = 0;rightDown = 2;other = searchNine(board, other, leftUp, leftDown, rightUp, rightDown, m);}if (b >= 3 && b <= 5) {//第2宫leftUp = 0;leftDown = 2;rightUp = 3;rightDown = 5;other = searchNine(board, other, leftUp, leftDown, rightUp, rightDown, m);}if (b >= 6 && b <= 8) {//第3宫leftUp = 0;leftDown = 2;rightUp = 6;rightDown = 8;other = searchNine(board, other, leftUp, leftDown, rightUp, rightDown, m);}}if (a >= 3 && a <= 5) {if (b >= 0 && b <= 2) {//第4宫leftUp = 3;leftDown = 5;rightUp = 0;rightDown = 2;other = searchNine(board, other, leftUp, leftDown, rightUp, rightDown, m);}if (b >= 3 && b <= 5) {//第5宫leftUp = 3;leftDown = 5;rightUp = 3;rightDown = 5;other = searchNine(board, other, leftUp, leftDown, rightUp, rightDown, m);}if (b >= 6 && b <= 8) {//第6宫leftUp = 3;leftDown = 5;rightUp = 6;rightDown = 8;other = searchNine(board, other, leftUp, leftDown, rightUp, rightDown, m);}}if (a >= 6 && a <= 8) {if (b >= 0 && b <= 2) {//第7宫leftUp = 6;leftDown = 8;rightUp = 0;rightDown = 2;other = searchNine(board, other, leftUp, leftDown, rightUp, rightDown, m);}if (b >= 3 && b <= 5) {//第8宫leftUp = 6;leftDown = 8;rightUp = 3;rightDown = 5;other = searchNine(board, other, leftUp, leftDown, rightUp, rightDown, m);}if (b >= 6 && b <= 8) {//第9宫leftUp = 6;leftDown = 8;rightUp = 6;rightDown = 8;other = searchNine(board, other, leftUp, leftDown, rightUp, rightDown, m);}}return other;}//遍历寻找9宫中为空数值public static char[] searchNine(char[][] board, char[] other, int leftUp, int leftDown, int rightUp, int rightDown, int m) {for (int i = leftUp; i <= leftDown; i++) {for (int j = rightUp; j <= rightDown; j++) {if (board[i][j] != '.') {other[m] = board[i][j];m++;}}}return other;}//两数组相减public static List<Character> arrContrast(char[] a, char[] b) {List<Character> list = new ArrayList<>();//输入的部分你写了我就不管了for (int i = 0; i < a.length; i++) {//a中的数是否b中也存在boolean have = false;for (int j = 0; j < b.length; j++) {if (a[i] == b[j]) {have = true;break;}}if (!have) {list.add(a[i]);}}return list;}//找身边九宫中的重复数据
}

2.EmptyNumberComparable类（用于集合从小到大排序）

import java.util.List;class EmptyNumberComparable implements Comparable<EmptyNumberComparable> {private List<Character> chance; //姓名private int i; // iprivate int j; // jpublic EmptyNumberComparable(List<Character> chance, int i, int j) {this.chance = chance;this.i = i;this.j = j;}public List<Character> getChance() {return chance;}public void setChance(List<Character> chance) {this.chance = chance;}public int getI() {return i;}public void setI(int i) {this.i = i;}public int getJ() {return j;}public void setJ(int j) {this.j = j;}@Overridepublic int compareTo(EmptyNumberComparable user) {           //重写Comparable接口的compareTo方法，return this.chance.size() - user.getChance().size();}
}

3.java源文件（懒人专用）

csdn下载方式

https://download.csdn.net/download/licongzhuo/21132265

百度云下载方式

链接：https://pan.baidu.com/s/1ODr7OfayENKW0qbBPBRDiA 
提取码：f0pr