鱼C论坛

 找回密码
 立即注册
查看: 9399|回复: 58

[技术交流] python小练习(067):回溯法(深度优先搜索)求解数独问题

[复制链接]
发表于 2017-2-7 10:20:22 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

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

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

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

源代码:
游客,如果您要查看本帖隐藏内容请回复

本帖被以下淘专辑推荐:

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2017-2-7 14:11:26 | 显示全部楼层
学习,受教了
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-2-7 15:44:36 | 显示全部楼层
谢谢,学习了
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-2-7 16:59:02 | 显示全部楼层
厉害
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2017-2-7 17:43:13 | 显示全部楼层
高端
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2017-2-9 02:56:22 | 显示全部楼层
学习
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2017-2-10 11:10:46 | 显示全部楼层
来学习思路
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-3-16 10:57:25 | 显示全部楼层
正想要找一些Python习题练习一下,不过这里面的看起来难度挺大
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-4-24 18:18:02 | 显示全部楼层
学习
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2017-4-25 13:32:41 | 显示全部楼层
  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. def check(x, y):
  12.     global a
  13.     flag = 0
  14.     for i in range(9):
  15.         if a[i][y] == a[x][y]:
  16.             flag += 1
  17.     for j in range(9):
  18.         if a[x][j] == a[x][y]:
  19.             flag += 1
  20.     if flag > 2:
  21.         return False
  22.     else:
  23.         return True
  24.    
  25. def fillblank(x, y):
  26.     global a
  27.     if x == 9:
  28.         input('input a key to stop: ')
  29.         print(a)
  30.         exit()
  31.     if a[x][y] == 0:
  32.         for i in range(1, 10):
  33.             a[x][y] = i
  34.             if check(x, y):
  35.                 if y < 8:
  36.                     fillblank(x, y + 1)
  37.                 else:
  38.                     fillblank(x + 1, 0)
  39.             else:
  40.                 continue
  41.         a[x][y] = 0
  42.     else:
  43.         if y < 8:
  44.             fillblank(x, y + 1)
  45.         else:
  46.             fillblank(x + 1, 0)
  47.         
  48. fillblank(0, 0)
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-4-25 13:40:58 | 显示全部楼层

有个疑问:如果我在fillblank函数判断终止那儿写 if x == 9:return,那么函数会运行很长时间(没有等到结果),这是为甚吗?
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-4-25 17:40:01 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2017-4-25 18:43:18 | 显示全部楼层
膜拜大佬
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-4-27 18:43:36 | 显示全部楼层
受教了
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2017-4-27 21:48:54 | 显示全部楼层
本帖最后由 jerryxjr1220 于 2017-4-27 21:58 编辑
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年才能算完
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-4-28 15:41:46 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2017-4-28 23:45:29 | 显示全部楼层
学习学习
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-4-29 09:38:41 | 显示全部楼层
jerryxjr1220 发表于 2017-4-27 21:48
你的check函数好像不完整吧?

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

原来我连玩法都没搞清楚啊,尴了个大尬~
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-6-12 11:41:26 | 显示全部楼层
学习
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

头像被屏蔽
发表于 2017-6-26 09:44:48 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-28 23:00

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表