高手玩的数独小程序（Java）

小学的时候玩过数独，在假期里做了好多数独题，初中的时候有一个同学给我发了一个特别难的数独题，是一个数学家出的，还据说有一个农民只花了一天的时间就做出来了。当时那个数独题实在是太难了，做到一定程度就感觉没有线索了。

后来大学之后学了编程，我就在想，可以自己写一个破解数独的程序来，让程序破解数独。于是我就自己想了一种算法，一个一个数字的往下测试，不通过就撤回，不通过就继续测试下一个数，最终破解的方法。

大一结束，疫情时代，暑假在家的时候做的，未参考任何数独破解相关资料就直接埋头做出来的。

草稿思路

结果

合影留念

import Java.util.ArrayList; import java.util.Scanner; /** * 破解数独的程序，java版 * 此程序要求使用者自己手动写入一个9*9标准数独，然后程序会对其破解 * 2020年7月19日 * @author littlefean */ public class Sudoku { public static void main(String[] args) { int[][][] sudokuBox = newTemp(); printSudoku(sudokuBox); startWrite(sudokuBox); printSudokuWithBorder(sudokuBox); crack(sudokuBox); printSudokuWithBorder(sudokuBox); } /** * 新创一个数独三维数组，返回这个三维数组 * 数独的数据结构是一个三维数组， * 其中第一维度是行， * 第二维度是列， * 第三维度是这个数的信息，含有两个元素，【数字，是否可写（0 1表示）】 * @return 返回这个三维数组 */ private static int[][][] newTemp(){ int[][][] box = new int[9][9][2]; for (int i = 0; i < 9; i ) { for (int j = 0; j < 9; j ) { box[i][j] = new int[]{0, 1}; } } //System.out.println(Arrays.deepToString(box)); return box; } /** * 打印数独三维数组 */ private static void printSudoku(int[][][] box){ for (int i = 0; i < 3; i ) { for (int j = 0; j < 3; j ) { for (int k = 0; k < 3; k ) { for (int m = 0; m < 3; m ) { System.out.print(box[i*3 j][k*3 m][0] " "); } System.out.print(" "); } System.out.println(); } System.out.println(); } } /** * 以含有边框的形式打印数独 * @param box 数独的三维数组 */ private static void printSudokuWithBorder(int[][][] box){ System.out.println("┏━━━━━━━┳━━━━━━━┳━━━━━━━┓"); for (int i = 0; i < 3; i ) { for (int j = 0; j < 3; j ) { System.out.print("┃ "); for (int k = 0; k < 3; k ) { for (int m = 0; m < 3; m ) { System.out.print(box[i*3 j][k*3 m][0] " "); } System.out.print("┃ "); } if(j != 3-1){ System.out.println(); } } if(i != 3-1){ System.out.println("\n┣━━━━━━━╋━━━━━━━╋━━━━━━━┫"); } } System.out.println("\n┗━━━━━━━┻━━━━━━━┻━━━━━━━┛"); } /** * 开始出题 * 传入数独数组，并要求用户输入数据对其内容进行修改 * 注意：该函数直接改变了三维数组参数的状态，所以不用返回值 * 注意：该函数没有处理输入异常，用户需要自觉输入整数 * @param box 空数独 * */ private static void startWrite(int[][][] box){ Scanner sc = new Scanner(System.in); System.out.println("提示：0表示空白位置，如果想删除某个位置的数，可以在输入数字的时候输入0，并覆盖相应的位置"); System.out.println("请输入数独中已知数的数量："); int num = sc.nextInt(); for (int i = 0; i < num; i ) { System.out.print("请输入第" i 1 "个数的数字："); int number = sc.nextInt(); System.out.print("数字在第几行？"); int y = sc.nextInt(); System.out.println("第几列？"); int x = sc.nextInt(); box[y-1][x-1][0] = number; box[y-1][x-1][1] = 0; } sc.close(); } /** * 判断整个数独是不是合法的，如果是，返回True，反之False。 * @param box 数独三维数组 * @return 如果是，返回True，反之False */ private static boolean isTrue(int[][][] box){ //判断所有行 for (int i = 0; i < 9; i ) { //遍历每一行： for (int j = 0; j < 9; j ) { //遍历1-9数字，看是否重复 int num = j 1; int numTimes = 0; for (int k = 0; k < 9; k ) { //遍历一行里的9个位置： if(box[i][k][0] == num){ numTimes ; } } if(numTimes>1){ return false; } } } //判断所有列 for (int i = 0; i < 9; i ) { //遍历每一列： for (int j = 0; j < 9; j ) { //遍历1-9数字，看是否超过1： int num = j 1; int numTimes = 0; for (int k = 0; k < 9; k ) { //遍历一列里的9个位置： if(box[k][i][0] == num){ numTimes ; } } if(numTimes>1){ return false; } } } //判断所有宫 for (int i = 0; i < 3; i ) { //遍历每一行宫 for (int j = 0; j < 3; j ) { //在每一行宫里遍历每一个宫 for (int k = 0; k < 9; k ) { //在每一个宫里遍历每一个数字： int num = k 1; int numTimes = 0; for (int m = 0; m < 3; m ) { //在每一个宫里遍历3行 for (int n = 0; n < 3; n ) { //在每一个宫的每一行里遍历三个位置： if(box[i*3 m][j*3 n][0] == num){ numTimes ; } } } if(numTimes>1){ return false; } } } } return true; } /** * 破解数独 * 输入一个数独三维数组，修改数独三维数组的内容使其成为一个完整的正确的数独三维数组 * 若发现无解则直接退出程序。 * 注意：此函数直接修改了数独的状态 * @param box 数独三维数组 */ private static void crack(int[][][] box){ //int[][] writeArray = new int[81][2]; //writeArray不知道多长，只能用集合表示 ArrayList<int[]> writeArray = new ArrayList<>(); for (int i = 0; i < 9; i ) { for (int j = 0; j < 9; j ) { if(box[i][j][1] == 1){ //在集合中增加box[i][j]这个数 writeArray.add(box[i][j]); } } } int x = 0; int n = 1; while(true){ //writeArray[x][0] = n; 编译器说这样不行 //Array type expected; found: 'java.util.ArrayList<int[]>' writeArray.get(x)[0] = n; if(isTrue(box)){ if(x == writeArray.size()-1){ System.out.println("破解成功"); break; }else{ x ; n=1; } }else{ while(true){ if(n >= 9){ if(x == 0){ System.out.println("无解"); System.exit(1); }else{ writeArray.get(x)[0] = 0; x --; n = writeArray.get(x)[0]; n ; } }else{ n ; break; } } } } } }

""" 破解数独-成功版 尝试破解标准数独，重新开始写代码 数独结构： [ [], [], [], [], [], [], [], [], [] ] [][][][][][][][][] [num, False] num表示此位置的数字，后面表示是是否可被更改 2020年7月8日 写好了全局判断函数 2020年7月18日 写好了破解函数，可以开始破解了 by littlefean """ def newTemp(): """ 创建一个空数独 调用该函数会返回一个9*9的二维列表，每个元素都是一个数字元素 :return: """ array = [] for i in range(9): array.append([]) for j in range(9): array[i].append([0, True]) return array # 这个函数在逻辑上是调用api的人写的，个人建议放在下面，即api函数应放一起，这个函数要单独放 def startWrite(array): """开始出题""" num = int(input("请输入初始数的数量：")) for i in range(num): print(f"请输入第{i 1}个数") num = int(input("您要输入的数字是多少？")) y = int(input("输入的数字在第几行？")) x = int(input("第几列？")) array[y - 1][x - 1][0] = num array[y - 1][x - 1][1] = False printSudokuTable(array) choice = input("数据输入完毕，开始破解输入1，修改输入数据请输入任意……") if choice != '1': while True: num = int(input("您要修改的数字是多少？")) y = int(input("输入的数字在第几行？")) x = int(input("第几列？")) array[y - 1][x - 1][0] = num array[y - 1][x - 1][1] = False printSudokuTable(array) do = input("是否开始破解？是请输入1，否则输入任意：") if do == '1': break return array def isTrue(array): """ 传入一个数独二维列表，判断其是否合法，若合法则返回真，否则返回假 :param array: 表示数独的二维列表 :return: """ # 判断所有行 for i in range(9): # 遍历每一行： for j in range(9): # 遍历1-9数字，看是否超过1： num = j 1 numTimes = 0 for k in range(9): # 遍历一行里的9个位置： if array[i][k][0] == num: numTimes = 1 if numTimes > 1: return False # 判断所有列 for i in range(9): # 遍历每一列： for j in range(9): # 遍历1-9数字，看是否超过1： num = j 1 numTimes = 0 for k in range(9): # 遍历一列里的9个位置： if array[k][i][0] == num: numTimes = 1 if numTimes > 1: return False # 判断所有宫 for i in range(3): # 遍历每一行宫 # y = i * 3 for j in range(3): # 在每一行宫里遍历每一个宫 # x = i * 3 for k in range(9): # 在每一个宫里遍历每一个数字： num = k 1 numTimes = 0 for m in range(3): # 在每一个宫里遍历3行 # y = m for n in range(3): # 在每一个宫的每一行里遍历三个位置： # x = n # if array[y][x][0] == num: if array[i * 3 m][j * 3 n][0] == num: numTimes = 1 if numTimes > 1: return False return True def printSudoku(array): """打印数独""" for i in range(3): # 三个大横段 for j in range(3): # 三横行紧凑 for k in range(3): # 横行里每三个数 for m in range(3): # 每一个数 print(array[i*3 j][k*3 m][0], end=" ") print(' ', end="") print() print() def printSudokuTable(array): """打印当前整个数独--有边框的方式""" print("┏━━━━━━━┳━━━━━━━┳━━━━━━━┓") for i in range(3): # 三个大横段 for j in range(3): # 每一行 print('┃ ', end="") for k in range(3): # 横行里每个组 for m in range(3): # 每一个数 print(array[i*3 j][k*3 m][0], end=" ") print('┃ ', end="") if j != 3-1: print('') if i != 3-1: print() print("┣━━━━━━━╋━━━━━━━╋━━━━━━━┫") print() print("┗━━━━━━━┻━━━━━━━┻━━━━━━━┛") def crack(soduArray): """破解数独""" # 先建立一个一维数组，存放数独可写位置 # 此数组里的对象是数独列表里的对象，所以可以直接引用，同步更改 writeArray = [] for i in range(len(soduArray)): for j in range(len(soduArray[i])): if soduArray[i][j][1]: writeArray.append(soduArray[i][j]) x = 0 n = 1 step = 0 while True: print(step) printSudokuTable(soduArray) writeArray[x][0] = n if isTrue(soduArray): step = 1 if x == len(writeArray)-1: print("破解成功") printSudokuTable(soduArray) break else: x = 1 n = 1 continue else: while True: step = 1 if n >= 9: if x == 0: exit("无解") else: writeArray[x][0] = 0 x -= 1 n = writeArray[x][0] n = 1 continue else: n = 1 break print(f"总共试了{step}个数") if __name__ == '__main__': # 初始化数独 sudoku = newTemp() print("欢迎使用破解程序，本程序由littlefean于2020年7月18日完成") print("下面进入数独初始状态输入阶段") print("提示：0表示空白位置，如果想删除某个位置的数，可以在输入数字的时候输入0，并覆盖相应的位置") # 开始出题 sudoku = startWrite(sudoku) print(isTrue(sudoku)) # 开始破解 crack(sudoku) input("end")

Python破解我那个初中同学发的很难的数独，花了30秒。而java几乎只花了3秒。Java的程序效率比Python的效率高出了很多。

下次我再改进程序的时候，我应该使用面向对象的方法把数独的元素封装起来，把数独写成一个类，方便使用。

肯定有比我的程序更好的算法。我的程序不一定很好。