Python3 趣味系列题1 ------回溯暴力解决

数独问题大家都很熟悉，很喜欢挑战。但解决此问题极其需要耐心和逻辑，正因为此，解决完才会享受到那种成就感的乐趣。本文利用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

上图展示了利用本文程序解决不同难度数独问题所用的时间对比。