【CPP】递归与回溯入门·八皇后问题

八皇后问题，一个经典的回溯算法问题。在8*8的国际象棋棋盘上如何才能放上八只皇后棋子，使它们彼此不会互相攻击到。皇后，是能攻击到以自己为中心的横线竖线和正斜线的强大棋子，在这样的棋盘上摆放8个皇后，这个程序就是要解决到底有多少种摆放法。历史上有那么多的大师研究这个问题，而如今利用计算机强大的计算能力，我们遍历一次棋盘——不到5ms的时间——便得到了结果，一共92种。

递归，简单的说就是让子程序（函数）在运行中调用其他的子程序，其中最常用的便是让自己调用自己来达到简化问题的目的。大部分编程都支持递归，在这里我们用C++完成这个问题。

回溯，顾名思义，就是像走迷宫一样，先随便找一条路开始走，当碰到死路时倒回到岔道口选择别的方向，也可以理解为电影《盗梦空间》中的梦中梦，不断一层层深入，直到最里层的梦找到了自己真正想要的东西时，带着答案一层层退出，本质上是一种基于栈的广度搜索，由于递归调用本身就是利用到系统内部的栈，所以回溯法特别适合用递归来编写。

现在来说八皇后，这个程序的思路其实并不复杂，网上其他地方也能看到各种解决它的奇技淫巧，（知乎上还有“如何在10行内写出八皇后”的问题hhh），在这里我写出自己的比较简单（麻烦）的算法。首先，初始化一个8*8的二维数组作为棋盘，全部用0填充表示空棋盘。然后将我们的目标函数参数写入x皇后x轴),num(皇后编号，且代表y轴，由于每个皇后都可攻击自己的那一行，所以每行只能有一个皇后)，map代表传入的棋盘。然后我们传入初始棋盘，皇后编号写入-1代表是一切的开始，目标函数的返回值是此问题的解的总数，也是每个递归出来的小问题的解的数。

然后在我们的目标函数中，我们首先初始化一个tempmap二维数组来暂时储存刚才传入的棋盘，目的是让程序在递归时可以倒退到棋子未放下的情况。然后就是递归的开始，从0开始，我们遍历第一行的每个位置作为第一个皇后的位置，然后传入num+1(这里也就是0)作为下一次函数调用时的参数。

然后是递归的主部分，当棋盘被遍历到的地方是可下位置是，我们放下一个皇后，利用循环将棋盘上皇后的攻击范围用1标识（abs函数是取绝对值，在math.h头文件中），然后将皇后自己的位置用2标识。当标识攻击范围时检测到其他皇后的话，返回0代表这层的递归得不到八皇后的其中一个解并跳出这一层层递归，没有必要接下去深入搜索了，所以总解数sum+=0。

接下来，当皇后找到了自己真正可放置的地方后，先检测是不是第8个皇后，如果是则结束这底层的递归，返回1让得到的总解数+1。如果不是的话，就像一开始一样，开始遍历下一行，进入下一层的递归，直到最深处。

然后当层递归全部结束是结束了，返回刚才下层递归得到了解的总数sum并传递给上层的递归，直到最表层（-1）。

通过递归，我们可以用很短的代码写出这样一个如果用纯循环会很复杂的程序，我们验证一下结果，为了直观，我们还可以在每次返回1时加上打印棋盘的代码，输出八皇后的详细解。

结果：92种。

这里给递归函数的代码，比起其他人的代码还是很长，而且有点丑hh。

啊，暑假就要过半了，啊。