python小练习（067）：回溯法（深度优先搜索）求解数独问题

qaz123765

shud=[
[0,0,8,0,0,0,2,0,0],
[0,3,0,8,0,2,0,6,0],
[7,0,0,0,9,0,0,0,5],
[0,5,0,0,0,0,0,1,0],
[0,0,4,0,0,0,6,0,0],
[0,2,0,0,0,0,0,7,0],
[4,0,0,0,8,0,0,0,6],
[0,7,0,1,0,3,0,9,0],
[0,0,1,0,0,0,8,0,0]]


def uniq(m,n,val):
    for r in shud[m]:
        if r==val:
            return False
    for c in shud:
        if c[n]==val:
            return False
    rx,cx=m//3*3,n//3*3
    for i in range(rx,rx+3):
        for rc in shud[i][cx:cx+3]:
            if rc==val:
                return False
    return True

def nextc(m,n):
    for mmn in range(n+1,9):
        if shud[m][mmn]==0:
            return m,mmn
    for mn in range(m+1,9):
        for nn in range(0,9):
            if shud[mn][nn]==0:
                return mn,nn 
    return -1,-1
def tryl(m,n):
    if shud[m][n]==0:
        for k in range(1,10):
            if uniq(m,n,k):
                shud[m][n]=k 
                nextm,nextn=nextc(m,n)
                if nextm==-1 and nextn==-1:
                    return True
                else:
                    valu=tryl(nextm,nextn)
                    if not valu:
                        shud[m][n]=0
                    else:
                        return True

for i in range(9):
    for j in range(9):
        if shud[i][j]==0:
            break
    break
tryl(i,j)
print(shud)

kio

学习学习

suloman

学习来了

cxbpritice

学习了

总有理

学习了。

nateen

感谢楼主

shigure_takimi

walter

学习学习！！！！！！！！！

JAY饭

执行速度远不如楼主快

s =[[0,0,8,0,0,0,2,0,0],
[0,3,0,8,0,2,0,6,0],
[7,0,0,0,9,0,0,0,5],
[0,5,0,0,0,0,0,1,0],
[0,0,4,0,0,0,6,0,0],
[0,2,0,0,0,0,0,7,0],
[4,0,0,0,8,0,0,0,6],
[0,7,0,1,0,3,0,9,0],
[0,0,1,0,0,0,8,0,0]]
s_kong = []   #空白坐标的列表
right = {}  #每个空白坐标对应的可选数字组成的列表
s_jiu = [[] for i in range(3)]  #s_jiu,s_heng,s_shu分别对应每一个九宫格，每一行，每一列
for i in range(9):              #只含非零数字的列表
    fen = i//3
    if i%3 == 0:
        t1 = []
        t2 = []
        t3 = []
    for j in range(9):
        if s[i][j] ==0:
            s_kong.append((i,j))
            continue
        if j//3 == 0:
            t1.append(s[i][j])
        elif j//3 ==1:
            t2.append(s[i][j])
        else:
            t3.append(s[i][j])
    if i%3 ==2:
        s_jiu[fen].append(t1)
        s_jiu[fen].append(t2)
        s_jiu[fen].append(t3)  

s_heng = [[] for i in range(9)]
s_shu = [[] for i in range(9)]
for i in range(9):
    for j in range(9):
        if s[i][j]: s_heng[i].append(s[i][j])
        if s[j][i]: s_shu[i].append(s[j][i])

for i in range(9):   #用right字典将每一个空白位置赋值对应可选的数字列表
    heng = s_heng[i] 
    for j in range(9):
        if not s[i][j]:
            shu = s_shu[j]
            a,b = i//3,j//3
            jiu = s_jiu[a][b]
            bu = heng + shu + jiu
            right[(i,j)] = [ i for i in range(1,10) if i not in bu]

m = 0  # m对应空白列表s_kong的每个元素
visit = []

def tianzi(m):
    x,y = s_kong[m]
    for i in right[(x,y)]: #将每个空白位置可选的元素迭代，筛选不和后面可选元素矛盾的元素
        a,b = x//3,y//3    #对应每个九宫格在s_jiu的位置
        sign = 0           #sign的作用决定是否继续递归下去
        s[x][y] = i
        if x==8 and y==8: 
            print('found')
            for real in s:
                print(real)
            return 1
        visit.append((x,y)) #将已经迭代的位置加入列表，保证后面的移除元素对已经遍历的
        lin = []            #位置没有影响，lin列表的作用记录此次迭代中被移除i元素的位置
        for j in right:     
            if j[0] == x or j[1] ==y or (j[0]//3 ==a and j[1]//3 == b):
                if j not in visit and i in right[j]:  #以上是判断是否跟(x,y)在同一行，一
                    lin.append(j)                     #列，或者同一个九宫格，如果是，是不是
                    right[j].remove(i)          #含有i元素，并且不在visit列表中
                    if len(right[j])==0:        #如果有位置的对应可选元素为空，终止此次迭代
                        sign=1
                        visit.pop()             #一切动过的元素都还原
                        break
        if sign:
            for l in lin:
                right[l].append(i)
            continue     #因为条件不符，不再继续往下递归
        if tianzi(m+1) == 1: 
            return 1
        visit.remove((x,y))  #一旦递归返回上一层，说明此次迭代失败，元素位置还原
        for l in lin:
                right[l].append(i)
tianzi(m)

LargeCat

谢谢！！！！！！！！！！！！！！！！！！！！

dfh93@163.com

谢谢楼主，认真学习！

wenweno

KING_NJ

666

达锅

看看

grf1973

学习

恋糖猫

kank

jxhjx

想看看结构

拉了盏灯

学习学习
⊙⊙！

bly

学习学习

子沙

学习学习