当年自学谭浩强的C语言一个月之后，终于搞懂了八皇后问题，而且打印菱形、水仙花数之类的题目也做了十几道，信心满满。我想，『是时候去当一个程序员了』。
小学时听村里下棋的长辈说过，象棋中的马可以从任何一个位置出发，不重复地跳遍棋盘上的每一个位置。这个问题看起来像一个稍微难一点的八皇后，我决定用程序来实现它。
我决定做一个动画。当时用的是turboc的graphics绘图功能，非常闪烁，代码乱七八糟地也写了好几百行，在修改了n次崩溃以后，运行了几天几夜。最终并没有找到任何路径，但是看着一条条直线消失又出现，我发现我能沉迷于写代码和运行代码的乐趣之中。
在后来的很多年中我多次用不同的语言和方法实现过马踏棋盘以及动画，这个问题其实很有趣味性，能学会不少知识，值得反复去实现。
//为了简短起见，假设本文中所有代码都已经usingnamespacestd;
回溯法关于回溯法的定义，我的理解与王晓东《计算机算法设计与分析》教材上的定义最为接近，即回溯法是以深度优先的方式系统地搜索问题的解的算法。
回溯法是一个既带有系统性又带有跳跃性的搜索算法。它在包含问题的所有解的空间树中，按照深度优先的策略，从根节点出发搜索解空间树。
算法搜索至解空间树的任一节点时，总是先判断该节点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该节点为根的子树的系统搜索，逐层向其祖先节点回溯。
否则，进入该子树，继续按深度优先的策略搜索。回溯法在用来求问题的所有解时，要回溯到根，且根节点的搜索子树都已被搜遍才结束。而回溯法在用来求任一解时，只要搜索到问题的一个解就可结束。
为了实现马踏棋盘的算法，先来定义几个简单的数据结构。
按照马跳日字的规则，在棋盘上的每一个点，最多可以朝周围的8个点跳跃，每个点的x和y坐标变化如下图：
这样来定义数据结构：
//每个点最多可以朝8个方向跳constintDIRECTIONS=8;//表示每个点的坐标的简单结构体，比用std::pair更清晰structXY{intx;inty;};//每个方向的x、y左边的变化constXYdelta[DIRECTIONS]={{1,-2},{2,-1},{2,1},{1,2},{-1,2},{-2,1},{-2,-1},{-1,-2}};templateintWIDTH=9,intHEIGHT=10classHorseJump{private://辅助函数//判断某个点是否在棋盘内inlineboolValid(constXYp)const;//坐标p在某个方向的跳跃点inlineXYNeighbour(constXYp,intdirection)const;private:voidOutPut();//输出结果public://获取以pos为起点的全部路径voidStepAll(intdepth,XYpos);public:HorseJump()=default;//构造函数private://保存结果路径arrayXY,WIDTH*HEIGHTpath_={};//保存每个点当前是否已经被访问过arrayarraybool,WIDTH,HEIGHTvisited_={};};
定义比较简单，只有两个成员、5个函数，构造函数什么代码都不用写，所以算是只有4个函数。其中StepAll是实现回溯的函数。先来将其它3个函数实现。
Valid非常简单，就是判断某个点是否在棋盘内：
templateintWIDTH,intHEIGHTboolHorseJumpWIDTH,HEIGHT::Valid(constXYp)const{returnp.x=0p.xWIDTHp.y=0p.yHEIGHT;}
Neighbour用来得到某个跳跃方向的坐标，用数字0~7表示一个方向。
templateintWIDTH,intHEIGHTXYHorseJumpWIDTH,HEIGHT::Neighbour(constXYp,intdirection)const{return{p.x+delta[direction].x,p.y+delta[direction].y};}
OutPut就是在控制台里面输出当前找到的路径，路径本身保存在path_里面，将其显示出来即可。
templateintWIDTH,intHEIGHTvoidHorseJumpWIDTH,HEIGHT::OutPut(){intsteps[HEIGHT][WIDTH]={0};for(inti=0;iWIDTH*HEIGHT;++i){constXYxy=path_;steps[xy.y][xy.x]=i+1;}for(inti=0;iHEIGHT;++i){for(intj=0;jWIDTH;++j){cout.width(2);coutsteps[j]"";}cout"\n";}cout"\n";}
接下来就是实现回溯的StepAll函数了，该函数是试图找到以参数pos为起点的全部路径，代码如下：
templateintWIDTH,intHEIGHTvoidHorseJumpWIDTH,HEIGHT::StepAll(intdepth,XYpos){path_[depth]=pos;//保存路径visited_[pos.y][pos.x]=true;//设置该点被访问过if(depth=WIDTH*HEIGHT-1){//找到了一条完整路径OutPut();//输出路径return;}//朝8个方向跳for(inti=0;iDIRECTIONS;++i){constXYnew_pos=Neighbour(pos,i);if(!Valid(new_pos)
visited_[new_pos.y][new_pos.x]){continue;}StepAll(depth+1,new_pos);visited_[new_pos.y][new_pos.x]=false;}}
回溯法对于解空间树的特点是「不重复、不遗漏」，都在上面那个简单的循环里面。
至此，就可以写一个main函数来运行上面的代码了。如果要搜索以(3,5)为起点的全部路径，main函数如下：
intmain(){HorseJumphorse;horse.StepAll(0,XY{3,5});}
将棋盘的宽度和高度定义为HorseJump的模板参数，比直接在将WIDTH和HEIGHT定义成常量的好处是一次编译可以包含多个不同大小的棋盘，比如：
{HorseJump3,6horse;horse.StepAll(0,XY{0,0});}{HorseJump3,7horse;horse.StepAll(0,XY{0,0});}{HorseJump3,8horse;horse.StepAll(0,XY{0,0});}//...
这个代码可以用脚本生成，探索到底多小的棋盘是合理的，后面的分治法可以用到。
模板比将width和height定义成const的成员写代码也好写，path_这种作为成员变量的数组，可以直接将WIDTH和HEIGHT作为常量来使用。
贪心算法前面的代码虽然很简单，但是对于中国象棋9x10的棋盘，运行到世界末日也不会找到任何路径。但是贪心算法瞬间就可以找到一条路径。效果如下：
如果仔细观察回溯法运行的动画，可以发现最难找到出路的是那些边角的点，这些边角的点有一个特点，是「出口」较少，出口按照前面的代码定义，就是Valid的Neighbour节点较少。
在遍历每个节点的8个方向时，优先选择出口较少的点，只要这些点被搞定了，其它那些出口多的点就容易得多。这就是贪心算法。
给前面的代码增加一个private的函数，叫WayOut，用来计算某个点的出口数量：
templateintWIDTH,intHEIGHTintHorseJumpWIDTH,HEIGHT::WayOut(constXYp)const{intret=0;for(inti=0;iDIRECTIONS;++i){constXYn=Neighbour(p,i);if(Valid(n)!visited_[n.y][n.x]){++ret;}}returnret;}
增加一个叫StepAllGreedy的函数，将StepAll的代码稍微改改：
templateintWIDTH,intHEIGHTvoidHorseJumpWIDTH,HEIGHT::StepAllGreedy(intdepth,XYpos){path_[depth]=pos;visited_[pos.y][pos.x]=true;if(depth=WIDTH*HEIGHT-1){//找到了一条完整路径OutPut();return;}vectorintdirs;//所有的方向，放这里面排序for(inti=0;iDIRECTIONS;++i){XYneighbour=Neighbour(pos,i);if(Valid(neighbour)!visited_[neighbour.y][neighbour.x]){dirs.push_back(i);}}sort(begin(dirs),end(dirs),[pos,this](constintlhs,constintrhs){returnWayOut(Neighbour(pos,lhs))WayOut(Neighbour(pos,rhs));});for(inti:dirs){//对8个方向按出口从少到多排序以后再访问constXYnew_pos=Neighbour(pos,i);StepAllGreedy(depth+1,new_pos);visited_[new_pos.y][new_pos.x]=false;}}迭代回溯
回溯法可以很简单地用递归实现，用递归实现出来叫递归回溯，用非递归实现就叫迭代回溯。
如果要消除递归改成循环，需要就借助栈的作用。在C++中可以直接用std::stack。
将递归改成循环是作为程序员的一种很基本的能力，我曾经选过一些递归改非递归的面试题，考察的效果都是很不错的。
递归改回溯其实就是对于递归函数调用的理解，将局部变量和函数参数保存在一个栈上，递归深度加深就相当于压栈，深度减少就相当于弹出栈。
由于篇幅的原因，迭代的代码我这里省略。我的github上一个名字叫temp的目录中有马踏棋盘的迭代实现，那是2年前写的。
可能有人要问，为什么要将递归改成迭代？就是为了面试么？
当然不是了。比如说要做出本文之前的动画那样的程序，递归的写法是一块不能被重入的逻辑，出了递归函数就再回不去之前出来时候的状态了。
绘制动画的时候每计算一帧绘制一帧，看起来才会连续，而且这样非常符合单线程程序的特点。
用线程实现动画迭代回溯并不是实现动画最简单的方法，多线程才是。我最初的几次马踏棋盘动画都是用java的线程实现的。
将StepAll放入一个单独的线程，每走一步就将当前的数据发送到主线程，然后再sleep一段时间。
由于StepAll是运行在单独的线程中的，并不会阻塞主线程，而且实现起来非常简单。如何发送消息其实也很简单，在windows里面可以用PostMessage之类的方法，在Qt中可以用postEvent方法。
关于多线程的实现，代码也省略，因为要做这个动画，无论是多线程还是改成迭代回溯，在C++20中都已经out，C++20已经支持协程。我本次提供的代码用的就是协程。
用协程实现动画协程综合了前面所提到的两种方法的优点，像递归一样简单，又像迭代一样可以重入，而且还不用引入线程。
C++20中提供了协程的底层功能，对于将递归改成协程所需要的generator这样的高级类，C++20中并没有提供，而是打算用几年的时间，集思广益，选出最好的一个，争取放入到C++23的标准库中。
自己写一个简单的generator只要几十行代码，但是要支持递归、支持iterator、兼容ranges等等，就比较麻烦。我用的这个是半年前被提议加入标准库的一个实现。
但是一个月之前又出现了一个更好的generator，支持Allocator。所以现在看来，标准委员会的保守做法是很对的，不会为了赶进度盲目加东西到标注库中。
generator的实现不是本文的重点，直接拿来用即可。关于协程的文章我可以写几十篇甚至更多，有栈无栈对称非对称都可以写，包括如何一步一步实现一个自己的generator。C++标准库以后会提供通用的generator，但是某些情况下用自己实现的，可以节省空间、提高性能。以后有机会我会先写一两篇看看反响。
找出全部的解的函数叫StepAll，找出一个解我就叫Step，都是回溯。我的github代码里面都有。下面来看看用协程实现的CotoStep函数。我给HorseJump加了一个private成员变量叫booldone_=false;。
templateintWIDTH,intHEIGHTgeneratortupleint,int,intHorseJumpWIDTH,HEIGHT::CoroStep(intdepth,XYpos){path_[depth]=pos;visited_[pos.y][pos.x]=true;co_yieldtuple{depth,pos.x,pos.y};if(depth=WIDTH*HEIGHT-1){//找到了一条完整路径done_=true;co_return;}for(inti=0;iDIRECTIONS;++i){constXYnew_pos=Neighbour(pos,i);if(!Valid(new_pos)
visited_[new_pos.y][new_pos.x])continue;co_yieldCoroStep(depth+1,new_pos);if(done_){co_return;}visited_[new_pos.y][new_pos.x]=false;}}
CoroStep的co_yieldtuple{depth,pos.x,pos.y};这一行代码每次向调用者返回一组数据，表示当前的递归深度以及坐标，只要有这3个值，就能画出动画。
如果是控制台程序不也可以直接将这3个值打印出来，我实现算法的代码和实现动画的代码是完全分离的。
直接控制台调用这样：
intmain(){HorseJump5,6horse;autog=horse.CoroStep(0,XY{4,0});for(auto[depth,x,y]:g){cout"corostep:"x","y"\n";}}
关乎Qt动画的制作我这里不想解释，就是向GraphicsScene中添加或者删除直线，我对Qt的了解就一些皮毛，但是用来展示这类问题完全足够。
用兴趣的可以学一点Qt，哪怕只是一点皮毛，也已经非常有用。在C++中面向对象的地位并不高，就连STL都不是面向对象的，想要学到面向的知识和思想，Qt是一个很好的领域。
分治算法在前面写的StepAll函数中，对于9x10的棋盘，永远也算不出答案，但是对于很小的棋盘，很短时间内就能算出答案。
于是可以将棋盘分成几个小块，只要每个小块都满足「从任何一个点出发，不重复地经过其它所有点」的特征，将每个小块的路径算出来以后，再连起来即可。
经过简单的测试，我发现分成两个5x6的小块和一个3x10的小块，可以满足这个特征。如下所示：
这个算法本身怎么实现呢？如果不做动画的话可以在出发点所在的小块中调用StepAll，找到一个「结束点能够跳到相邻的小块」的一个解，然后进入相邻的小块再调用StepAll，直到3块都调用完毕为止。
为了实现动画，显示出实时路径，只要之前的Valid和Neighbour函数与当前所在的小方块结合起来即可。每次递归所在的depth必定在固定的小方块之中，判断起来很简单。
最终的效果如下，可以明确地看到，遍历的路径被分割在三个小方块之中。
这是我第一次用分治法解决马踏棋盘的问题，由于时间的原因，方法不一定是最简，但是这个思路是一个很好的方向，大家自己去研究。如果我以后发现更简单的方法，我会将代码更新到github里面。
相关的代码依然在github/franktea/treehouse与标题同名的目录中。
后记在20多年前第一次实现马踏棋盘之后不久，我就认识到，只学编程语言，距离程序员的要求还远远不够，接下去还要学习数据结构与算法。几个月以后，我就会用贪心法解这个问题了。
马踏棋盘对于我后来走上程序员的道路有深远的影响。我常常会回想当时的情形，可以知道自己究竟走了多远，也提醒自己当初为何要出发。
欢迎