论坛 › Python交流 › python小练习（068）：回溯法（深度优先搜索）30行代码求解“马踏棋盘”问题

jerryxjr1220 发表于 2017-6-14 21:32:22

WelanceLee 发表于 2017-6-14 20:20
我的是10分钟也算不出来……

我又写了一个不用递归的方法，只有十几行代码。不过也不快，大概1～2分钟才出答案。n = 8
moves = [, , [-2, 1], [-2, -1], , , [-1, 2], [-1, -2]]
start = [(7,0)]
queue =
while queue:
    q = queue.pop()
    if len(q) == n*n:
      print('Done!')
      print(q)
      break
    loc = q[-1]
    for m in moves:
      x = loc + m
      y = loc + m
      if -1<x<n and -1<y<n and (x,y) not in q:
            queue.append(q + [(x, y)])
Done!
[(7, 0), (6, 2), (5, 0), (4, 2), (3, 0), (2, 2), (1, 0), (0, 2), (1, 4), (0, 6), (2, 5), (1, 3), (0, 1), (2, 0), (1, 2), (0, 0), (2, 1), (3, 3), (4, 1), (5, 3), (4, 5), (3, 7), (1, 6), (0, 4), (2, 3), (1, 1), (0, 3), (1, 5), (0, 7), (2, 6), (3, 4), (4, 6), (2, 7), (3, 5), (4, 7), (6, 6), (7, 4), (5, 5), (6, 7), (7, 5), (5, 4), (7, 3), (6, 1), (4, 0), (3, 2), (2, 4), (0, 5), (1, 7), (3, 6), (4, 4), (5, 6), (7, 7), (6, 5), (5, 7), (7, 6), (6, 4), (7, 2), (6, 0), (5, 2), (3, 1), (4, 3), (5, 1), (6, 3), (7, 1)]

P先生 发表于 2017-6-26 09:45:30

zdh 发表于 2017-8-10 10:49:46

看看

da19921111 发表于 2017-8-11 15:29:22

谢谢分享

撒法空间 发表于 2017-8-11 18:55:23

厉害了

huahuacn1 发表于 2017-9-4 10:22:33

谢谢大佬的分享～

sagerzone 发表于 2017-10-3 10:02:04

学习了

Barnett_xxf 发表于 2017-10-3 19:48:33

！

elbert 发表于 2017-10-16 17:15:33

来看看看啦

elbert 发表于 2017-10-16 17:15:48

来看看看啦。。

elbert 发表于 2017-10-16 17:16:42

来看看，学习下

18064164275 发表于 2018-1-11 11:40:18

哈哈顶！！！！！！！！！！

JAY饭 发表于 2018-2-11 08:44:47

{:9_227:}这个运行速度还跟移动顺序有关系，我自己写的顺序，饭吃完了都没出结果，

象牙芒果 发表于 2018-2-12 14:52:28

学习学习

DRanger23 发表于 2018-3-15 02:31:03

学习了，谢谢

shigure_takimi 发表于 2018-3-15 08:23:57

勉強させていただきます。

cjk101 发表于 2018-3-23 21:55:29

学习一下

wyh150 发表于 2018-4-19 08:50:38

学习学习！

溯影 发表于 2018-4-19 09:03:49

先预习一下数据结构上的深度优先搜索哈哈{:10_254:}

wuying12138 发表于 2018-8-13 18:23:05

{:7_113:}

查看完整版本: python小练习（068）：回溯法（深度优先搜索）30行代码求解“马踏棋盘”问题