Nameless Site

But one day, you will stand before its decrepit gate,without really knowing why.

0%

n皇后

Posted on In , ,
Symbols count in article: 2k Reading time ≈ 2 mins.

来自Leetcode第51题n皇后

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

img

上图为 8 皇后问题的一种解法。

给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。

每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
输入: 4
输出: [
 [".Q..",  // 解法 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // 解法 2
  "Q...",
  "...Q",
  ".Q.."]
]
解释: 4 皇后问题存在两个不同的解法。

回溯

逐行放置皇后，检查第y列和(x,y)所在的两条斜线上是否有皇后即可。

  1. 检查第y列是否有皇后，比对纵坐标即可；
  2. 检查(x,y)所在的两条斜线上是否有皇后：
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>> que = new ArrayList<>();
    public List<List<String>> solveNQueens(int n) {
        char[][] board = new char[n][n];
        for(int i = 0 ; i < n ; i++)
            for(int j = 0 ; j < n ;j++)
                board[i][j] = '.';  //棋盘初始化
        int[] queens = new int[n];
        for(int i = 0 ; i < n ; i++)
            queens[i] = -1;  //皇后位置初始化
        backtrack(board,0,queens);
        return que;
    }

    private void backtrack(char[][] board,int x,int[] queue){
        if(x == board.length){
            //有效解
            List<String> list = new ArrayList<>();
            for(char[] row : board)
                list.add(new String(row));
            que.add(list);
            return;
        }
        for(int y = 0 ; y < board.length;y++){
            if(can(board,x,y,queue)){
                board[x][y] = 'Q';
                queue[x] = y ;// 放置皇后
                backtrack(board,x + 1,queue); //开始回溯
                //取消上一次的尝试
                board[x][y] = '.';
                queue[x] = -1;
            }
        }
    }

    //检查能否放置皇后
    private boolean can (char[][] board,int x,int y,int[] queen){
        if(y == board.length)
            return false;
        int dx,dy;
        for(int i = 0 ; i < x; i++){
            dy = y - queen[i];
            if(dy == 0)
                return false;  //同一列上有皇后
            dx = x - i;
            if(dx == dy || dx == -dy)  //对角线
                return false;
        }
        return true;
    }
}

位运算

补一个位运算的版本，看的不是很懂，不过这是针对下一题就总共解法的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int totalNQueens(int n) {
        dfs(n, 0, 0, 0, 0);
        return this->res;
    }
    
    void dfs(int n, int row, int col, int ld, int rd) {
        if (row >= n) { res++; return; }
        
        int bits = ~(col | ld | rd) & ((1 << n) - 1);
        while (bits > 0) {
            int pick = bits & -bits;
            dfs(n, row + 1, col | pick, (ld | pick) << 1, (rd | pick) >> 1);
            bits &= bits - 1;
        }
    }

private:
    int res = 0;
};