一 问题描述

在 n * n 的棋盘上放置了彼此不受攻击的 n 个皇后。按照国际象棋的规则，皇后可以攻击与之在同一行、同一列、同一斜线上的棋子。请在 n * n 的棋盘上放置 n 个皇后，使其彼此不受攻击。

如果棋盘如下图所示，我们在第 i 行第 j 列放置一个皇后，那么第 i 行其他位置，第 j 列其他位置，同一斜线上的其他位置，都不能再放皇后。

不可能杂乱无章地尝试每个位置，需要有策略地求解，可以以行为主导。

1 在第 1 行第 1 列放置第 1 个皇后。

2 在第 2 行放置第 2 个皇后。第 2 个皇后的位置不能与第 1 个皇后同列、同斜线，不用再判断是否同行，因为每行只放置一个，本来就已经不同行。

3 在第 3 行放置第 3 个皇后。第 3 个皇后的位置不能与前 2 个皇后同列、同斜线。

4 ......

5 在第 t 行放置第 t 个皇后。第 t 个皇后的位置不能与前 t-1 个皇后同列、同斜线。

6 ......

7 在第 n 行放置第 n 个皇后。第 n 个皇后的位置不能与前 n-1 个皇后同列、同斜线。

二 算法设计

1 定义问题的解空间

n 皇后问题的解的形式为 n 元组：{x1，x2，x3...xi...xn}，分量 xi 表示第 i 个皇后放置在第 i 行第 xi 列，xi 的取值为 1,2...n。例如 x2=5，表示第 2 个皇后被放置为第 2 行第 5 列。

2 解空间组织结构。

n 皇后问题的解空间是一棵 m（m=n） 叉树，树的深度为 n，如下图所示。

3 搜索解空间

3.1 约束条件

在第 i 行放置第 t 个皇后时，第 t 个皇后的位置不能与前 t-1 个皇后同列、同斜线。第 i 个皇后与第 j 个皇后不同列，即 xi != xj，并且不同斜线 |i-j| != |xi-xj|。

3.2 限界条件

该问题不存在放置方案是否好坏的情况，所以不需要设置限界条件。

3.3 搜索过程

从根开始，以深度优先搜索的方式进行搜索。根节点是活节点并且是当前扩展节点。在搜索过程中，当前扩展节点沿纵深方向移向一个新节点，判断该新节点是否满足隐条件，如果满足，则新节点成为活节点，并且成为当前扩展节点，继续深一层的搜索，如果不满足，则换到该节点的兄弟节点继续搜索；如果新节点没有兄弟节点，或者其它兄弟节点已全部搜索完毕，则扩展节点称为死节点，搜索回溯到其父节点继续进行。搜索到问题的根节点变成死节点时为止。

三 图解

在 4 * 4 的棋盘商放置 4 个皇后，使其不受攻击。

1 开始搜索第 1 层

2 扩展节点 2

3 扩展节点 3

节点3是死节点，回溯到节点 2。

4 重新扩展节点 2

5 扩展节点 4

6 扩展节点5

节点 5 是死节点，向上回溯到节点 4。

7 继续扩展节点4

节点 4 是死节点，向上回溯到节点 2，节点 2 的所有孩子都考察完，也称为了死节点。向上回溯到节点 1。

8 继续扩展节点 1

9 扩展节点6

10 扩展节点7

11 扩展节点 8

12 扩展节点9

t > n,找到一个可行解，用 bestx[] 保存当前可行解{2,1,4,3}。节点 9 称为死节点，向上回溯到节点 8。

13 继续扩展节点 8

不符合约束，节点 8 成为死节点，向上回溯到节点 7。

14 继续扩展节点 7

不符合约束，节点 7 成为死节点，向上回溯到节点 6。节点 6 的所有孩子都考察完，它也成为了死节点。向上回溯到节点 1。

15 继续扩展节点 1

16 扩展节点 10

17 扩展节点 11

18 扩展节点 12

19 扩展节点13

t > n,找到一个可行解，用 bestx[] 保存当前可行解{3,1,4,2}。节点 13 称为死节点，向上回溯到节点 12。

20 继续扩展节点 12

不满足约束，成为死节点，向上回溯到节点 11，节点 11 的所有孩子都考察完，成为死节点。向上回溯到节点 10。

21 继续扩展节点 10

不满足约束，称为死节点，向上回溯到节点 1.

22 继续扩展节点 1

23 扩展节点 14

24 扩展节点 15

25 扩展节点 16

不满足约束，成为死节点，回溯到节点 15。

26 继续扩展节点 15

不满足约束，成为死节点，回溯到节点 14。

27 继续扩展节点 14

28 扩展节点 17

不满足约束，成为死节点，回溯到节点 14。回溯到节点 14。

29 继续扩展节点 14

不满足约束，成为死节点，回溯到节点 1。

30 对节点 1 的所有孩子均考察完毕并成为死节点，算法结束。

四 算法实现说明

1 约束函数

在第 t 行放置第 t 个皇后时，第 t 个皇后与前 t-1 个皇后不能同列或同斜线。如果有一个成立，则第 t 个皇后不可以被放置在该位置。x[t] == x[j] 表示第 t 个皇后和第 j 个皇后同列。t-j == abs(x[t]-x[j]) 表示第 t 个皇后与第 j 个皇后同斜线。

2 按约束条件搜素求解

t 表示当前扩展节点在第 t 层。如果 t>n,则表示已经到达叶子节点，记录最优值和最优解，返回。否则，分别判断 n 个分支，x[t]=i;判断每个分支是否满足约束条件，如果满足，则进入下一层，否则考察下一个分支（兄弟节点）。

五 代码

package com.platform.modules.alg.alglib.p924;
 
public class P924 {
    private final int M = 105;
    // n表示n个皇后
    private int n;
    // x[i]表示第i个皇后放置在第i行第x[i]列
    int x[] = new int[M];
    // countn 表示 n 皇后问题可行解的个数
    long countn;
 
    public String output = "";
 
    public String cal(String input) {
        n = Integer.parseInt(input);
        countn = 0;
        Backtrack(1);
        output += countn;
        return output;
    }
 
    // 判断第 t 个皇后能否放置在第 i 个位置
    boolean Place(int t) {
        boolean ok = true;
        for (int j = 1; j < t; j++)   //判断该位置的皇后是否与前面t-1个已经放置的皇后冲突
        {
            // 判断列、对角线是否冲突
            if (x[t] == x[j] || t - j == Math.abs(x[t] - x[j])) {
                ok = false;
                break;
            }
        }
        return ok;
    }
 
    void Backtrack(int t) {
        // 如果当前位置为 n,则表示已经找到了问题的一个解
        if (t > n) {
            countn++;
            // 打印选择的路径
            for (int i = 1; i <= n; i++)
                output += x[i] + " ";
            output += "\n";
        } else
            // 分别判断 n 个分支,特别注意 i 不要定义为全局变量,否则递归调用有问题
            for (int i = 1; i <= n; i++) {
                x[t] = i;
                if (Place(t))
                    Backtrack(t + 1); // 如果不冲突的话进行下一行的搜索
            }
    }
}

六 测试