數(shù)獨(dú)起源于18世紀(jì)初瑞士數(shù)學(xué)家歐拉等人研究的拉丁方陣，20世紀(jì)70年代，經(jīng)過美國(guó)及日本學(xué)者的推廣和改良，定名為數(shù)獨(dú)(Sudoku)，大致的意思是“獨(dú)個(gè)的數(shù)字”或“只出現(xiàn)一次的數(shù)字”。 標(biāo)準(zhǔn)的九宮格數(shù)獨(dú)包含9×9個(gè)格子，且每3×3的區(qū)域組成一宮，數(shù)獨(dú)的規(guī)則要求在空出來的格子里填如1～9的數(shù)字，要滿足每行、每列和每宮內(nèi)的數(shù)字都不重復(fù)，也就是行、列及宮里都是由不重復(fù)的1~9構(gòu)成。數(shù)獨(dú)還包含了一些6×6、不規(guī)則九宮等個(gè)性數(shù)獨(dú)，本篇僅討論標(biāo)準(zhǔn)九宮格數(shù)獨(dú)的情況。
手動(dòng)解的技巧有唯余解法、基礎(chǔ)排除法、區(qū)塊排除法、數(shù)對(duì)唯余法等，進(jìn)階的有唯一矩形法、數(shù)對(duì)占位法、雙分支匹配等。
用電腦解最通用的還是窮舉整個(gè)解空間，根據(jù)數(shù)獨(dú)規(guī)則進(jìn)行剪枝和回溯。效率和遞歸深度、需要緩存的中間過程有關(guān)，遞歸深度主要由挖空的個(gè)數(shù)決定。最簡(jiǎn)單的窮舉算法是對(duì)每個(gè)單元格都用1~9分別嘗試，滿足條件繼續(xù)嘗試下一個(gè)挖空的格，直到所有單元格都填了合適的數(shù)字，且檢查符合數(shù)獨(dú)規(guī)則就算找到一個(gè)解。唯一解要求當(dāng)前盤面有且只有這一個(gè)解。
進(jìn)一步的做法是為每個(gè)挖空的格子維護(hù)一個(gè)候選數(shù)列表，用這個(gè)列表中的值進(jìn)行試數(shù)，出現(xiàn)矛盾就回溯，很暴力但其實(shí)挺有效的。更高級(jí)一點(diǎn)的舞蹈鏈法及利用模擬退火等方法，也還是離不開試數(shù)和回溯的思路。因此下面主要實(shí)現(xiàn)的是基于候選數(shù)的回溯解法。
首先數(shù)獨(dú)中的數(shù)值我們可以用一個(gè)一維長(zhǎng)度為81的數(shù)組表示，也可以用二維9×9的數(shù)組表示，下面采用9×9的數(shù)組表示，例如一個(gè)數(shù)獨(dú)，其盤面用二維數(shù)組表示如下：
回溯的思路是：從第一個(gè)挖空的單元格開始，根據(jù)其相關(guān)20格（本行、本列及所在宮內(nèi)的單元格）生成候選數(shù)列表lst，lst的生成直接地利用了唯余法進(jìn)行排除，對(duì)列表lst中的值進(jìn)行向下嘗試，嘗試下一個(gè)挖空的單元格，當(dāng)不滿足數(shù)獨(dú)規(guī)則時(shí)，回退到上一個(gè)挖空的單元格。
寫成代碼如下：
再把getPrem(x,y,board)及cheackNotSame(x,y,v,board)實(shí)現(xiàn)后，就可以變成完整的代碼了，
class sovSudoku: #求解數(shù)獨(dú)
def __init__(self,board=[]):
self._b=board.copy() #直接寫=board會(huì)直接修改傳進(jìn)來的列表
def trysxy(self,x,y): #主循環(huán)，嘗試x，y處的解答
if self._b[x][y]==0: #不等于0的情況在調(diào)用外處理
pv=self.getPrem(x,y)
#for v in range(1,10): #從1到9嘗試
for v in pv:
self._t+=1 #遞歸次數(shù)+1
if self.checkNotSame(x,y,v):# 符合 行列宮均滿足v符合條件 的
self._b[x][y]=v
nx,ny=self.getNext(x,y) #得到下一個(gè)0值格
if nx==-1: #沒有下一個(gè)0格了；and ny==-1可以寫但沒必要
return True
else:
_end=self.trysxy(nx,ny) #向下嘗試,遞歸
if not _end:
self._b[x][y]=0 #回溯，繼續(xù)for v循環(huán)
#只需要改x，y處的值，不改其他值
else:
return True
def checkNotSame(self,x,y,val):#檢查每行,列及宮內(nèi)是否有和b[x,y]相同項(xiàng)
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的情況下，其實(shí)沒必要，val不會(huì)是0
if self._b[r][c]==val:
return False
return True
def getNext(self,x,y): #得到下一個(gè)未填項(xiàng),從x,y往下數(shù)，值等于0就返回新下標(biāo)
for ny in range(y+1,9): #下標(biāo)是[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) #不存在下一個(gè)未填項(xiàng)的情況
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): #傳入一個(gè)數(shù)獨(dú)盤面
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]),']')
對(duì)于上面的最難數(shù)獨(dú)，在本機(jī)上求解效果如下，耗時(shí)在秒級(jí)，回溯性能也不是很差。
網(wǎng)上再找?guī)讉€(gè)數(shù)獨(dú)進(jìn)行測(cè)試，各自耗時(shí)如下：
在leetcode上有兩道數(shù)獨(dú)相關(guān)的題目，第37題就是根據(jù)輸入的數(shù)獨(dú)（用9×9的二維數(shù)組表示）求結(jié)果。它是用'.'代表挖空，把上面的代碼改一下，提交運(yùn)行的效果如下：
運(yùn)行時(shí)間在秒級(jí)以下，因?yàn)榛厮輹?huì)有多次棧調(diào)用，內(nèi)存花費(fèi)在10多MB。大于平常的一些練習(xí)題。
第36題是檢查當(dāng)前盤面的合法性，不考慮該數(shù)獨(dú)能否求解，只需要根據(jù)數(shù)獨(dú)規(guī)則判斷是否滿足數(shù)獨(dú)條件，將以上代碼修改后提交的結(jié)果如下：
數(shù)獨(dú)游戲GUI
有了上面的檢查數(shù)獨(dú)是否合法以及解數(shù)獨(dú)的代碼后，再加上生成數(shù)獨(dú)的代碼就可以寫一個(gè)小游戲訓(xùn)練自己了。81個(gè)單元格，假設(shè)每次挖掉n 個(gè)數(shù)字形成一個(gè)數(shù)獨(dú)題目，根據(jù)排列組合的算法，一共有C(81,n)種挖法。要保證數(shù)獨(dú)有唯一解，則至少要保留17個(gè)提示數(shù)，也就是說n 最多只能是81-17=64。n取1,2這種數(shù)也沒什么好玩的，只挖一兩個(gè)空太好解了，因此n應(yīng)該有個(gè)合理的最小值，如果每行挖兩個(gè)空，那就是18個(gè)空，因此n可以取[18,64]，從量級(jí)上我們就能看出，就算我們每天接觸1萬個(gè)數(shù)獨(dú)，窮盡一生接觸到的數(shù)獨(dú)題目數(shù)量也只占冰山一角，因此不需要擔(dān)心會(huì)刷到重復(fù)的數(shù)獨(dú)，概率太低。直接隨機(jī)某個(gè)位置隨機(jī)填入一個(gè)數(shù)字再隨機(jī)其他位置來生成數(shù)獨(dú)效率并不高，比較合理的做法是程序內(nèi)部有幾個(gè)完整的數(shù)獨(dú)，通過數(shù)字置換和隨機(jī)挖空來產(chǎn)生新的數(shù)獨(dú)。
考慮數(shù)獨(dú)的特點(diǎn)，如果我們有一個(gè)數(shù)組[6,8,5,1,9,4,3,2,7]，表示將數(shù)獨(dú)中的數(shù)字1變成數(shù)字6，把2變成8，以此類推……，類似凱撒加密的做法。由數(shù)獨(dú)的特點(diǎn)可以推出新生成的數(shù)獨(dú)也是符合規(guī)則的。
挖空操作就是隨機(jī)挖去n處的值，再驗(yàn)證是否有唯一解，就可以生成一個(gè)數(shù)獨(dú)題目了。
GUI程序的流程還是遵從：
導(dǎo)入tk庫，創(chuàng)建主窗體->添加控件->處理交互->進(jìn)入主事件循環(huán)
最后實(shí)現(xiàn)的GUI如下：
各按鈕交互簡(jiǎn)介：
生成數(shù)獨(dú)： 隨機(jī)生成一個(gè)數(shù)獨(dú)；
驗(yàn)證答案： 沒填完的情況下，根據(jù)當(dāng)前所填進(jìn)行驗(yàn)證；填完了，不滿足條件則提示，滿足說明解答正確，進(jìn)行彈窗；
電腦解：電腦對(duì)當(dāng)前基礎(chǔ)盤面進(jìn)行計(jì)算，把值渲染到數(shù)獨(dú)上（可以對(duì)字體、顏色進(jìn)行進(jìn)一步個(gè)性化）；
清空：把所有值都清空，方便用戶輸入一個(gè)盤面。
代碼如下，繼續(xù)用內(nèi)置的tkinter庫實(shí)現(xiàn)。
root=tk.Tk()
root.geometry('310x350+400+100') #大小和位置
root.title('Sudoku')
btnlst=[] # 每一個(gè)輸入框 全局變量
evs=[] #和btnlst對(duì)應(yīng)的變量列表 僅get，set操作
def initOneSudo(s0): #根據(jù)初始數(shù)獨(dú)和挖空個(gè)數(shù)，生成一個(gè)一維的數(shù)獨(dú)列表
s1=xyTo81(s0) #s0是二維的
u=randint(0,8)
if u!=0:s1=resetsd(s1,u) #對(duì)s1中的數(shù)進(jìn)行“替換加密”
m=randint(18,41) #挖空個(gè)數(shù)。目前允許多解
wlst=[] #挖空位置
while len(wlst)<m:
i=randint(0,80)
while i in wlst:
i+=2 #或者這里繼續(xù)用隨機(jī)數(shù)
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):#檢查數(shù)獨(dú)是否合法
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)
### 主函數(shù) s0:內(nèi)置的基礎(chǔ)數(shù)獨(dú)
s1=initOneSudo(s0) #81
s1=nighty2xy(s1,n=9)
s1cp=s1.copy()
s2=zeroToNAstr(s1,0) #9*9
evs=initSudo(s2,[])
i=0 #用81個(gè)輸入框表示每個(gè)數(shù)獨(dú)單元格
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): #按鈕點(diǎn)擊的回調(diào)函數(shù)
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': #電腦解；這里涉及用戶輸入，確實(shí)需要的約束判斷挺多的
s5,msg=getSudo(evs,0) #9*9
if msg[0]!='':
messagebox.showinfo('提示',msg[0])
elif msg[1]!='': #有空值來驗(yàn)證
s6=s5.copy()
isvs=isValidSudoku(s6)
if isvs==-1:
messagebox.showinfo('提示','當(dāng)前盤面為空，請(qǐng)先手動(dòng)輸入一個(gè)合法盤面或點(diǎn)生成數(shù)獨(dú)')
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('提示','當(dāng)前盤面包含不滿足數(shù)獨(dú)條件的值，請(qǐng)檢查')
else:#填完了的情況
s6=s5.copy()
isvs=isValidSudoku(s6)
if isvs==-1:
messagebox.showinfo('提示','當(dāng)前盤面為空，請(qǐng)先手動(dòng)輸入一個(gè)合法盤面或點(diǎn)生成數(shù)獨(dú)')
elif isvs:
messagebox.showinfo('恭喜','恭喜，當(dāng)前數(shù)獨(dú)已解答正確！')
else:
messagebox.showinfo('提示','當(dāng)前盤面包含不滿足數(shù)獨(dú)條件的值，請(qǐng)檢查')
elif x=='s': #驗(yàn)證盤面
s5,msg=getSudo(evs,0) #9*9
if msg[0]!='':
messagebox.showinfo('提示',msg[0])
elif msg[1]!='': #有空值來驗(yàn)證
s6=s5.copy()
isvs=isValidSudoku(s6)
if isvs==-1:messagebox.showinfo('提示','當(dāng)前盤面為空，請(qǐng)先手動(dòng)輸入一個(gè)合法盤面或點(diǎn)生成數(shù)獨(dú)')
elif isvs:messagebox.showinfo('提示','當(dāng)前盤面滿足數(shù)獨(dú)條件,請(qǐng)繼續(xù)作答或選擇電腦解答')
else:messagebox.showinfo('提示','當(dāng)前盤面包含不滿足數(shù)獨(dú)條件的值，請(qǐng)檢查')
else:#填完了的情況
s6=s5.copy()
isvs=isValidSudoku(s6)
if isvs:messagebox.showinfo('恭喜','恭喜，當(dāng)前數(shù)獨(dú)已解答正確！')
else:messagebox.showinfo('提示','當(dāng)前盤面包含不滿足數(shù)獨(dú)條件的值，請(qǐng)檢查')
#隨機(jī)生成 電腦解 驗(yàn)證答案
ranInitBtn=tk.Button(root,text='生成數(shù)獨(dú)',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可執(zhí)行文件，大小是8點(diǎn)多M，作為Python導(dǎo)出的exe文件，這個(gè)大小是有優(yōu)勢(shì)的，結(jié)果如下：
小結(jié)
本文從解數(shù)獨(dú)的手動(dòng)解法引入，講到解數(shù)獨(dú)常用的回溯法，并且按照思路實(shí)現(xiàn)回溯代碼，通過這一思路去解兩個(gè)LeetCode題，為了可玩性增加隨機(jī)生成一個(gè)數(shù)獨(dú)的代碼，并把以上功能整合為一個(gè)GUI程序，用于平時(shí)的數(shù)獨(dú)訓(xùn)練，并且把這一GUI腳本打包為一個(gè)exe文件，在Windows系統(tǒng)下使用。
項(xiàng)目完整代碼更新于https://github.com/QLWeilcf/sudokupyGUI
