N皇后问题

发表于 | 分类于 | 阅读次数：

题目描述

如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击（皇后攻击范围为横、竖以及对角线），输出所有可能的放置情况，皇后以Q表示。

示例

输入n为4时，输出：

1
2
3
4
5
6
7
8
9
10
11
[
 [".Q..",  // 解法 1
  "...Q",
  "Q...",
  "..Q."],

["..Q.",  // 解法 2
  "Q...",
  "...Q",
  ".Q.."]
]

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
public class NQueens {

    public static List<List<String>> solveNQueens(int n) {
        boolean[] col = new boolean[n];
        boolean[] left = new boolean[2*n];//2n长度防止越界
        boolean[] right = new boolean[2*n];
        List<String> solution = new ArrayList<>();
        List<List<String>> result = new ArrayList<>();
        dfs(0, col, left, right, solution, result);
        return result;
    }

    /**
     *
     * @param row 标记当前行数
     * @param column 标记当前行不可用的列,true为被占用
     * @param cl 标记当前行不可用的左对角格（每一元素代表一条约束公式，数组下标由行号列号共同决定）
     * @param cr 标记标记当前行不可用的右对角格
     * @param solution 一种可行答案
     * @param result 所有答案集
     */
    public static void dfs(int row, boolean[] column, boolean[] cl, boolean[] cr, List<String> solution, List<List<String>> result){

        if(row >= column.length){
            List<String> copyArray = new ArrayList<>(solution);
            result.add(copyArray);//将一种可行情况放入结果数组中
        }else{
            for(int i = 0; i < column.length; i++){
                int l = 2*column.length - i - row -1;//左斜约束
                int r = i - row +column.length;//右斜约束
                if(!column[i] && !cl[l] && !cr[r]){
                    char[] pointStr = new char[column.length];
                    Arrays.fill(pointStr, '.');//填充"."
                    pointStr[i] = 'Q';//一旦放入Q该层遍历完成
                    String rowStr = new String(pointStr);
                    solution.add(rowStr);
                    /**
                     * 更新标记不可用的数组
                     */
                    column[i] = true;cl[l] = true;cr[r] = true;
                    dfs(row+1, column, cl, cr, solution, result);//递归进入下一行
                    /**
                     * 用于回溯时清除标记数组
                     */
                    solution.remove(rowStr);
                    column[i] = false;cl[l] = false;cr[r] = false;
                }
            }
        }
    }



    public static void main(String[] args) {
        List<List<String>> result = NQueens.solveNQueens(4);
        for (List<String> one : result) {
            for (String row : one) {
                System.out.println(row);
            }
            System.out.println();
        }
    }
}