八皇后问题算法详解

八皇后问题，是一个古老而著名的问题，是 回溯算法 的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 高斯 认为有76种方案。1854年在柏林的扰游象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。

本文缓帆销的主要描述的是基于回溯算法轿备思想的求解算法，并尽可能在细节上给予读者直观展示，以使得读者可以有更好的理解。抛砖引玉，如有错误请不吝赐教。

算法的关键在于用一个二维数组chess [ ] [ ] 来记录每一个位置(第 i 行第 j 列)是否合法（行列对角线上没有填皇后，对应于数组 chess [ i ] [ j ] 为 0），用一个一维数Queenplace [ ] 组来记录每一行上皇后的列标（比如Queenplace [ row ] =column 表示第 row 行第 column 列填入皇后）。

行数 i 从第一行开始，遍历每一列 j ，如果chess [ i ] [ j ] 为0，那么说明此位置可以填入皇后，则将chess中与此位置同行同列同对角线的value自增 1 并且在 数组Queenplace 中记录相应的坐标。然后递归计算每一行直到最后一行成功填入皇后并在此时打印棋盘 。最后进行回溯，恢复chess [ ] [ ] ，将chess中与此位置同行同列同对角线的value自减 1 并继续进行下一列的计算。

Left[15],Right[15]

是用来标记对角线的上是否有皇后。

分别表示者弯\这个方向和/这个方向。

你会发现，对于2维数组下标来说。

/这个方向的下标它的和一样，就说明在一条\线上。

\这个方向就是它的差值是一样的。由于会有负值，所以题目中加了个7.

Left[n+h]=true

Right[n-h+7]=true

八皇后问题，的解法是个典型的回溯求解。

每一次针对一行，然后改行有8个位置可供选择，然后根据

int

col[8],Left[15],Right[15]

这个标识选择性的放皇后。然后在递归进入下一行。

它的搜索过程类似深度优先搜索。只不过稿辩它搜索的时候，会判断当前节点是否可能是解，不是解，它就不扩首敬闷展了。

---