马踏棋盘算法（骑士周游问题）

一、问题概述

马踏棋盘算法也被称为骑士周游问题。问题内容是：

将马随机放在国际象棋的 n×n 棋盘的某个方格中， 马按走棋规则（马走日字）进行移动。要求每个方格只能走一次， 走遍棋盘上全部方格，求可行的路径。

二、思路分析

马踏棋盘问题实际上是图的深度优先搜索（DFS）的应用。

该问题的解决思想为：

1. 假设以 V 为起点，首先找出在指定规则下 V 点下一步可能的落点。
2. 在下一步的可能的落点中选择一个点（假设是 U 点），然后走到 U 点。
3. 再以 U 点为起点，找出指定规则下 U 点下一步可能的落点。
4. 在下一步可能的落点中选择一个点（假设是 W 点），然后走到 W 点。
5. 如此循环下去，直至走完了所有的格子。

需要注意的是，在下一步可能的落点中选择一个点这个操作具体怎么进行呢？是随机选择一个点的吗？

并不是随机的，这里面用到了贪心算法：为了让之后的选择尽可能少一点，一般会在下一步可能的落点选项中优先选择这样的一个点，这个点的特点是它的下一步可能的落点的个数最少。

举个栗子，假如 V0 点的下一步可能的落点有 U0、U1、U2，而 U0 的下一步可能的落点只有 W0，U1下一步可能的落点有 W1、W2，U2 下一步可能的落点有 W3、W4、W5。由于 U0 的下一步可能的落点个数只有 1 个，是 U0、U1、U2 中最少的，因此 V0 下一步将会优先选择走到 U0。

三、代码实现

首先是实现找到下一步可能的落点，我们首先来看下图：

从图中可以知道，任意一个点下一步的落点至多有 8 种可能，对于每种可能我们都需要考虑到。因此找到下一步可能的落点实现代码如下：

/**
 * 获取当前点下一步可以走的点的集合
 * @param curPoint  当前点
 */
public static ArrayList<Point> next(Point curPoint){
   
    ArrayList<Point> points = new ArrayList<>();    // 当前点下一步可选的点集合
    Point point = new Point();

    /* 针对 8 种情况的判断 */
    if ((point.x=curPoint.x-2)>=0 && (point.y=curPoint.y-1)>=0){
       // 左 2 上 1
        points.add(new Point(point));
    }
    if ((point.x=curPoint.x-1)>=0 && (point.y=curPoint.y-2)>=0){
       // 左 1 上 2
        points.add(new Point(point));
    }
    if ((point.x=curPoint.x+1)<col && (point.y=curPoint.y-2)>=0){
      // 右 1 上 2
        points.add(new Point(point));
    }
    if ((point.x=curPoint.x+2)<col && (point.y=curPoint.y-1)>=0)</
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22