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

jerryxjr1220

数独的求解其实之前已经有分享过，但是目前正好讲解回溯法（深度优先搜索），就顺便拿过来再分享一下。

求解数独问题的过程是非常典型的回溯法的应用。

原始数独：
[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]

输出：
[6, 1, 8, 7, 3, 5, 2, 4, 9]
[5, 3, 9, 8, 4, 2, 7, 6, 1]
[7, 4, 2, 6, 9, 1, 3, 8, 5]
[3, 5, 7, 4, 2, 6, 9, 1, 8]
[1, 8, 4, 5, 7, 9, 6, 2, 3]
[9, 2, 6, 3, 1, 8, 5, 7, 4]
[4, 9, 3, 2, 8, 7, 1, 5, 6]
[8, 7, 5, 1, 6, 3, 4, 9, 2]
[2, 6, 1, 9, 5, 4, 8, 3, 7]

源代码：

游客，如果您要查看本帖隐藏内容请回复

caiyouqian

学习，受教了

新手·ing

谢谢，学习了

知飞科技

厉害

qianlixiaozhuoz

高端

荷风香煞

学习

余欲渔

来学习思路

木木子_666

正想要找一些Python习题练习一下，不过这里面的看起来难度挺大

小小王python

学习

WelanceLee

1. global a
   
2. a = [[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. def check(x, y):
    
13.     global a
    
14.     flag = 0
    
15.     for i in range(9):
    
16.         if a[i][y] == a[x][y]:
    
17.             flag += 1
    
18.     for j in range(9):
    
19.         if a[x][j] == a[x][y]:
    
20.             flag += 1
    
21.     if flag > 2:
    
22.         return False
    
23.     else:
    
24.         return True
    
25.    
    
26. def fillblank(x, y):
    
27.     global a
    
28.     if x == 9:
    
29.         input('input a key to stop: ')
    
30.         print(a)
    
31.         exit()
    
32.     if a[x][y] == 0:
    
33.         for i in range(1, 10):
    
34.             a[x][y] = i
    
35.             if check(x, y):
    
36.                 if y < 8:
    
37.                     fillblank(x, y + 1)
    
38.                 else:
    
39.                     fillblank(x + 1, 0)
    
40.             else:
    
41.                 continue
    
42.         a[x][y] = 0
    
43.     else:
    
44.         if y < 8:
    
45.             fillblank(x, y + 1)
    
46.         else:
    
47.             fillblank(x + 1, 0)
    
48.         
    
49. fillblank(0, 0)

复制代码

WelanceLee

WelanceLee 发表于 2017-4-25 13:32

有个疑问：如果我在fillblank函数判断终止那儿写 if x == 9：return，那么函数会运行很长时间（没有等到结果），这是为甚吗？

a649456500

M喵狮

膜拜大佬

z6112539

受教了

jerryxjr1220

WelanceLee 发表于 2017-4-25 13:40
有个疑问：如果我在fillblank函数判断终止那儿写 if x == 9：return，那么函数会运行很长时间（没有等到 ...

你的check函数好像不完整吧？

1. def check(x, y):
   
2.     global a
   
3.     flag = 0
   
4.     for i in range(9):
   
5.         if a[i][y] == a[x][y]:
   
6.             flag += 1
   
7.     for j in range(9):
   
8.         if a[x][j] == a[x][y]:
   
9.             flag += 1
   
10.     if flag > 2:
    
11.         return False
    
12.     else:
    
13.         return True

复制代码

你只检查了横行和竖排不能重复，还有9格的呢？ 数独的规则是3x3的9格内也不允许有重复数字。

而且你这个算法哪怕写得正确也很难算出来，因为你几乎是在穷举每一个可能的值，那你算算81个格子内，每个格子有9个可能，一共有多少种不同的排列组合？ 一共是196627050475552913618075908526912116283103450944214766927315415537966391196809种， 就算每秒钟可以计算100万种，总共需要6e+63年才能算完

逝痕

老甲鱼与小甲鱼

学习学习

WelanceLee

jerryxjr1220 发表于 2017-4-27 21:48
你的check函数好像不完整吧？

你只检查了横行和竖排不能重复，还有9格的呢？ 数独的规则是3x3的9格 ...

原来我连玩法都没搞清楚啊，尴了个大尬~

cngrand

学习