天天看点

python 回溯法 子集树模板 系列 —— 18、马踏棋盘

将马放到国际象棋的8*8棋盘board上的某个方格中,马按走棋规则进行移动,走遍棋盘上的64个方格,要求每个方格进入且只进入一次,找出一种可行的方案。

python 回溯法 子集树模板 系列 —— 18、马踏棋盘

说明:这个图是5*5的棋盘。

类似于迷宫问题,只不过此问题的解长度固定为64

每到一格,就有[(-2,1),(-1,2),(1,2),(2,1),(2,-1),(1,-2),(-1,-2),(-2,-1)]顺时针8个方向可以选择。

走到一格称为走了一步,把每一步看作元素,8个方向看作这一步的状态空间。

套用回溯法子集树模板。

python 回溯法 子集树模板 系列 —— 18、马踏棋盘