分治法解决马踏棋盘问题（马走日问题）

最终效果：https://chromezh.github.io/knights-tour-visualization/

代码：https://github.com/chromezh/knights-tour-visualization

代码采用纯 C 语言编写，然后通过 Emscripten 将 C 语言编译为 JavaScript，放入网页中，使用 Canvas 绘图。

算法：

解决马踏棋盘问题，我使用的算法是分治法，是对论文 Parberry, Ian. “An efficient algorithm for the Knight’s tour problem.” Discrete Applied Mathematics 73.3(1997):251-260. 中算法的实现。

定义 1：如果能从棋盘上最后遍历的一个点回到第一个点，则称这种马的遍历是闭合的。

定义 2：如果马的遍历路径包含下图中的所有路径，则称这种马的遍历是结构性的。

数学上已经证明：n * n 棋盘上具有闭合的马的遍历路径当且仅当 n ≥ 6 且是偶数。

对于 6 * 6, 6 * 8, 8 * 8, 8 * 10, 10 * 10, 10 * 12 的棋盘，已经找到闭合的、结构性的马的遍历路径，如下图所示：

这说明对于 n ∈ {6, 8, 10}，问题已经解决了。

对于更大的 n, 考虑将棋盘分割为小块，每一小块符合上述大小，例如对于 n = 42，可以进行如下分割：

分割后，每一个小块都已经解决，下一步是将各个小块连接在一起。由于每个小块都是结构性的，可以将角上的路径做如下替换，问题得到解决。

数据结构如下：

由于每个点只与其它两个点相连，将路径存放在有两个元素的数组中。

从一个点到其它点只有 8 种可能的方向，定义为 0-7。

point attribute 变量存放这个点的属性，在棋盘的角上有 8 个位置需要替换，定义为 0-7，不需要替换的是普通点，定义为 8。