Lynsdata

lyndon's blog

数独的暴力回溯解法和Python-GUI

发表于 更新于 分类于 | 3.4k 字 | ≈ 14 分钟

数独起源于18世纪初瑞士数学家欧拉等人研究的拉丁方阵，20世纪70年代，经过美国及日本学者的推广和改良，定名为数独(Sudoku)，大致的意思是“独个的数字”或“只出现一次的数字”。
标准的九宫格数独包含9×9个格子，且每3×3的区域组成一宫，数独的规则要求在空出来的格子里填如1~9的数字，要满足每行、每列和每宫内的数字都不重复，也就是行、列及宫里都是由不重复的1~9构成。数独还包含了一些6×6、不规则九宫等个性数独，本篇仅讨论标准九宫格数独的情况。

各种数独

手动解的技巧有唯余解法、基础排除法、区块排除法、数对唯余法等，进阶的有唯一矩形法、数对占位法、双分支匹配等。
【数独示例及手动解法概览】

(数独解法概览来自标准数独）
用电脑解最通用的还是穷举整个解空间，根据数独规则进行剪枝和回溯。效率和递归深度、需要缓存的中间过程有关，递归深度主要由挖空的个数决定。最简单的穷举算法是对每个单元格都用1~9分别尝试，满足条件继续尝试下一个挖空的格，直到所有单元格都填了合适的数字，且检查符合数独规则就算找到一个解。唯一解要求当前盘面有且只有这一个解。

进一步的做法是为每个挖空的格子维护一个候选数列表，用这个列表中的值进行试数，出现矛盾就回溯，很暴力但其实挺有效的。更高级一点的舞蹈链法及利用模拟退火等方法，也还是离不开试数和回溯的思路。因此下面主要实现的是基于候选数的回溯解法。

首先数独中的数值我们可以用一个一维长度为81的数组表示，也可以用二维9×9的数组表示，下面采用9×9的数组表示，例如一个数独，其盘面用二维数组表示如下：

【图】

回溯的思路是：从第一个挖空的单元格开始，根据其相关20格（本行、本列及所在宫内的单元格）生成候选数列表lst，lst的生成直接地利用了唯余法进行排除，对列表lst中的值进行向下尝试，尝试下一个挖空的单元格，当不满足数独规则时，回退到上一个挖空的单元格。

写成代码如下：

【图】

再把getPrem(x,y,board) 及cheackNotSame(x,y,v,board)实现后，就可以变成完整的代码了，

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
class sovSudoku:  #求解数独
    def __init__(self,board=[]):
        self._b=board.copy()  #直接写=board会直接修改传进来的列表
    def trysxy(self,x,y): #主循环，尝试x，y处的解答
        if self._b[x][y]==0: #不等于0的情况在调用外处理
            pv=self.getPrem(x,y)
            #for v in range(1,10): #从1到9尝试
            for v in pv:
                self._t+=1 #递归次数+1
                if self.checkNotSame(x,y,v):# 符合 行列宫均满足v符合条件 的
                    self._b[x][y]=v
                    nx,ny=self.getNext(x,y) #得到下一个0值格
                    if nx==-1: #没有下一个0格了；and ny==-1可以写但没必要
                        return True
                    else:
                        _end=self.trysxy(nx,ny) #向下尝试,递归
                        if not _end:
                            self._b[x][y]=0 #回溯，继续for v循环
                            #只需要改x，y处的值，不改其他值
                        else:
                            return True
	
    def checkNotSame(self,x,y,val):#检查每行,列及宫内是否有和b[x,y]相同项
        for row_item in self._b[x]: #第x行
            if row_item==val:
                return False
        for rows in self._b:#y所在列
            if rows[y]==val:
                return False
        ax=x//3*3 #把0~3中的值映射到[0,3]
        ab=y//3*3
        for r in range(ax,ax+3):
            for c in range(ab,ab+3):#注意r==x & c==y的情况下，其实没必要，val不会是0
                if self._b[r][c]==val:
                    return False
        return True
    def getNext(self,x,y): #得到下一个未填项,从x,y往下数，值等于0就返回新下标
        for ny in range(y+1,9): #下标是[0,8]
            if self._b[x][ny]==0:
                return (x,ny)
        for row in range(x+1,9):
            for ny in range(0,9):
                if self._b[row][ny]==0:
                    return (row,ny)
        return (-1,-1) #不存在下一个未填项的情况
    def getPrem(self,x,y): #得到x，y处可以填的值
        prem=[]
        rows=list(self._b[x])
        rows.extend([self._b[i][y] for i in range(9)])
        cols=set(rows)
        for i in range(1,10):
            if i not in cols:
                prem.append(i)
        return prem
    def solve(self):
        #x,y=(0,0) if self._b[0][0]==0 else self.getNext(0,0)
        if self._b[0][0]==0:#更容易理解的写法
            self.trysxy(0,0)
        else:
            x,y=self.getNext(0,0)
            self.trysxy(x,y)
			#以下为辅助代码
	def updateSudo(self,cb): #传入一个数独盘面
        if len(cb)==9 and len(cb[0])==9:
            self._b=cb
        else:
            print('files size not shape',len(cb),len(cb[0]))
    def __str__(self): #print(sovSudoku)
        return '{0}{1}{2}'.format('[',',\n'.join([str(i) for i in self._b]),']')

对于上面的最难数独，在本机上求解效果如下，耗时在秒级，回溯性能也不是很差。
【图】

网上再找几个数独进行测试，各自耗时如下：

【图】

在leetcode上有两道数独相关的题目，第37题就是根据输入的数独（用9×9的二维数组表示）求结果。它是用'.'代表挖空，把上面的代码改一下，提交运行的效果如下：

【图】

运行时间在秒级以下，因为回溯会有多次栈调用，内存花费在10多MB。大于平常的一些练习题。

第36题是检查当前盘面的合法性，不考虑该数独能否求解，只需要根据数独规则判断是否满足数独条件，将以上代码修改后提交的结果如下：

【图】

数独游戏GUI

有了上面的检查数独是否合法以及解数独的代码后，再加上生成数独的代码就可以写一个小游戏训练自己了。81个单元格，假设每次挖掉n 个数字形成一个数独题目，根据排列组合的算法，一共有C(81,n)种挖法。要保证数独有唯一解，则至少要保留17个提示数，也就是说n 最多只能是81-17=64。n取1,2这种数也没什么好玩的，只挖一两个空太好解了，因此n应该有个合理的最小值，如果每行挖两个空，那就是18个空，因此n可以取[18,64]，从量级上我们就能看出，就算我们每天接触1万个数独，穷尽一生接触到的数独题目数量也只占冰山一角，因此不需要担心会刷到重复的数独，概率太低。直接随机某个位置随机填入一个数字再随机其他位置来生成数独效率并不高，比较合理的做法是程序内部有几个完整的数独，通过数字置换和随机挖空来产生新的数独。

考虑数独的特点，如果我们有一个数组[6,8,5,1,9,4,3,2,7]，表示将数独中的数字1变成数字6，把2变成8，以此类推……，类似凯撒加密的做法。由数独的特点可以推出新生成的数独也是符合规则的。

挖空操作就是随机挖去n处的值，再验证是否有唯一解，就可以生成一个数独题目了。

GUI程序的流程还是遵从：

导入tk库，创建主窗体->添加控件->处理交互->进入主事件循环

最后实现的GUI如下：

【几个盘面以及交互，初始数独，填写验证，电脑解】

各按钮交互简介：

  • 生成数独： 随机生成一个数独；
  • 验证答案： 没填完的情况下，根据当前所填进行验证；填完了，不满足条件则提示，满足说明解答正确，进行弹窗；
  • 电脑解：电脑对当前基础盘面进行计算，把值渲染到数独上（可以对字体、颜色进行进一步个性化）；
  • 清空：把所有值都清空，方便用户输入一个盘面。

部分代码如下，继续用内置的tkinter库实现。

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
root=tk.Tk()
root.geometry('310x350+400+100') #大小和位置
root.title('Sudoku')
btnlst=[] # 每一个输入框  全局变量
evs=[] #和btnlst对应的变量列表 仅get，set操作

def initOneSudo(s0): #根据初始数独和挖空个数，生成一个一维的数独列表
    s1=xyTo81(s0) #s0是二维的
    u=randint(0,8)
    if u!=0:s1=resetsd(s1,u) #对s1中的数进行“替换加密”
    m=randint(18,41) #挖空个数。目前允许多解
    wlst=[] #挖空位置 
    while len(wlst)<m:
        i=randint(0,80)
        while i in wlst:
            i+=2 #或者这里继续用随机数
            if i>80:
                i-=30
        s1[i]=0
        wlst.append(i)
    return s1


def initSudo(s1,evs):
    sk1=xyTo81(s1)
    if evs==[]:
        for j in range(0,81):
            evs.append(tk.IntVar(root,sk1[j]))
    else:
        for j in range(0,81):
            evs[j].set(sk1[j])
    return evs

def isValidSudoku(board):
    if board[0][0]!=0:
        return validCheck(0,0,board)
    else:
        nx,ny=getNext(0,0,board)
        if nx==-1:
            return -1
        return validCheck(nx,ny,board)
def validCheck(x,y,b):#检查数独是否合法
    v=b[x][y]
    for r in range(0,9):
        if r!=x:
            if b[r][y]==v:
                return False
        if r!=y:
            if b[x][r]==v:
                return False
    ax=x//3*3
    ab=y//3*3
    for r in range(ax,ax+3):
        for c in range(ab,ab+3):
            if b[r][c]==v and r!=x and c!=y:
                return False
    nx,ny=getNext(x,y,b)
    if nx==-1:
        return True
    return validCheck(nx,ny,b)

### 主函数   s0:内置的基础数独
s1=initOneSudo(s0)  #81
s1=nighty2xy(s1,n=9)

s1cp=s1.copy()
s2=zeroToNAstr(s1,0) #9*9
evs=initSudo(s2,[])

i=0 #用81个输入框表示每个数独单元格
for r in range(9):
    for c in range(9):
        if r>2 and r<6 and c>2 and c<6:
            btnlst.append(tk.Entry(root,textvariable=evs[i],justify='center'))
        elif r>2 and r<6:
            btnlst.append(tk.Entry(root,textvariable=evs[i],justify='center'))
            btnlst[i]['background']='#AFEEEE'
        elif c>2 and c<6:
            btnlst.append(tk.Entry(root,textvariable=evs[i],justify='center'))
            btnlst[i]['background']='#AFEEEE'
        else:
            btnlst.append(tk.Entry(root,textvariable=evs[i],justify='center'))
        btnlst[i].place(x=5+c*30,y=0+r*30,width=30,height=30)
        i+=1

def btnClick(x): #按钮点击的回调函数
    global evs,s1,s1cp
    if x=='c': #清空
        for i in range(81):
            evs[i].set('')
    elif x=='n':
        s1=initOneSudo(s0) #81
        s1cp=nighty2xy(s1,n=9)
        for k1 in range(81):
            if s1[k1]==0:
                evs[k1].set('')
            else:
                evs[k1].set(s1[k1])
    elif x=='m': #电脑解；这里涉及用户输入，确实需要的约束判断挺多的
        s5,msg=getSudo(evs,0) #9*9
        if msg[0]!='':
            messagebox.showinfo('提示',msg[0])
        elif msg[1]!='': #有空值来验证
            s6=s5.copy()
            isvs=isValidSudoku(s6)
            if isvs==-1:
                messagebox.showinfo('提示','当前盘面为空，请先手动输入一个合法盘面或点生成数独')
            elif isvs:
                ss=sovSudoku(s1cp)
                ss.solve()
                s3=ss.getSudoku() #[[1,2],[3,4]]
                s4=xyTo81(s3)
                for k1 in range(81): #从s3写入盘面
                    if s4[k1]==0:
                        evs[k1].set('')
                    else:
                        evs[k1].set(s4[k1])
            else:
                messagebox.showinfo('提示','当前盘面包含不满足数独条件的值，请检查')
        else:#填完了的情况
            s6=s5.copy()
            isvs=isValidSudoku(s6)
            if isvs==-1:
                messagebox.showinfo('提示','当前盘面为空，请先手动输入一个合法盘面或点生成数独')
            elif isvs:
                messagebox.showinfo('恭喜','恭喜，当前数独已解答正确！')
            else:
                messagebox.showinfo('提示','当前盘面包含不满足数独条件的值，请检查')
    elif x=='s': #验证盘面
        s5,msg=getSudo(evs,0) #9*9
        if msg[0]!='':
            messagebox.showinfo('提示',msg[0])
        elif msg[1]!='': #有空值来验证
            s6=s5.copy()
            isvs=isValidSudoku(s6)
            if isvs==-1:messagebox.showinfo('提示','当前盘面为空，请先手动输入一个合法盘面或点生成数独')
            elif isvs:messagebox.showinfo('提示','当前盘面满足数独条件,请继续作答或选择电脑解答')
            else:messagebox.showinfo('提示','当前盘面包含不满足数独条件的值，请检查')
        else:#填完了的情况
            s6=s5.copy()
            isvs=isValidSudoku(s6)
            if isvs:messagebox.showinfo('恭喜','恭喜，当前数独已解答正确！')
            else:messagebox.showinfo('提示','当前盘面包含不满足数独条件的值，请检查')

#随机生成 电脑解 验证答案
ranInitBtn=tk.Button(root,text='生成数独',command=lambda x='n':btnClick(x)) #new one sudo
ranInitBtn.place(x=5,y=310,width=60,height=30)
#……
root.mainloop()

打包GUI为exe文件

还是用pyinstaller把程序变成exe可执行文件，大小是8点多M，作为Python导出的exe文件，这个大小是有优势的，结果如下：

【内存大小，图】

本文从解数独的手动解法引入，讲到解数独常用的回溯法，并且按照思路实现回溯代码，通过这一思路去解两个LeetCode题，为了可玩性增加随机生成一个数独的代码，并把以上功能整合为一个GUI程序，用于平时的数独训练，并且把这一GUI脚本打包为一个exe文件，在Windows系统下使用。