Java & Python 破解数独（2020年7月18日）

创作背景

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

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

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

效果截图

程序流程图草稿

默认数独破解

破解结果

破解完成

源代码

Java版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
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版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
"""
破解数独-成功版
尝试破解标准数独，重新开始写代码
数独结构：
    [ [], [], [], [], [], [], [], [], [] ]
        [][][][][][][][][]
            [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的效率高出了很多。

反思与总结

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

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