数独问题大家都很熟悉，很喜欢挑战。但解决此问题极其需要耐心和逻辑，正因为此，解决完才会享受到那种成就感的乐趣。本文利用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
上图展示了利用本文程序解决不同难度数独问题所用的时间对比。
