算法八皇后问题理解回溯法

　　回溯算法从空解开始，并逐步扩展该解。搜索递归地通过各种不同的构造解决方案的路径。
　　例如，考虑计算n皇后问题：在nn的棋盘上放置彼此不受攻击的n个皇后。
　　（皇后可以攻击在同一行、同一列、同一斜线上的棋子）
　　按以上规则：同一行或同一列或同一斜线上只能有一个皇后，同一行或同一列上必须有一个皇后。
　　n皇后问题的解空间是一棵n叉树，树的深度为n。
　　当n为4时，有两种可能的解决方案：
　　八皇后问题对于每一行是否可以放置皇后，可用一个规模为8的循环去判断。每一行的判断操作相同，如果操作完成了8行（放置了8个皇后），便求出了一个解。所以该问题可以用递归去做。如果某一行全部位置无法放置皇后时，没必要继续深入，可以回溯到上一步，也就是使用回溯法。对于非尾递归，递归函数回退时，递归点后面的代码就是递归函数回退后执行的部分。对于八皇后问题，上述的循环可以判断某行下一列是否可以放置皇后，而上一列放置皇后的操作进行逆操作后便完成了回溯（递归有天然的回退阶段）。
　　八皇后问题的暴力枚举搜索或递归解法会形成一个棵8叉完全树，回溯解法可以通过约束条件避免一些搜索继续深入，形成一棵8叉不完全树。
　　为简便起见，我们可以用四皇后问题去理解，然后泛化到一般的情况。
　　在底层，前三种配置是非法的，因为皇后们互相攻击。然而，第四种配置是有效的，可以通过在棋盘上再放置两个皇后来扩展到完整的解决方案。只有一种方法可以放置剩下的两个皇后。
　　如下面左图所示：
　　从y0，x0开始，search（0）递归调用search（1）（x2，y1），递归调用search（2）
　　当y2，x3时，递归函数search（2）执行完毕，回退到search（1），x0，逆操作，循环到x3
　　codedemo：includestdio。hdefinen4intcolumn〔n2〕｛0｝；intdiag1〔n2〕｛0｝；intdiag2〔n2〕｛0｝；intcount0；voidsearch（inty）｛if（yn）｛count；return；｝for（intx0；xn；x）｛if（column〔x〕diag1〔xy〕diag2〔xyn1〕）continue；column〔x〕diag1〔xy〕diag2〔xyn1〕1；search（y1）；column〔x〕diag1〔xy〕diag2〔xyn1〕0；回退时的逆操作，下一轮循环x｝return；｝main（）｛search（0）；printf（d，count）；getchar（）；｝n4，2n8，92n16，14772512
　　搜索从调用search（0）开始。棋盘的大小为nn，代码计算要计数的解决方案数。
　　代码假设棋盘的行和列编号从0到n1。当使用参数y调用函数搜索时，它会在行y上放置皇后，然后使用参数y1调用自身。然后，如果yn，则已找到解决方案，变量count增加1。
　　数组column跟踪包含皇后的列，数组diag1和diag2跟踪对角线。不允许在已包含皇后的列或对角线中添加其他皇后。例如，44棋盘编号如下，当x、y取不同的值时，对应列方向column〔x〕、方向上diag1〔xy〕、方向上diag2〔xy41〕的取值为0时表示无皇后：
　　y2，x3
　　回溯。
　　y1，x3
　　count1。
　　回溯到下面绿色点：
　　继续逐步回溯：
　　count2。
　　继续逐步回溯，最后count2。
　　可视化操作的网页地址：
　　https：pythontutor。comrender。htmlmodedisplay
　　End