数独问题大家都很熟悉，很喜欢挑战。但解决此问题极其需要耐心和逻辑，正因为此，解决完才会享受到那种成就感的乐趣。本文利用Python3 解决数独问题，虽然过程不一样，但结果还是会让人感受一样的乐趣。
问题描述
根据九宫格盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个宫(3 * 3)内的数字均含1—9这9个数字。说句题外话，三位爱尔兰数学家2012年发表了一篇论文，证明了数独至少需要 17 个初始数字才有唯一解。
解决思路
对每个空格寻找到其可能的数字，选择有可能的数字数量最小的，为其添加一个数字，并记录此状态，以此类推，当无解时则返回上一个节点状态，直到全部空格填充完毕。
Python3代码
import pandas as pd
import numpy as np
本文利用Pandas读取存放数独的Excel文件，利用Numpy进行运算。首先读取文件：
Data=r'C:\Users\GWT9\Desktop\sukodu\sudoko.xlsx'
ReadData=pd.read_excel(Data)
NumData=ReadData.values
Excel文件格式如下图：
sukodu.png
下面设置数独问题的宫数，一是为了读取数据，因为Pandas读取数据时，如果最后一列全为空，则不会读出。二是本文程序可以拓展到16、25宫。
sukoducount=9
判断数据行的完整性，防止最后一行全为空无法读出。
while len(NumData)<sukoducount:
NumData=np.row_stack((NumData,[np.nan]*sukoducount))
计算某个位置空格的可能性数字
def ProbNumber(hang,lie,data):
#当前位置所在行
H=list(data[hang])
#当前位置所在列
L=list(data[:,lie])
#当前位置所在宫
G=[]
sfang=int(len(data)**0.5)
hh=hang//sfang
ll=lie//sfang
for ig in range(sfang):
for gi in range(sfang):
G.append(data[hh*sfang+ig,ll*sfang+gi])
lal=list(H)+list(L)+G
#该空格的可能性数字集合
prob=[ip for ip in list(range(1,len(data)+1)) if ip not in lal]
return prob
创建可能性字典
def ForK(data):
Kdict={}
for ik in range(len(data)):
for ki in range(len(data)):
if np.isnan(data[ik,ki]):
trans=ProbNumber(ik,ki,data)
#因为Python字典无序，在后面需要选择包含最少的数字可能
#性时，下面的设置可以保证每次取出的最小都是固定的。
jieti=len(trans)*10000000+ik*10000+ki*10
Kdict['%s-%s'%(ik,ki)]=[jieti,len(trans),trans]
return Kdict
选择可能性最小的位置
def SeleM(ddict):
Small=min(ddict.items(),key=lambda x:(x[1][0]))[0]
weizhi=Small.split('-')
Ha=int(weizhi[0])
Li=int(weizhi[1])
SE=ddict[Small][2]
return Ha,Li,SE
初始状态
InitialState={}
InitialState[0]=NumData
NumDict={}
代表整个程序进程的全局变量
global NU
NU=1
本程序中实现状态转移时采用的尾递归方式，但是Python内部没有对这种形式进行优化，并且最大递归层数大概是999。其解决办法是利用装饰器，参考：http://code.activestate.com/recipes/474088/。本文采用的方法是：在达到最大递归层数之前，记录下当时状态，退出递归，然后在重新进入递归，每这样一次称为一次循环。
def TransFer(insta,numdi,n=0,c=0):
if n==-1:
global NU
NU=2
return '此题无解'
#判断是否满足结束条件
if len(ForK(insta[n]))==0:
global NU
NU=0
return insta,numdi,n
#选择最小的
mmi=SeleM(ForK(insta[n]))
#当前递归层数的判断
if c>900:
return insta,numdi,n
if len(mmi[2])==0:
del insta[n]
c+=1
return TransFer(insta,numdi,n-1,c)
else:
middle=insta[n].copy()
if n in numdi:
if numdi[n]+1<len(mmi[2]):
numdi[n]+=1
middle[mmi[0],mmi[1]]=mmi[2][numdi[n]]
n+=1
insta[n]=middle.copy()
c+=1
return TransFer(insta,numdi,n,c)
else:
del numdi[n]
del insta[n]
c+=1
return TransFer(insta,numdi,n-1,c)
else:
numdi[n]=0
middle[mmi[0],mmi[1]]=mmi[2][0]
n+=1
insta[n]=middle.copy()
c+=1
return TransFer(insta,numdi,n,c)
第一次循环
c_0=TransFer(InitialState,NumDict)
VAR_NAME=locals()
实现无数次循环直到解决的函数
def Sudoku():
count=1
while NU!=0:
VAR_NAME['c_%s'%count]=TransFer(eval('c_%s'%(count-1))[0],eval('c_%s'%(count-1))[1],eval('c_%s'%(count-1))[2])
count+=1
print(eval('c_%s'%(count-1))[0][eval('c_%s'%(count-1))[2]])
return '数独问题解决'
实例
下面上图
Paste_Image.png
上图展示了利用本文程序解决不同难度数独问题所用的时间对比。
