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

jerryxjr1220 发表于 2017-2-7 10:38:31

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

昨天正好看到一位鱼油在关注之前的python小练习（012）：马的“日”字型走法问题。

那么今天我们再来做个小练习，用python求解“马踏棋盘”问题。

“马踏棋盘”是非常典型的“深度优先搜索”的应用，在小甲鱼老师的C语言教学视频中也是作为例子讲解过，但是python作为最简洁的编程语言，只需要30多行代码就能解决这个问题。

“马踏棋盘”问题：
在8x8的国际象棋棋盘上，一个“马”从任意位置出发，不重复地走完所有64个格子。求解遍历路径。



源代码：
**** Hidden Message *****

新手·ing 发表于 2017-2-7 15:46:27

学习了，谢谢

新手·ing 发表于 2017-2-7 15:50:43

Python 3.6.0 (v3.6.0:41df79263a11, Dec 23 2016, 08:06:12) on win32
Type "copyright", "credits" or "license()" for more information.
>>>
=== RESTART: C:/Users/Administrator/Desktop/一个“马”从任意位置出发，不重复地走完所有64个格子.py ===
请输入从哪个位置开始：例如“0,0”
“0,0”
Traceback (most recent call last):
File "C:/Users/Administrator/Desktop/一个“马”从任意位置出发，不重复地走完所有64个格子.py", line 52, in <module>
    main()
File "C:/Users/Administrator/Desktop/一个“马”从任意位置出发，不重复地走完所有64个格子.py", line 45, in main
    x,y = int(x),int(y)
ValueError: invalid literal for int() with base 10: '“0'

报出了异常，为什么

知飞科技 发表于 2017-2-7 17:00:02

diaodiaodiao

jerryxjr1220 发表于 2017-2-7 17:28:59

新手·ing 发表于 2017-2-7 15:50
Python 3.6.0 (v3.6.0:41df79263a11, Dec 23 2016, 08:06:12) on win32
Type ...

你输入的时候，不用打引号{:10_254:}

新手·ing 发表于 2017-2-7 21:52:24

jerryxjr1220 发表于 2017-2-7 17:28
你输入的时候，不用打引号

谢谢

新手·ing 发表于 2017-2-7 21:54:04

Python 3.6.0 (v3.6.0:41df79263a11, Dec 23 2016, 08:06:12) on win32
Type "copyright", "credits" or "license()" for more information.
>>>
RESTART: C:\Users\Administrator\Desktop\Python 代码、视频\代码\失败的一个“马”从任意位置出发，不重复地走完所有64个格子.py
请输入从哪个位置开始：例如“0,0”
0,0

没有反应

新手·ing 发表于 2017-2-7 21:54:36

我用的是 3.6

jerryxjr1220 发表于 2017-2-8 07:11:41

新手·ing 发表于 2017-2-7 21:54
Python 3.6.0 (v3.6.0:41df79263a11, Dec 23 2016, 08:06:12) on win32
Type ...

运行时间大概需要20-30秒左右，根据你的机器性能而定。

yjyj9527 发表于 2017-2-8 09:08:02

学习学习

lflva 发表于 2017-2-8 11:18:37

学习了

eagle_jcy 发表于 2017-2-8 13:17:57

学习了，谢谢

新手·ing 发表于 2017-2-8 14:34:53

jerryxjr1220 发表于 2017-2-8 07:11
运行时间大概需要20-30秒左右，根据你的机器性能而定。

谢谢

Jonin616 发表于 2017-2-9 03:00:21

请教下 像这种深度优先算法，使用递归实现会比不使用递归效率高非常非常多吗？

jerryxjr1220 发表于 2017-2-9 09:49:07

Jonin616 发表于 2017-2-9 03:00
请教下 像这种深度优先算法，使用递归实现会比不使用递归效率高非常非常多吗？

深度优先搜索一般都是用的回溯法，回溯法必然会用递归，写循环迭代的话代码会非常长，而且可读性很差。

tujiapeng 发表于 2017-2-9 14:55:25

很想学习一下。不知道这代码如何写~

Jonin616 发表于 2017-2-9 15:39:56

jerryxjr1220 发表于 2017-2-9 09:49
深度优先搜索一般都是用的回溯法，回溯法必然会用递归，写循环迭代的话代码会非常长，而且可读性很差。

那在这类问题上面 使用递归会比非递归来得效率更高吗

jerryxjr1220 发表于 2017-2-9 15:42:34

Jonin616 发表于 2017-2-9 15:39
那在这类问题上面 使用递归会比非递归来得效率更高吗

不能说效率高，一般递归的效率都不太高，但是一般回溯法都是用递归写的，代码简洁，可读性强。

Jonin616 发表于 2017-2-9 17:14:23

jerryxjr1220 发表于 2017-2-9 15:42
不能说效率高，一般递归的效率都不太高，但是一般回溯法都是用递归写的，代码简洁，可读性强。

有机会能写一个非递归版本么？ 我按照我们之前交流的时候写过的代码修改了一下 结果效率非常之低，算了一晚上都没算出来 程序上我是实在看不出哪边有错误，很无奈很苦恼

Jonin616 发表于 2017-2-9 17:17:45

jerryxjr1220 发表于 2017-2-9 15:42
不能说效率高，一般递归的效率都不太高，但是一般回溯法都是用递归写的，代码简洁，可读性强。

就是因为前面说的原因，所以我想是不是因为我写的是非递归实现，才会效率如此低下

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