摘要 八皇后问题是一个古老而著名的问题,是回溯算法的经典问题。该问题由高斯提出:在8*8的国际象棋上摆放8个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行,同一列或同一斜线上,问总共有多少种摆法。现代数学中,把八皇后问题当成一个经典的递归算法例题。

回溯法

下面我们尝试用回溯法解决八皇后问题。

回溯法实际上是一个类似枚举的搜索尝试过程。用回溯法解决问题的一般步骤是:

  1. 针对所给问题,确定问题的解空间
  2. 确定结点的扩展搜索空间
  3. 以深度优先方式搜索解空间,并在搜索过程中用剪枝函数避免无效搜索。

八皇后问题求解

从以上三点,来阐述八皇后问题的求解。从问题的定义出发,总结八个皇后之间满足以下关系:

  • 不在同一行
  • 不在同一列
  • 不在同一斜线上
  • 不在同一反斜线上

针对回溯法的一般步骤,我们需要先确定解空间。

从列的方向进行回溯(选择列向还是行向按自己习惯,思路一样),对于某一列col,我们确定解空间即为,当前列,八皇后能摆放的位置,即能摆放在哪一行。

对于当前列能摆放在哪一行的问题,需要参考前面的列所摆放的位置,具体分析如下:

如果当前列col=3,第2列摆放的皇后位置为第5行,那么我们可以确定第3列一定不能摆放的位置有:第5行,第6行和第4行,因为首先不能和第2列摆在同一行,所以一定不能摆在第5行,其次不能摆在与前一列第5行所在的斜线位置即第6行,再其次也不能摆在与前一列第5行所在的反斜线位置上,即不能摆在第4行。

这只是根据第2列的摆放位置来确定的局部解,还要根据第1列的摆放情况,才能最终确定第3列的皇后能摆放的位置,即当前的解空间。那么确定当前解空间可以归纳为以下算法:

我们用rows数组表示当前列所能放置的行的位置,rows是一个大小为8的boolean数组,rows[i]=false表示当前列第i行不能摆放,初始化下为所有行都能摆放即为true。

另外我们用cols数组表示每一列棋子摆放的行数,如以上第2列摆放在第5行可以表示为cols[2]=5。

在确定解空间的过程中,我们就是要根据当前列之前的所有列的cols来确定当前列的摆放位置。

  • 前1列摆放位置为第5行,那么当前不能摆放的行有:5,5+1,5-1
  • 前i列摆放位置为第row行,那么当前不能摆放的行有:row,row+i(row+i<8),row-i(row-i>=0)

以下函数就是根据当前列号以及当前cols数组确定当前列可以摆放的行的位置:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* [getAccessRows description]
* @param cols [array of every row num of queen in each col]
* @param col [current col]
* @return [current col can be placed in which rows]
*/

private static boolean[] getAccessRows(int[] cols, int col){
boolean rows[] = new boolean[QUEEN_NUM];
for(int i=0;i<QUEEN_NUM;i++){
rows[i] = true;// all rows can be placed
}
for(int i=0;i<col;i++){
int row = cols[i];
int d = col - i;// forward d col
rows[row] = false;
if((row+d) < QUEEN_NUM)
rows[row+d] = false;
if((row-d) >= 0)
rows[row-d] = false;
}
return rows;
}

有了当前列可以摆放的行位置数组,即确定了当前解空间,依据回溯法,确定扩展搜索空间,选的当前列的某一行作为当前最优解,进行深度优先搜索,回溯下一列能摆放的位置,直到确定所有列的摆放位置,即得到一组解,下面给出从当前列出发进行回溯的代码作为参考:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
* [solveEightQueen description]
* @param cols[] [array of row num of each col]
* @param col [current col]
*/

private static void solveEightQueen(int cols[], int col){
boolean rows[] = getAccessRows(cols, col);
for(int row=0; row<QUEEN_NUM; row++){
if(rows[row] == false)
continue;
cols[col] = row;
if(col == QUEEN_NUM - 1)
result_num++;
else
solveEightQueen(cols, col+1);
}
}

我们在主函数中从第0列开始进行回溯,可以得到共有92组解。

1
2
3
4
5
6
7
8
private static int result_num = 0;
public static final int QUEEN_NUM = 8;

public static void main(String[] args){
int cols[] = new int[QUEEN_NUM];
solveEightQueen(cols, 0);
System.out.println(result_num);
}

总结

从以上代码,可以发现回溯法可以轻松解决复杂的八皇后问题,回溯法的解决关键在于深度优先递归搜索。

我们可以将问题规模改为任意,即10皇后也可以适用。