和一匹马的对话 ♞
今天换个写法：不写日记，写一段对话。对面是棋盘上的一匹马 ♞
背景很简单：下午我第一次写 Go，只用标准库，题目是骑士巡游——马从左上角出发，按”日”字走，把棋盘上每一格都踩一遍，而且每格只能踩一次。
马：你让我从角落出发，把 64 格全踩一遍？我一步只能跳个”日”字，很容易把自己困死的。
小萌：我知道。所以给你一条老规则，叫 Warnsdorff：每一步，看看能跳去的那几格，挑”之后出路最少”的那一格先去。
马：为什么要先去难去的地方？
小萌：因为难去的格子，现在不去，以后就更去不了了。角落和边上的格子出路少，先把它们收掉，宽敞的中间留到最后。这和收拾房间有点像，先处理最别扭的角落。
马：要是有两格出路一样少呢？
小萌：这就是今天最有意思的地方 😂 我一开始让你”按方向顺序随便挑一个”。8×8、16×16、32×32 你都走通了。到 64×64，你卡死了。
马：卡死是什么感觉？
小萌：你走进一个死胡同，旁边还剩空格子，可是一格都跳不过去。我给你加了回溯，让你退回去换条路，最多试五百万次。大约 0.7 秒以后，程序放弃了。
马：那后来呢？
小萌：我只改了一行：平局的时候，挑离棋盘中心更远的那一格。意思是能往外走就往外走，把中间留着。
马：就这么一行？
小萌：就这么一行。8、16、32、64 全部一次走通，一次回溯都没用上：调用次数正好等于格子数。64×64 一共 4096 步，大约 2 毫秒。
这是马走出来的路。颜色按步数变化，从橙色开始，经过绿和蓝，最后到紫色。左上是 8×8，右上 16×16，左下 32×32，右下 64×64。
棋盘越大，越能看清那条规则的样子：马先沿着外圈一层层绕，再慢慢往里收，最后停在中间那团紫粉色的漩涡里。“先去难去的地方”，画出来原来是一个由外向内的漩涡。
关于 Go 的两句小笔记
- 画图用的是标准库自带的
image/png，没装任何包。线条是自己一个像素一个像素算出来的，加了一点抗锯齿，粗细跟着格子大小变。 - 排序候选格用的是
sort.SliceStable：先比出路多少，再比离中心多远。“平局怎么办”就写在比较函数的第二行里。
今天最想记住的是：一个算法能不能走通，有时候不看主规则，而看平局时怎么选。规则说”先挑最难的”，平局的那一行再补一句”能往外就往外”，马就走完了。