背景

  之前上python课的时候，有一次实验是求解数独，要求时间复杂度要低；为此老师讲解了一个高效的数独算法，我觉得算法挺有意思的，写篇博客记录一下。


描述

首先需要知晓数独的两个规则：

  1. 若某个位置的值已经确定，那么，和这个位置在同一行，同一列，同一个3×3的格子，都不能填写这个值，比如，九宫格（1，1）位置的值为2，那么，第一行，第一列，以及第一个3×3的格子里，都不能在填2了；
  2. 若某一行，或者某一列，或者某一个3×3里面，只有一个位置可能填1（假如是1），那么1一定是填写在这个位置，因为没有其他位置可以填它了；、

求解步骤

  1. 创建一个三维数组，假设就叫“可能值数组”，记录数独9×9的81个位置中，每个位置可能填写的值，初始情况下，每个位置的可能值都是1到9，表示每个位置都可能填写1-9中任何一个数字；

  2. 遍历数独的每一个位置，若某个位置已经有值，则将这个位置的可能值更新为这个值，比如，九宫格上，（1，1）的值已经确定是2了，那就将三维数组中（1，1）位置的可能值从[1-9]更新为[2]，直到所有的位置更新完毕；

  3. 使用上述规则1进行剪枝：

    （1）：从第一个位置开始遍历九宫格，若当前遍历到的位置（i,j），它的值已经知晓，那么就更新可能值数组，将第i行，第j列，以及其对应的3×3（【i/3×3 , j/3×3】就是这个3×3的第一个点）的所有位置，它们的可能值都要去除（i，j）位置的值；

    （2）：若某个位置在经过上一步的剪枝后，可能值只剩下一个了，那这个位置的值就确定了，比如说，位置（1，1）的初始可能值是1到9，经过上面的一步步去除，只剩下一个3了，那这个（1，1）位置填写的值必定就是3了。此时我们可以再次使用规则1，即第一行，第一列，以及其对应的3×3中，所有的格子的可能值不能有3；

    （3）：依次遍历每一个位置，使用上面的规则1，直到最后一格子，第一次剪枝便完成了；

  4. 使用上面的规则2进行剪枝：

    （1）：统计每一行，每一列，以及每一个3×3中，每个数出现的次数，比如统计第一行每个格子的可能值，看1-9各出现几次，若某个可能值只出现一次，那出现这个值的位置，就是填写这个值，比如说，在第一行，3这个数字，只有（1，1）这个位置可能填写，那（1，1）就是填3，因为其他位置的可能值当中都不包含3，也就是都不能填写3；

    （2）：根据上一步确定了某个位置的值后，那我们此时又可以使用规则1了，比如，上一步确定了（1，1）是填写3，那么第一行，第一列，以及第一个3×3中其余的格子， 都不能在写3了，我们从可能值数组中，将这些位置的可能，值删除3这个数；

    （3）：而此时，又可能出现上面的第3步中的（3）的情况；

  5. 规则2剪枝完毕后，数独还没有解决完毕，那我们只能通过枚举每一个位置的值，来一一尝试，直到找到最后的解决办法：

    （1）：我们在最开始创建了一个三维数组，存储每一个位置的可能值，初始情况下，每个位置的可能值都是1-9，但是经过上面两个规则的剪枝后，已经去除了很多；

    （2）：此时我们使用DFS深度优先搜索，尝试为每一个位置填值。经过上面的剪枝，每个位置的可能值的数量应该不一样了，而为了减少DFS搜索的次数，我们应该从可能值最少的位置开始搜索；

    （3）：遍历9宫格，找出还未填写值，且可能值最少的那个位置（可能有多个，找出第一个），尝试将他的第一个可能值填写在这个位置，然后再次调用规则1和规则2进行剪枝，剪枝完毕后，判断当前的九宫格中，是否有不和规则的地址，比如同一行出现两个一样的数。若没有不合法的地方，则再次进行一次（3），若有，表示这个位置不能填这个值，则从这个位置的可能值中再选择另外一个；

    （4）：一直使用步骤（3），直到所有的位置都确定，则表示成功解出数独，若有某个位置，它的任何一个可能值填上去，都不能得到最终结果，那数独就是无解的；

  6. 经过上面这些步骤，就能快速的解出数独，因为主要通过规则1，2进行剪枝，大大减少了枚举的次数，提升了效率；


所需计算

  1. 已知位置（i，j），则这个位置所在的3*3，其第一个点是（i/3×3 , j/3×3），i/3×3表示先作除法，去除了小数部分，再乘3，就是3的倍数了；
  2. 已知位置（i，j），如何计算这个位置属于第几个3×3，那就是（i/3×3 + j/3），每个3*3都占3行，且3列，i/3得到这个位置在第几个3行，j/3得到这个位置在第几个3列，每三行有三个3×3，所以i/3×3 + j/3就可以得到这个位置在第几个3×3；

代码

因为是为了完成python实验，所以代码是用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
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
# 此类用来表示搜索时，需要搜索的一个位置
# x，y为此位置的坐标，size为此位置的可能值的数量
class Node:
    def __init__(self, x, y, size):
        self.x = x
        self.y = y
        self.size = size

# 读取方式2，读取top95
def read_way2():
    # 从文件中读取初始数独
    value = [[0] * 10 for i in range(10)]
    # 读取文件2，3
    s = infile.readline();
    if s == '':
        return
    for i in range(9):
        for j in range(9):
            value[i][j] = int(s[i * 9 + j])
    return value

# 初始化函数
def init():
    value = read_way2()   # 读取top95
    # 初始化possibleValue，若当前位置有值，则其可能值就是这个值本身
    # 若没有值,则初始的可能值就是1-9
    possibleValue = [[[] for j in range(10)] for i in range(10)]
    for i in range(9):
        for j in range(9):
            if value[i][j] != 0:
                possibleValue[i][j] = [value[i][j]]
            else:
                possibleValue[i][j] = [1, 2, 3, 4, 5, 6, 7, 8, 9]

    return possibleValue

#####################################################################################################################

# 根据规则1进行剪枝
# 遍历所有的位置,找到已经确定的位置进行剪枝
def pruningByRule1(possibleValue):
    for i in range(9):
        for j in range(9):
            if len(possibleValue[i][j]) == 1:
                removeValueByRule1(i, j, possibleValue)    # 以当前位置为起点,移除重复的可能值


# 在规则1剪枝中,将同一区域中,已经确定的数移除
# 以(i,j)位置为起点,移除重复的可能值
def removeValueByRule1(i, j, possibleValue):
    # 与当前值在同一行或同一列的位置，可能值减去当前位置的值
    for k in range(9):
        # 从第i行中的可能值列表中,移除当前值
        confirmOneValueInRule1(i, k, possibleValue[i][j][0], possibleValue)
        # 从第i列中的可能值列表中,移除当前值
        confirmOneValueInRule1(k, j, possibleValue[i][j][0], possibleValue)

    # 与当前值在同3*3的位置，可能值减去当前位置的值
    for k in range(int(i / 3) * 3, int(i / 3) * 3 + 3):
        for l in range(int(j / 3) * 3, int(j / 3)* 3 + 3):
            confirmOneValueInRule1(k, l, possibleValue[i][j][0], possibleValue)

# 移除某个位置的可能值,并在移除后判断能否得到确定值
def confirmOneValueInRule1(i, j, num, possibleValue):
    if len(possibleValue[i][j]) == 1:
        return
    # 从当前位置的可能值中,移除已经确定的数
    if num in possibleValue[i][j]:
        possibleValue[i][j].remove(num)
    # 判断移除后,当前位置能否确定
    if len(possibleValue[i][j]) == 1:
        # 若当前位置确定，则以当前位置为基准进行移除操作
        removeValueByRule1(i, j, possibleValue)


###########################################################################################

# 根据规则2剪枝,判断同一个区域每个值可能出现的次数
# 若某个值可能出现的位置只有一个,表示这个值就在此位置
def pruningByRule2(possibleValue):
    # 统计第i行，数字j可能值出现了几次
    countX = [[0] * 10 for i in range(12)]
    # 统计第i列，数字j可能值出现了几次
    countY = [[0] * 10 for i in range(12)]
    # 统计第i个3*3，数字j可能值出现了几次
    countZ = [[0] * 10 for i in range(12)]

    # 统计各个区域可能值出现的次数
    for i in range(9):
        for j in range(9):
            for num in possibleValue[i][j]:
                countX[i][num] += 1
                countY[j][num] += 1
                countZ[i // 3 * 3 + j // 3][num] += 1

    # 判断哪些数字只出现了一次, 若只出现了一次的数字
    # 表示这个数字就是那个位置的答案
    for i in range(9):
        for j in range(1,10):
            # 若第i行数字j只出现了一次
            if countX[i][j] == 1:
                for k in range(9):  # 遍历第i行的每一列，判断这个唯一值出现在哪
                    confirmValueInRule2(i, k, j, possibleValue)

            # 若第i列数字j只出现了一次
            if countY[i][j] == 1:
                for k in range(9):  # 遍历第i列的每一列，判断这个唯一值出现在哪
                    confirmValueInRule2(k, i, j, possibleValue)

            # 若第i个3 * 3中，数字j的可能值只有一个
            if countZ[i][j] == 1:
                # 遍历第i个3*3的所有位置，判断这个唯一值出现在哪
                for k in range(i//3*3, i//3*3+3):
                    for l in range(i%3*3, i%3*3+3):
                        confirmValueInRule2(k, l, j, possibleValue)


# 判断当前位置是否包含某个数,包含则为此位置的答案
def confirmValueInRule2(i, j, singleNum, possibleValue):
    # 若当前位置已经确定值了, 直接返回
    if len(possibleValue[i][j]) ==1:
        return
    # 若当前位置包含唯一可能值，则这个位置的确定值就是它
    if singleNum in possibleValue[i][j]:
            possibleValue[i][j] = [singleNum]
            # 重新调用规则1
            removeValueByRule1(i, j, possibleValue)

###########################################################################################

# 递归搜索
def searchForPruning(node, possibleValue):
    # 若没有需要填值的点了，表示搜索结束，答案已出
    if node is None:
        return possibleValue

    # 获取当前位置的x，y坐标
    x = node[0]
    y = node[1]
    for num in possibleValue[x][y]:
        # 复制一份当前状态
        tempPossibleValue = copy.deepcopy(possibleValue)
        # 更新数据
        tempPossibleValue[x][y] = [num]
        # 调用规则1，2
        removeValueByRule1(x, y, tempPossibleValue)
        pruningByRule2(tempPossibleValue)

        # 调用规则1，2后，判断当前结果是否合法，若合法，则进行递归下一层
        if judge_result(tempPossibleValue):
            # 递归求解
            tempPossibleValue = searchForPruning(get_lowest_node(tempPossibleValue), tempPossibleValue)
            # 判断递归结果，若结果有返回值，则表示求解成功
            if tempPossibleValue is not None:
                return tempPossibleValue

# 获取当前可能值最小的位置
def get_lowest_node(possibleValue):
    minn = 100
    node = None
    for i in range(9):
        for j in range(9):
            # 若当前位置没有确定值，并且可能值的数量更少，则更新记录，
            if 1 < len(possibleValue[i][j]) < minn:
                minn = len(possibleValue[i][j])
                node = (i, j)
    return node


# 判断某个位置是否可以放某个值
def judge_result(possibleValue):
    # 标记某个数字是否出现
    countX = [[False] * 10 for i in range(12)]
    countY = [[False] * 10 for i in range(12)]
    countZ = [[False] * 10 for i in range(12)]

    # 统计各个区域可能值出现的次数
    for i in range(9):
        for j in range(9):
            if len(possibleValue[i][j]) == 1:
                # 若当前状态不合法，返回false
                if countX[i][possibleValue[i][j][0]] or countY[j][possibleValue[i][j][0]] or countZ[i // 3 * 3 + j // 3][possibleValue[i][j][0]]:
                    return False
                # 若合法，则标记已经确定的数字
                countX[i][possibleValue[i][j][0]] = True
                countY[j][possibleValue[i][j][0]] = True
                countZ[i // 3 * 3 + j // 3][possibleValue[i][j][0]] = True
    return True


# 判断某个位置是否可以放某个值
def judge_now_number(possibleValue, i, j, num):
    # 判断num在这一行和这一列是否被使用
    for k in range(9):
        if len(possibleValue[i][k]) == 1 and possibleValue[i][k][0] == num:
            return False
        if len(possibleValue[k][j]) == 1 and possibleValue[k][j][0] == num:
            return False
    # 判断num在这个3*3是否被使用
    for k in range(int(i / 3) * 3, int(i / 3) * 3 + 3):
        for l in range(int(j / 3) * 3, int(j / 3) * 3 + 3):
            if len(possibleValue[k][l]) == 1 and possibleValue[k][l][0] == num:
                return False
    return True

###########################################################################################


# 输出展示可能值列表
def display(possibleValue):
    for i in range(9):
        for j in range(9):
            print(possibleValue[i][j], end="---")
        print()
    print()

###########################################################################################

# 主函数
def main():
    start = time.time()
    c = 0
    # 主逻辑
    while True:
        # 调用初始化函数
        possibleValue = init()
        # 调用规则1剪枝
        pruningByRule1(possibleValue)
        # 调用规则2剪枝
        pruningByRule2(possibleValue)
        # display(possibleValue)

        possibleValue = searchForPruning(get_lowest_node(possibleValue), possibleValue)
        # 判断是否有解
        if possibleValue is not None:
            display(possibleValue)
        else:
            print("无解")

        if not judge_result(possibleValue):
            print("结果异常")

        c += 1
        if c >= 90:
            break
    end = time.time()
    print(end - start)


# 读取本地存储文件
infile = open("D:/top95.txt")
main()

扩展

  数独求解的算法，上面这种并不是最快的，还有一种叫做舞蹈链（Dancing Links）的算法，效率更高，有兴趣的可以了解一下；