Leetcode(51) N-Queens

发表于 | 分类于

Description

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

img

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens’ placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

解法

经典的算法问题：N皇后问题。先解释一下：皇后不能同时出现在同一列，同一行或在同一条斜边上。为了找出所有可能的摆放，我们按行进行搜索，每一行寻找一个可以摆放的位置，如果合法，则进行下一行的搜索，当那一行不存在合法的摆放时，回溯归位。就是典型的回溯法解题啦~此题的关键在于数据结构的设计，巧妙地使用一维数组记录每一行皇后的j坐标可以将算法的设计大大简化。

具体代码如下：

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
class Solution {
    List<List<String>> res = new ArrayList<>();

    public List<List<String>> solveNQueens(int n) {
        //jpos[i]中存第i行中皇后摆放的纵坐标
        int[] jpos = new int[n];
        searchline(0, n, jpos);
        return res;
    }

    void searchline(int k, int n, int[] jpos) {
        //终止条件
        if (k == n) {
            List<String> s = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                StringBuffer tmp = new StringBuffer("");
                for (int j = 0; j < n; j++) {
                    if (j == jpos[i]) {
                        tmp.append("Q");
                    } else {
                        tmp.append(".");
                    }
                }
                s.add(tmp.toString());
            }
            res.add(s);
            return;
        }
        //依次选择j列的位置进行当前行的摆放
        for (int j = 0; j < n; j++) {
            jpos[k] = j;
            //合法则对下一行进行搜索
            if (canplace(k, jpos)) {
                searchline(k + 1, n, jpos);
            }
            //回溯还原
            jpos[k] = 0;

        }
    }

    //判断第k行的插入是否可行
    Boolean canplace(int k, int[] jpos) {
        for (int i = 0; i < k; i++) {
            if (jpos[i] == jpos[k] || Math.abs(jpos[i] - jpos[k]) == Math.abs(k - i)) {
                return false;
            }
        }
        return true;
    }
}