给沙雕群友看的马踏棋盘算法

题目：已知马走日。8*8的棋盘上，输入马的初始位置(x,y)，输出一种能够让马不重复地走遍整个棋盘的方法。（注：这题竟然没要求最后必须回到出发点，什么鬼。）

解：看到这个题目，首先想到回溯法。用通俗的语言解释，就是：

boolean 跳(棋盘b, 当前点p) {

    如果b已完成，return true;

    否则，对于p的每一个可行的下一步位置p1，递归调用跳(去掉p1的b, p1)。然后如果其中有true则打印出来并return true，否则return false;

}

说白了就是一个DFS。

于是我们首先构造Point类，内置x,y两个参数并且实现一些有用的方法。

然后我们构造棋盘类，其中内置一个8*8的二维boolean数组，并实现clone()方法方便传参。

然后构造主类

然后就写完了，是不是很简单？

我们只需要美滋滋的点击运行，然后。。

。。我擦，程序怎么卡住了？

。。三分钟过去了

。。五分钟过去了

。。十分钟过去了，还是没有算出东西来。

我擦，是哪里写错了吗？

我慌得要死，慌忙把棋盘大小改成6*6，却发现程序一瞬间就给出了结果。

我忽而想起上次专栏里提到的沙雕同学的语录，“指数复杂度的算法多少都沾点脑瘫”。

凡事总须研究，才会明白。古来时常脑瘫，我也还记得，可是不甚清楚。我翻开代码一查，这代码没有注释，歪歪斜斜的每叶上都写着“深度优先”几个字。我横竖睡不着，仔细看了半夜，才从字缝里看出字来，满本都写着两个字是“脑瘫”！

注：此时的算法实现了一个8叉n²层（n为棋盘边长），但下层比较稀疏的选择树，在最坏条件下的时间复杂度是O(8^(n²))。

但在这道题里，脑瘫似乎不可避免。因此我们可以通过某种方式加快程序的运行速度，这种方式就是（某种意义上的）贪心。即，在每一步跳跃时，优先跳向那些邻接点比较少的点，这样可以尽量避免某些点成为所有邻接点都用完的，不可访问的“死点”。否则，在一个点成为“死点”后，程序仍然会傻乎乎的运行半天，直到发现自己永远也达不到跳完的真实。为此，我们只需要对列表进行排序：

然后重新运行程序。

此时我们可以惊奇地发现，哇，新的算法算出结果只需不到一秒！

（但这并不影响它仍然是一个脑瘫算法的本质）

以上。