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

jerryxjr1220

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

我又写了一个不用递归的方法，只有十几行代码。不过也不快，大概1～2分钟才出答案。

1. n = 8
   
2. moves = [[2, 1], [2, -1], [-2, 1], [-2, -1], [1, 2], [1,-2], [-1, 2], [-1, -2]]
   
3. start = [(7,0)]
   
4. queue = [start]
   
5. while queue:
   
6.     q = queue.pop()
   
7.     if len(q) == n*n:
   
8.         print('Done!')
   
9.         print(q)
   
10.         break
    
11.     loc = q[-1]
    
12.     for m in moves:
    
13.         x = loc[0] + m[0]
    
14.         y = loc[1] + m[1]
    
15.         if -1<x<n and -1<y<n and (x,y) not in q:
    
16.             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)]

zdh

看看

da19921111

谢谢分享

撒法空间

厉害了

huahuacn1

谢谢大佬的分享～

sagerzone

学习了

Barnett_xxf

！

elbert

来看看看啦

elbert

来看看看啦。。

elbert

来看看，学习下

18064164275

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

JAY饭

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

象牙芒果

学习学习

DRanger23

学习了，谢谢

shigure_takimi

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

cjk101

学习一下

wyh150

学习学习！

溯影

先预习一下数据结构上的深度优先搜索哈哈

wuying12138