一 问题描述
八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于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 并继续进行下一列的计算。
三 完整函数代码
public class EightQueen {
private int QUEEN_COUNT = 0; // 皇后的默认数量
private int[][] chess;// 分配8X8的数组，充当棋盘，存放皇后
private int count = 0;// 记录皇后的放置方法的总数
private int[] Queenplace;// 对于索引n, Queenplace[n]表示第n行的皇后放置位置是第Queenplace[n]列
public EightQueen(int n) {
this.QUEEN_COUNT = n;
this.count = 0;
this.chess = new int[QUEEN_COUNT][QUEEN_COUNT];
Queenplace = new int[QUEEN_COUNT];
}
public void putQueen() {
putQueen(0);
}
private void putQueen(int row0) {
int row = row0;// 行标
for (int column = 0; column < QUEEN_COUNT; column++) {
if (chess[row][column] == 0) {// 判断第row行、第column列是否可以放皇后
//因为之前的行都已填入皇后，所以只需要从下一行开始记录chess数组状态
for (int nextRow = row + 1; nextRow < QUEEN_COUNT; nextRow++) {
chess[nextRow][column]++;
if (column - nextRow + row >= 0) {
chess[nextRow][column - nextRow + row]++;
}
if (column + nextRow - row < QUEEN_COUNT) {
chess[nextRow][column + nextRow - row]++;
}
}
//记录皇后位置
Queenplace[row] = column;
// 如果是最后一行，则直接打印棋盘，并将摆放方法数加1
if (row == QUEEN_COUNT - 1) {
printQueen(++count);
} else // 否则递归继续计算下一行
{
putQueen(row + 1);
}
// 回溯chess状态，通过最外层循环进入下一列的计算过程
for (int rows = row + 1; rows < QUEEN_COUNT; rows++) {//
chess[rows][column]--;
if (column - rows + row >= 0) {
chess[rows][column - rows + row]--;
}
if (column + rows - row < QUEEN_COUNT) {
chess[rows][column + rows - row]--;
}
}
}
}
if (row == 0) { //这为递归的最顶层，说明程序结束 ，打印最终计数结果
System.out.println(QUEEN_COUNT + "皇后问题共有" + count + "个解.");
}
}
private void printQueen(int size) {// 打印皇后布局
System.out.println(QUEEN_COUNT + "皇后的第" + size + "个解是:");
System.out.println();
for (int row = 0; row < QUEEN_COUNT; row++) {
for (int column = 0; column < QUEEN_COUNT; column++) {
System.out.print(Queenplace[row] == column ? " * " : " - ");
}
System.out.println();
}
System.out.println();
}
public static void main(String[] args) {
EightQueen eq = new EightQueen(8);
eq.putQueen();
}
}
