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

qaz123765

1. shud=[
   
2. [0,0,8,0,0,0,2,0,0],
   
3. [0,3,0,8,0,2,0,6,0],
   
4. [7,0,0,0,9,0,0,0,5],
   
5. [0,5,0,0,0,0,0,1,0],
   
6. [0,0,4,0,0,0,6,0,0],
   
7. [0,2,0,0,0,0,0,7,0],
   
8. [4,0,0,0,8,0,0,0,6],
   
9. [0,7,0,1,0,3,0,9,0],
   
10. [0,0,1,0,0,0,8,0,0]]
    
11. 
    
12. 
    
13. def uniq(m,n,val):
    
14.     for r in shud[m]:
    
15.         if r==val:
    
16.             return False
    
17.     for c in shud:
    
18.         if c[n]==val:
    
19.             return False
    
20.     rx,cx=m//3*3,n//3*3
    
21.     for i in range(rx,rx+3):
    
22.         for rc in shud[i][cx:cx+3]:
    
23.             if rc==val:
    
24.                 return False
    
25.     return True
    
26. 
    
27. def nextc(m,n):
    
28.     for mmn in range(n+1,9):
    
29.         if shud[m][mmn]==0:
    
30.             return m,mmn
    
31.     for mn in range(m+1,9):
    
32.         for nn in range(0,9):
    
33.             if shud[mn][nn]==0:
    
34.                 return mn,nn
    
35.     return -1,-1
    
36. def tryl(m,n):
    
37.     if shud[m][n]==0:
    
38.         for k in range(1,10):
    
39.             if uniq(m,n,k):
    
40.                 shud[m][n]=k
    
41.                 nextm,nextn=nextc(m,n)
    
42.                 if nextm==-1 and nextn==-1:
    
43.                     return True
    
44.                 else:
    
45.                     valu=tryl(nextm,nextn)
    
46.                     if not valu:
    
47.                         shud[m][n]=0
    
48.                     else:
    
49.                         return True
    
50. 
    
51. for i in range(9):
    
52.     for j in range(9):
    
53.         if shud[i][j]==0:
    
54.             break
    
55.     break
    
56. tryl(i,j)
    
57. print(shud)
    

复制代码

kio

学习学习

suloman

学习来了

cxbpritice

学习了

总有理

学习了。

nateen

感谢楼主

shigure_takimi

walter

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

JAY饭

执行速度远不如楼主快

1. s =[[0,0,8,0,0,0,2,0,0],
   
2. [0,3,0,8,0,2,0,6,0],
   
3. [7,0,0,0,9,0,0,0,5],
   
4. [0,5,0,0,0,0,0,1,0],
   
5. [0,0,4,0,0,0,6,0,0],
   
6. [0,2,0,0,0,0,0,7,0],
   
7. [4,0,0,0,8,0,0,0,6],
   
8. [0,7,0,1,0,3,0,9,0],
   
9. [0,0,1,0,0,0,8,0,0]]
   
10. s_kong = []   #空白坐标的列表
    
11. right = {}  #每个空白坐标对应的可选数字组成的列表
    
12. s_jiu = [[] for i in range(3)]  #s_jiu,s_heng,s_shu分别对应每一个九宫格，每一行，每一列
    
13. for i in range(9):              #只含非零数字的列表
    
14.     fen = i//3
    
15.     if i%3 == 0:
    
16.         t1 = []
    
17.         t2 = []
    
18.         t3 = []
    
19.     for j in range(9):
    
20.         if s[i][j] ==0:
    
21.             s_kong.append((i,j))
    
22.             continue
    
23.         if j//3 == 0:
    
24.             t1.append(s[i][j])
    
25.         elif j//3 ==1:
    
26.             t2.append(s[i][j])
    
27.         else:
    
28.             t3.append(s[i][j])
    
29.     if i%3 ==2:
    
30.         s_jiu[fen].append(t1)
    
31.         s_jiu[fen].append(t2)
    
32.         s_jiu[fen].append(t3)  
    
33. 
    
34. s_heng = [[] for i in range(9)]
    
35. s_shu = [[] for i in range(9)]
    
36. for i in range(9):
    
37.     for j in range(9):
    
38.         if s[i][j]: s_heng[i].append(s[i][j])
    
39.         if s[j][i]: s_shu[i].append(s[j][i])
    
40. 
    
41. for i in range(9):   #用right字典将每一个空白位置赋值对应可选的数字列表
    
42.     heng = s_heng[i]
    
43.     for j in range(9):
    
44.         if not s[i][j]:
    
45.             shu = s_shu[j]
    
46.             a,b = i//3,j//3
    
47.             jiu = s_jiu[a][b]
    
48.             bu = heng + shu + jiu
    
49.             right[(i,j)] = [ i for i in range(1,10) if i not in bu]
    
50. 
    
51. m = 0  # m对应空白列表s_kong的每个元素
    
52. visit = []
    
53. 
    
54. def tianzi(m):
    
55.     x,y = s_kong[m]
    
56.     for i in right[(x,y)]: #将每个空白位置可选的元素迭代，筛选不和后面可选元素矛盾的元素
    
57.         a,b = x//3,y//3    #对应每个九宫格在s_jiu的位置
    
58.         sign = 0           #sign的作用决定是否继续递归下去
    
59.         s[x][y] = i
    
60.         if x==8 and y==8:
    
61.             print('found')
    
62.             for real in s:
    
63.                 print(real)
    
64.             return 1
    
65.         visit.append((x,y)) #将已经迭代的位置加入列表，保证后面的移除元素对已经遍历的
    
66.         lin = []            #位置没有影响，lin列表的作用记录此次迭代中被移除i元素的位置
    
67.         for j in right:     
    
68.             if j[0] == x or j[1] ==y or (j[0]//3 ==a and j[1]//3 == b):
    
69.                 if j not in visit and i in right[j]:  #以上是判断是否跟(x,y)在同一行，一
    
70.                     lin.append(j)                     #列，或者同一个九宫格，如果是，是不是
    
71.                     right[j].remove(i)          #含有i元素，并且不在visit列表中
    
72.                     if len(right[j])==0:        #如果有位置的对应可选元素为空，终止此次迭代
    
73.                         sign=1
    
74.                         visit.pop()             #一切动过的元素都还原
    
75.                         break
    
76.         if sign:
    
77.             for l in lin:
    
78.                 right[l].append(i)
    
79.             continue     #因为条件不符，不再继续往下递归
    
80.         if tianzi(m+1) == 1:
    
81.             return 1
    
82.         visit.remove((x,y))  #一旦递归返回上一层，说明此次迭代失败，元素位置还原
    
83.         for l in lin:
    
84.                 right[l].append(i)
    
85. tianzi(m)
    

复制代码

LargeCat

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

dfh93@163.com

谢谢楼主，认真学习！

wenweno

KING_NJ

666

达锅

看看

grf1973

学习

恋糖猫

kank

jxhjx

想看看结构

拉了盏灯

学习学习
⊙⊙！

bly

学习学习

子沙

学习学习