- Published on
Micro Project | 填数独 Sudoku Solving
- Authors
- Name
- Jiaqi Wang(Ramis)
[最后更新 于 2024-05-19]
最近在刷题遇到了解决数独这个题，我顿时来了兴趣，这种小游戏怎么少得了我。 尝试写了一个代码，由于最终的结果还是比较理想的。所以在此把思路和代码块在这里分享。
核心的想法
深度优先搜索 DFS
首先，基本确定采用深度优先搜索，因为广度优先搜索不到最后一刻不知道这个数独对不对，从而会耗费大量的时间和内存。
标记进栈次序的队列 A queue tracking the search order
接下来，还需要考虑怎么搜索，盲目的搜索和枚举。考虑到每格虽然只有九种可能，但是考虑到空白的格子很多，不仅要挨个枚举还要考虑堆栈的深度，这些会引发爆炸的时空复杂度。因而，我考虑通过一个有序队列来控制搜索的顺序：
回想自己做数独的经历，我们往往从已知数字最多的行、列和九宫格里来先一步进行尝试。同样的道理，我们对求解的数独做预处理，对行、列、九宫格中缺少的数字个数按照由少到多排序。那么，在搜索时，就能大幅度减少不必要的搜索分支（控制搜索栈栈底底的可能性尽量少）。
哈希表 Hash Table
此外，每次尝试填数时，我们都需要查询该行、该列、该九宫格内没有重复元素，如果傻蠢蠢用循环进行扫描十分影响效率。那么就必须简单使用一下我们的好朋友 哈希表，来记录某行、某列、某九宫格内某元素是否出现过。这样每次尝试本身的复杂度降低到O(1)。
代码讲解
下面具体来讲解一下代码：
我们先看初始化的部分：
#Initiating:
#这三个数组分别对应某行(row)、某列(column)、某九宫格(square)中某元素出现过了没有,
r = [[0 for _ in range(10)] for _ in range(10)]
c = [[0 for _ in range(10)] for _ in range(10)]
s = [[0 for _ in range(10)] for _ in range(10)]
#我们用r[i][x]（x=1 to 9）来标记x是否已经出现在i行,c和s同理。
而r[i][0],c[i][0],和s[i][0]则用来记录该行中尚未填写数字的格数，并且将其坐标存在从r[i][10],c[i][10],s[i][10]以后的格子里。注意，这里的坐标对于行和列来说是单一的常数，而对于九宫格来说，则采用当前下标mod 3+1的元组来存储。
visited = [[False for _ in range(10)] for _ in range(10)]
for i,row in enumerate(board):
for j,x in enumerate(row):
if x!=".":
r[i+1][int(x)]=1
c[j+1][int(x)]=1
s[(i//3)*3+(j//3)+1][int(x)]=1
if x==".":
r[i+1][0]+=1
c[j+1][0]+=1
s[(i//3)*3+(j//3)+1][0]+=1
r[i+1].append(j+1)
c[j+1].append(i+1)
s[(i//3)*3+(j//3)+1].append((i%3+1,j%3+1))
#接着，我们将r[i][0],c[i][0],s[i][0]的值以及其对应的索引值汇入一个队列中。然后我们对该队列的第一个值，也就是未填数字的多少进行从小到大排序，获得队列q。
q=[]
for i in range(1,10):
scode="r"+str(i)
q.append((r[i][0],scode))
for i in range(1,10):
scode="c"+str(i)
q.append((c[i][0],scode))
for i in range(1,10):
scode="s"+str(i)
q.append((s[i][0],scode))
q=sorted(q)
#但这个q并没有具体到哪个坐标，因此还要让对应的坐标进队，因此我们建立新数组position queue（posque）。（位于同一行的坐标不再进行排序而是直接按照大小依次进队）。注意，这里需要对坐标进行判重，保证其不会二次进入队列。
posque=[]
for x in q:
nums,sortcode=x #我们先取出上一个队列中的元组，sortcode用来判断当前值代表的行、列或九宫格。nums是改行中的空位数。
for j in range(0,nums): #用循环让所有空格入队。
if sortcode[0]=="r": #这里要根据首字母判断当前是行、列还是九宫格再计算坐标。
pos_x=int(sortcode[1])
pos_y=(r[int(sortcode[1])][j+10]) #如果是行，则x坐标是标签内的值，y坐标是当前行坐标表索引10以后所存的列坐标。
elif sortcode[0]=="c":
pos_x=(c[int(sortcode[1])][j+10])
pos_y=int(sortcode[1]) #同理，如果是列，则y坐标采用标签内的值，x坐标是所在列坐标表索引10以后所存的的行坐标。
elif sortcode[0]=="s":
pos_x,pos_y=(s[int(sortcode[1])][j+10]) #如果是九宫格的话要麻烦一些，我们先把空格所在的九宫格内部坐标取出来
pos_x=pos_x+((int(sortcode[1])-1)//3)*3 #然后我们将其通过九宫格的标签值对应到9*9的数独格中。
pos_y=pos_y+((int(sortcode[1])-1)%3)*3
if not visited[pos_x][pos_y]: #注意，这里在x y坐标入队前需要判重，因为一个空格势必是会出现三次的。
posque.append((pos_x,pos_y))
visited[pos_x][pos_y]=True
#这样我们就完成了初始化的过程
对于以下一个数独，上述所有涉及到的变量在初始化后的状态应该如下：
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"]]
#row：
r= [ [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[6, 0, 0, 1, 0, 1, 0, 1, 0, 0, 3, 4, 6, 7, 8, 9],
[5, 1, 0, 0, 0, 1, 1, 0, 0, 1, 2, 3, 7, 8, 9],
[6, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 4, 5, 6, 7, 9],
[6, 0, 0, 1, 0, 0, 1, 0, 1, 0, 2, 3, 4, 6, 7, 8],
[5, 1, 0, 1, 1, 0, 0, 0, 1, 0, 2, 3, 5, 7, 8],
[6, 0, 1, 0, 0, 0, 1, 1, 0, 0, 2, 3, 4, 6, 7, 8],
[6, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 3, 4, 5, 6, 9],
[5, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 2, 3, 7, 8],
[6, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 3, 4, 6, 7]]
#由于r[0]所在行是空行，以之后的第一行（r[1]为例，第一位r[1][0]说明第一行有六个空格，而从第10位开始记录空格所在行：分别是第3, 4, 6, 7, 8, 9列。
#column是一样的道理
c= [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[4, 0, 0, 0, 1, 1, 1, 1, 1, 0, 3, 7, 8, 9],
[6, 0, 0, 1, 0, 0, 1, 0, 0, 1, 2, 4, 5, 6, 8, 9],
[8, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 2, 4, 5, 6, 7, 8, 9],
[6, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 3, 4, 6, 7, 9],
[3, 1, 1, 0, 0, 0, 1, 1, 1, 1, 3, 5, 7],
[6, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 3, 4, 6, 7, 9],
[8, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 8, 9],
[6, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 2, 4, 5, 6, 8],
[4, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 2, 3, 7]]
#Square记录九宫格方法也类似，只是坐标记录中采用元组，此处坐标用1，2，3来表示其在九宫格中的位置。
九宫格序号：
|11 12 13 14 15 16 17 18 19| |.........|.........|.........|
|21 22 23 24 25 26 27 28 29| |... 1 ...|... 2 ...|... 3 ...|
|31 32 33 34 35 36 37 38 39| |_________|_________|_________|
|41 42 43 44 45 46 47 48 49| |.........|.........|.........| |11 12 13|
|51 52 53 54 55 56 57 58 59| --> |... 4 ...|... 5 ...|... 6 ...| ->|21 22 23|
|61 62 63 64 65 66 67 68 69| |_________|_________|_________| |31 32 33|
|71 72 73 74 75 76 77 78 79| |.........|.........|.........|
|81 82 83 84 85 86 87 88 89| |... 7 ...|... 8 ...|... 9 ...|
|91 92 93 94 95 96 97 98 99| |_________|_________|_________|
九宫格序号 九宫格内坐标
比如，我们将44坐标映射到s[5],(1,1)的位置
s= [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[4, 0, 0, 1, 0, 1, 1, 0, 1, 1, (1, 3), (2, 2), (2, 3), (3, 1)],
[5, 1, 0, 0, 0, 1, 0, 1, 0, 1, (1, 1), (1, 3), (3, 1), (3, 2), (3, 3)],
[8, 0, 0, 0, 0, 0, 1, 0, 0, 0, (1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 3)],
[6, 0, 0, 0, 1, 0, 0, 1, 1, 0, (1, 2), (1, 3), (2, 2), (2, 3), (3, 2), (3, 3)],
[5, 0, 1, 1, 0, 0, 1, 0, 1, 0, (1, 1), (1, 3), (2, 2), (3, 1), (3, 3)],
[6, 1, 0, 1, 0, 0, 1, 0, 0, 0, (1, 1), (1, 2), (2, 1), (2, 2), (3, 1), (3, 2)],
[8, 0, 0, 0, 0, 0, 1, 0, 0, 0, (1, 1), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)],
[5, 1, 0, 0, 1, 0, 0, 0, 1, 1, (1, 1), (1, 2), (1, 3), (3, 1), (3, 3)], [4, 0, 1, 0, 0, 1, 0, 1, 1, 1, (1, 3), (2, 1), (2, 2), (3, 1)]]
排序后的队列q=
[(3, 'c5'), (4, 'c1'), (4, 'c9'), (4, 's1'), (4, 's9'), (5, 'r2'), (5, 'r5'), (5, 'r8'), (5, 's2'), (5, 's5'), (5, 's8'), (6, 'c2'), (6, 'c4'), (6, 'c6'), (6, 'c8'), (6, 'r1'), (6, 'r3'), (6, 'r4'), (6, 'r6'), (6, 'r7'), (6, 'r9'), (6, 's4'), (6, 's6'), (8, 'c3'), (8, 'c7'), (8, 's3'), (8, 's7')]
依次填数字的队列 posque=
[(3, 5), (5, 5), (7, 5), (3, 1), (7, 1), (8, 1), (9, 1), (1, 9), (2, 9), (3, 9), (7, 9), (1, 3), (2, 2), (2, 3), (8, 7), (8, 8), (9, 7), (2, 7), (2, 8), (5, 2), (5, 3), (5, 7), (5, 8), (8, 2), (8, 3), (1, 4), (1, 6), (3, 4), (3, 6), (4, 4), (4, 6), (6, 4), (6, 6), (7, 4), (7, 6), (9, 4), (9, 6), (4, 2), (6, 2), (9, 2), (1, 8), (4, 8), (6, 8), (1, 7), (3, 7), (4, 3), (4, 7), (6, 3), (6, 7), (7, 3), (9, 3)]
接下来就是搜索的过程。
def solveSudoku(self, board):
def Trysudoku(priority,rv,cv,sv,current_board): #此处priority是有待查询的空格队列，rv,cv,sv是当前尝试状态中对应的行、列、九宫格查询哈希表，current_board是当前棋盘。
if len(priority)==1: #若队列中仅剩一个元素，也就是数独内只剩一个空格，那么我们知道这是该搜索路径的最后一层，关系到是否成功完成数独以及退出搜索。
xi,yi=priority[0] #取出空格位置
for t in range(1,10): #1-9进行尝试
sindex=((xi-1)//3)*3+(yi-1)//3+1 #这里的sindex是将当前空格的坐标x y映射到所在的九宫格序号
if (rv[xi][t]==0) and (cv[yi][t]==0) and(sv[sindex][t]==0): #若在行列九宫格中该尝试数字都未出现：那么我们将t填入current board，打印完成的数独，然后返回True。
current_board[xi-1][yi-1]=str(t)
print(current_board)
return(True)
else: #否则，也就是待查询队列不止一个元素，那我们不仅要进行尝试，在尝试后还要继续搜索下一个元素。
xi,yi=priority[0]
for t in range(1,10):
sindex=((xi-1)//3)*3+(yi-1)//3+1
if (rv[xi][t]==0) and (cv[yi][t]==0) and (sv[sindex][t]==0): #若该数字是可填的，我们填入后修改相关行、列、九宫格的查询表
current_board[xi-1][yi-1]=str(t)
rv[xi][t]=1
cv[yi][t]=1
sv[sindex][t]=1
if Trysudoku(priority[1:],rv,cv,sv,current_board):return(True) #在递归调用搜索队列之后的元素，若沿着该路径最终查询成果，那么再向上层返回true。如果失败（没有return True结束搜索），我们就要将所有查询数组和数独盘还原到尝试前的状态，接着尝试填入其他数或返回上一层。
rv[xi][t]=0
cv[yi][t]=0
sv[sindex][t]=0
current_board[xi-1][yi-1]='.'
这里是主程序中的递归调用，board是代填数独：
Trysudoku(posque,r,c,s,board)
最后发图，说明这样的优化还是挺有效率的。
（合理怀疑本人为了发这张图而写了一篇博客，o(￣▽￣)ブ）
这个星期三下了班熬夜写代码调试这个东西，还算写成了。 到头来其实不难，感觉九宫格的坐标应该可以更简单地存储，只是感觉这样写比较 "优美"。 周末还有一整天。 整个这半个月过得很充实。 遁走。
-鹅仔 2024/5/19 1：08