八皇后问题：是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848 年提出：在 8×8 格的国际象棋上摆放八个皇后，使其不能互相攻击，即： 任意两个皇后都不能处于同一行 、 同一列或同一斜线上，问有多少种摆法(92)。
根据排列组合：C64 取8，一共有4.426×10的9次方种方案
不难发现，每一行只能放一个皇后，所以8！=40320种方案
然后在40320种方案中，挑选符合题意的方案！
八皇后地图
根据条件我们可知每行每列最多都只能有一个皇后，这样可以在一定程度上缩减问题的规模。在第一行的某一列选择放置一个皇后，共有8种不同的选择，而第二行只能选择剩下的7列，也就是7种选择，剩下每一行的选择都会递减1， 那么总共可供选择的方案有8的阶乘种，已经是一种远优于暴力解法的解法， 但是这个阶乘的时间复杂度恐怕也难以令人接受，还有更优的解法吗？
- 回溯递归法
- 回溯非递归法
- 生成遍历法
回溯递归法基本框架
基本思路：
- 第一个皇后先放第一行第一列
- 第二个皇后放在第二行第一列、然后判断是否 OK， 如果不 OK，继续放在第二列、第三列、依次把所有列都 放完，找到一个合适
- 继续第三个皇后，还是第一列、第二列……直到第 8 个皇后也能放在一个不冲突的位置，算是找到了一个正确 解
- 当得到一个正确解时，在栈回退到上一个栈时，就会开始回溯，即将第一个皇后，放到第一列的所有正确解， 全部得到.
- 然后回头继续第一个皇后放第二列，后面继续循环执行 1,2,3,4 的步骤
小结：当我们选择了第一个皇后的位置之后，与其处于同行同列同斜线的位置便都无法被选择，第二个皇后只能放在未被第一个皇后所辐射到的位置上，接着放置第三个皇后，同样不能放在被前两个皇后辐射到的位置上，
- 若此时已经没有未被辐射的位置能够被选择，也就意味着这种摆法是不可行的，我们需要回退到上一步，给第二个皇后重新选择一个未被第一个皇后辐射的位置，再来看是否有第三个皇后可以摆放的位置，如还是没有则再次回退至选择第二个皇后的位置，
- 若第二个皇后也没有更多的选择则回退到第一个皇后，重新进行位置的选择。
- 完成一次可行解即递归找到出口后，此时递归栈的栈顶会被弹出，次栈顶元素会被顶上，即下一行会继续搜索每列的位置，直到搜索到第一行所有列为止
图解
1.第一层递归，尝试在第一行摆放第一个皇后： 
2.第二层递归，尝试在第二行摆放第二个皇后（前两格被第一个皇后封锁，只能落在第三格）： 
3.第三层递归，尝试在第三行摆放第三个皇后（前四格被第一第二个皇后封锁，只能落在第五格）： 
4.第四层递归，尝试在第四行摆放第四个皇后（第一格被第二个皇后封锁，只能落在第二格）： 
5.第五层递归，尝试在第五行摆放第五个皇后（前三格被前面的皇后封锁，只能落在第四格）： 
6.由于所有格子都“绿了”，第六行已经没办法摆放皇后，于是进行回溯，重新摆放第五个皇后到第八格。 
7.第六行仍然没有办法摆放皇后，第五行也已经尝试遍了，于是回溯到第四行，重新摆放第四个皇后到第七格。 
8.继续摆放第五个皇后，以此类推…
代码
效果
使用 int Q[8][8]; 存储八皇后的数据，看起来比较直观，但是深入思考一下，每一行只存放1个数据，这样使用二维数组会造成空间的浪费，所以可使用 int Q[10]; 来存储八个皇后的位置，比如 Q[0]：第0行皇后的列数 Q[1]：第1行皇后的列数 …
用一个一维数组即可解决问题. arr[8] = {0 , 4, 7, 5, 2, 6, 1, 3} //对应 arr 下标 表示第几行，即第几个皇后，arr[i] = val , val 表示第 i+1 个皇后，放在第 i+1 行的第 val+1 列
改进一：使用一维数组
因为每放置一个皇后需要移动到下一行，不需要对该行判断，只需要对列主副对角线进行判断即可； 如何用一个值代表一条线呢？ 平面坐标系中的副对角线实际上也就是二维数组中的主对角线
所以得出:
任意一条副对角线公式为 y = x + b => b = y - x + n(数组中没有负数所以平移n位) 任意一条主对角线公式为 y = - x + b => b = x + y
主对角线: rup[x+y] 副对角线: lup[y-x+n]
b 是任意一条主副对角线到（0，0）的截距
那我们就可以通过一个一维数组来表示二维数组中的每一条主副对角线
至多会有2*n条主或副对角线，所以只需要开2n的空间就可以了 
改进二：使用主副对角线判断
回溯法从问题本身出发，寻找可能出现的所有情况。和穷举法类似，但回溯法如果发现情况不存在就返回上一步继续尝试其他 分支，直到找到所有解或者搜索完所有分支为止
其策略为：能进则进，不能进则换，不能换则退
回溯非递归法基本框架(就是一般的回溯法)
回溯非递归法代码
搞清楚了八皇后问题下面可以开发个八皇后小游戏验证是否正确
先看效果图
一：绘制棋盘 
二 放置皇后 
三 验证八皇后问题
先看个错误的 
在测试个通过的 正确的一种解法-- 1 5 8 6 3 7 2 4 
完整代码