Java & Python 破解数独（2020年7月18日）
创作背景
小学的时候玩过数独，在假期里做了好多数独题，初中的时候有一个同学给我发了一个特别难的数独题，是一个数学家出的，还据说有一个农民只花了一天的时间就做出来了。当时那个数独题实在是太难了，做到一定程度就感觉没有线索了。
后来大学之后学了编程，我就在想，可以自己写一个破解数独的程序来，让程序破解数独。于是我就自己想了一种算法，一个一个数字的往下测试，不通过就撤回，通过就继续测试下一个数，最终破解的方法。
大一结束，疫情时代，暑假再家的时候做的，未参考任何数独破解相关资料就直接埋头做出来的。
效果截图
破解完成
破解结果
程序流程图草稿
默认数独破解
源代码
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;
}
}
}
}
}
}
python版
"""
破解数独-成功版
尝试破解标准数独，重新开始写代码
数独结构：
[ [], [], [], [], [], [], [], [], [] ]
[][][][][][][][][]
[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的效率高出了很多。
反思与总结
下次我再改进程序的时候，我应该使用面向对象的方法把数独的元素封装起来，把数独写成一个类，方便使用。
肯定有比我的程序更好的算法。我的程序不一定很好。
