鱼C论坛

 找回密码
 立即注册
楼主: jerryxjr1220

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

[复制链接]
发表于 2017-7-7 00:29:27 From FishC Mobile | 显示全部楼层
本帖最后由 qaz123765 于 2017-7-7 00:47 编辑
  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. def uniq(m,n,val):
  12.     for r in shud[m]:
  13.         if r==val:
  14.             return False
  15.     for c in shud:
  16.         if c[n]==val:
  17.             return False
  18.     rx,cx=m//3*3,n//3*3
  19.     for i in range(rx,rx+3):
  20.         for rc in shud[i][cx:cx+3]:
  21.             if rc==val:
  22.                 return False
  23.     return True

  24. def nextc(m,n):
  25.     for mmn in range(n+1,9):
  26.         if shud[m][mmn]==0:
  27.             return m,mmn
  28.     for mn in range(m+1,9):
  29.         for nn in range(0,9):
  30.             if shud[mn][nn]==0:
  31.                 return mn,nn
  32.     return -1,-1
  33. def tryl(m,n):
  34.     if shud[m][n]==0:
  35.         for k in range(1,10):
  36.             if uniq(m,n,k):
  37.                 shud[m][n]=k
  38.                 nextm,nextn=nextc(m,n)
  39.                 if nextm==-1 and nextn==-1:
  40.                     return True
  41.                 else:
  42.                     valu=tryl(nextm,nextn)
  43.                     if not valu:
  44.                         shud[m][n]=0
  45.                     else:
  46.                         return True

  47. for i in range(9):
  48.     for j in range(9):
  49.         if shud[i][j]==0:
  50.             break
  51.     break
  52. tryl(i,j)
  53. print(shud)
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

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

使用道具 举报

发表于 2017-9-8 22:36:28 From FishC Mobile | 显示全部楼层
学习来了
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

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

使用道具 举报

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

使用道具 举报

发表于 2017-11-28 23:16:50 | 显示全部楼层
感谢楼主
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

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

使用道具 举报

发表于 2017-12-3 22:51:04 | 显示全部楼层
学习学习!!!!!!!!!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-3-3 21:12:39 | 显示全部楼层
执行速度远不如楼主快
  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. s_heng = [[] for i in range(9)]
  34. s_shu = [[] for i in range(9)]
  35. for i in range(9):
  36.     for j in range(9):
  37.         if s[i][j]: s_heng[i].append(s[i][j])
  38.         if s[j][i]: s_shu[i].append(s[j][i])

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

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

  50. def tianzi(m):
  51.     x,y = s_kong[m]
  52.     for i in right[(x,y)]: #将每个空白位置可选的元素迭代,筛选不和后面可选元素矛盾的元素
  53.         a,b = x//3,y//3    #对应每个九宫格在s_jiu的位置
  54.         sign = 0           #sign的作用决定是否继续递归下去
  55.         s[x][y] = i
  56.         if x==8 and y==8:
  57.             print('found')
  58.             for real in s:
  59.                 print(real)
  60.             return 1
  61.         visit.append((x,y)) #将已经迭代的位置加入列表,保证后面的移除元素对已经遍历的
  62.         lin = []            #位置没有影响,lin列表的作用记录此次迭代中被移除i元素的位置
  63.         for j in right:     
  64.             if j[0] == x or j[1] ==y or (j[0]//3 ==a and j[1]//3 == b):
  65.                 if j not in visit and i in right[j]:  #以上是判断是否跟(x,y)在同一行,一
  66.                     lin.append(j)                     #列,或者同一个九宫格,如果是,是不是
  67.                     right[j].remove(i)          #含有i元素,并且不在visit列表中
  68.                     if len(right[j])==0:        #如果有位置的对应可选元素为空,终止此次迭代
  69.                         sign=1
  70.                         visit.pop()             #一切动过的元素都还原
  71.                         break
  72.         if sign:
  73.             for l in lin:
  74.                 right[l].append(i)
  75.             continue     #因为条件不符,不再继续往下递归
  76.         if tianzi(m+1) == 1:
  77.             return 1
  78.         visit.remove((x,y))  #一旦递归返回上一层,说明此次迭代失败,元素位置还原
  79.         for l in lin:
  80.                 right[l].append(i)
  81. tianzi(m)
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-3-4 10:11:13 | 显示全部楼层
谢谢!!!!!!!!!!!!!!!!!!!!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-3-4 16:40:04 | 显示全部楼层
谢谢楼主,认真学习!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-3-17 16:58:42 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-3-26 10:44:40 | 显示全部楼层
666
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-4-7 22:26:21 From FishC Mobile | 显示全部楼层
看看
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

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

使用道具 举报

发表于 2018-5-22 14:00:23 | 显示全部楼层
kank
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-8-1 20:36:48 | 显示全部楼层
想看看结构
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-8-2 00:19:54 From FishC Mobile | 显示全部楼层
学习学习
⊙⊙!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-8-9 14:47:18 | 显示全部楼层
学习学习
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-8-15 06:32:49 From FishC Mobile | 显示全部楼层
学习学习
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

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

本版积分规则

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

GMT+8, 2024-3-29 14:57

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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