leetcode51-52.N-Queens

发表于 更新于 分类于 ，

题目要求

1
The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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.

For example,
There exist two distinct solutions to the 4-queens puzzle:

[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

这里的王后相当于国际围棋的王后，该王后一共有三种移动方式：水平、垂直，对角线。问要如何将n个王后布局在n*n的棋盘中保证她们不会互相伤害捏？

思路一：利用Set和Map

利用动态编程的思想。只要当前列，以及左对角线和右对角线都没有被占用的话，就可以在当前位置上暂时填上一个值。并将当前的临时结果作为下一轮的输入进行下一轮的预判。
在这里我们用Map<Integer, Integer>存储每一行填入Q的列数，用Set存储占据的对角线。

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
public List<List<String>> solveNQueens(int n) {
    List<List<String>> result = new ArrayList<List<String>>();
    if(n==0){
        return result;
    }
    //记录左右对角线情况
    Set<Integer> leftCordinal = new HashSet<Integer>(), rightCordinal = new HashSet<Integer>();
    Map<Integer, Integer> current = new HashMap<Integer, Integer>();
    solveNQueens(result, current, leftCordinal, rightCordinal, n);
    return result;
}

public void solveNQueens(List<List<String>> result, Map<Integer, Integer> current, Set<Integer> leftCordinal, Set<Integer> rightCordinal, int n){
    if(current.size() == n){
        List<String> currentResult = new ArrayList<String>();
        StringBuilder s = new StringBuilder();
        for(int i = 0 ; i<n ; i++){
            s.append(".");
        }
        for(int i = 0; i<n ; i++){
            s.setCharAt(current.get(i), 'Q');
            currentResult.add(s.toString());
            s.setCharAt(current.get(i), '.');
        }
        result.add(currentResult);
        return;
    }
    int row = current.size();
    if(row == 0){
        for(int i = 0 ; i<n ; i++){
            current.put(row, i);
            leftCordinal.add(row+i);
            rightCordinal.add(i-row);
            solveNQueens(result, current, leftCordinal, rightCordinal, n);
            leftCordinal.remove(row+i);
            rightCordinal.remove(i-row);
        }
    }else{
        for(int i = 0 ; i<n ; i++){
            if(current.containsValue(i) || leftCordinal.contains(row+i) || rightCordinal.contains(i-row)){
                continue;
            }
            current.put(row, i);
            leftCordinal.add(row+i);
            rightCordinal.add(i-row);
            solveNQueens(result, current, leftCordinal, rightCordinal, n);
            leftCordinal.remove(row+i);
            rightCordinal.remove(i-row);
        }
    }
    current.remove(row);
}

在这里其实可以用boolean[]代替Set，用简单值类型的数组代替复杂的数据结构往往可以提高性能。

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
public List<List<String>> solveNQueens2(int n) {
    List<List<String>> result = new ArrayList<List<String>>();
    if(n==0){
        return result;
    }
    //记录左右对角线情况
    boolean[] leftCordinal = new boolean[n*2-1], rightCordinal = new boolean[n*2-1];
    Map<Integer, Integer> current = new HashMap<Integer, Integer>();
    solveNQueens2(result, current, leftCordinal, rightCordinal, n);
    return result;
}

public void solveNQueens2(List<List<String>> result, Map<Integer, Integer> current, boolean[] leftCordinal, boolean[] rightCordinal, int n){
    if(current.size() == n){
        List<String> currentResult = new ArrayList<String>();
        StringBuilder s = new StringBuilder();
        for(int i = 0 ; i<n ; i++){
            s.append(".");
        }
        for(int i = 0; i<n ; i++){
            s.setCharAt(current.get(i), 'Q');
            currentResult.add(s.toString());
            s.setCharAt(current.get(i), '.');
        }
        result.add(currentResult);
        return;
    }
    int row = current.size();
    for(int column = 0 ; column<n ; column++){
        if(current.containsValue(column) || leftCordinal[row+column] || rightCordinal[column-row+n-1]){
            continue;
        }
        current.put(row, column);
        leftCordinal[row+column] = true;
        rightCordinal[column-row+n-1] = true;
        solveNQueens2(result, current, leftCordinal, rightCordinal, n);
        leftCordinal[row+column] = false;
        rightCordinal[column-row+n-1] = false;;
    }
    current.remove(row);
}

将Map类型也转化一下？##

我们发现，每一次得到一个结果时，都需要将相应的值转化为String然后添加的数组再添加到结果集中。但是其实这些String 的值都是重复利用的。毕竟Q可能位于0~n-1的任何位置上，也就是说有n个固定的互异字符串，但是一个结果上一定会包含所有这些字符串。这里我们进行了进一步的优化，**将Map转化为boolean[]+int[]**，其中bool数组用来记录该列是否被占领，int数组用来记录该行占领了那一列。

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
public List<List<String>> solveNQueens2(int n) {
    List<List<String>> result = new ArrayList<List<String>>();
    if(n==0){
        return result;
    }
    //记录左右对角线情况
    boolean[] leftCordinal = new boolean[n*2-1], rightCordinal = new boolean[n*2-1];
    Map<Integer, Integer> current = new HashMap<Integer, Integer>();
    solveNQueens2(result, current, leftCordinal, rightCordinal, n);
    return result;
}

public void solveNQueens2(List<List<String>> result, Map<Integer, Integer> current, boolean[] leftCordinal, boolean[] rightCordinal, int n){
    if(current.size() == n){
        List<String> currentResult = new ArrayList<String>();
        StringBuilder s = new StringBuilder();
        for(int i = 0 ; i<n ; i++){
            s.append(".");
        }
        for(int i = 0; i<n ; i++){
            s.setCharAt(current.get(i), 'Q');
            currentResult.add(s.toString());
            s.setCharAt(current.get(i), '.');
        }
        result.add(currentResult);
        return;
    }
    int row = current.size();
    for(int column = 0 ; column<n ; column++){
        if(current.containsValue(column) || leftCordinal[row+column] || rightCordinal[column-row+n-1]){
            continue;
        }
        current.put(row, column);
        leftCordinal[row+column] = true;
        rightCordinal[column-row+n-1] = true;
        solveNQueens2(result, current, leftCordinal, rightCordinal, n);
        leftCordinal[row+column] = false;
        rightCordinal[column-row+n-1] = false;;
    }
    current.remove(row);
}

N-Queens II 题目和实现

Follow up for N-Queens problem.

Now, instead outputting board configurations, return the total number of distinct solutions.

相比于I，这里不要去获得具体的答案，只需要返回解答的数量即可。其实比I要简单。思路还是相同的，利用迭代实现自顶向下的动态编程
代码如下：

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
public class NQueens_51 {
    //将map数据结构int[]+boolean[]+lines[]+
    List<List<String>> res;
    boolean[] col, lslash, rslash;
    int[] p;
    int n;
    String[] lines;
    private void dfs(int i) {
        if(i == n) {
            List<String> board = new ArrayList<String>();
            for(int j = 0; j < n; j++) {
                board.add(lines[p[j]]);
            }
            res.add(board);
            return;
        }
        
        for(int j = 0; j < n; j++) {
            if(!col[j] && !lslash[i+j] && !rslash[j-i+n-1]) {
                col[j] = true;
                lslash[i+j] = true;
                rslash[j-i+n-1] = true;
                p[i] = j;
                dfs(i+1);
                col[j] = false;
                lslash[i+j] = false;
                rslash[j-i+n-1] = false;
            }
        }
    }
    public List<List<String>> solveNQueens3(int n) {
        this.n = n;
        res = new ArrayList<List<String>>();
        col = new boolean[n];
        lslash = new boolean[2*n-1];
        rslash = new boolean[2*n-1];
        p = new int[n];
        char[] line = new char[n];
        lines = new String[n];
        for(int i = 0; i < n; i++) {
            line[i] = '.';
        }
        for(int i = 0; i < n; i++) {
            line[i] = 'Q';
            lines[i] = String.copyValueOf(line);
            line[i] = '.';
        }
        dfs(0);
        return res;
    }

}