【回溯算法】leetcode 51. N 皇后

51. N 皇后

题目描述

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

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

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

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

示例1：

输入： n = 4
输出： [[“.Q…”,“…Q”,“Q…”,“…Q.”],[“…Q.”,“Q…”,“…Q”,“.Q…”]]
解释： 如上图所示，4 皇后问题存在两个不同的解法。

示例2：

输入： n = 1
输出： [[“Q”]]

提示

• $1<=n<=9$

方法：回溯算法

解题思路

回溯模板：

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }
    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}
1
2
3
4
5
6
7
8
9
10
11

回溯三部曲：

• 确定回溯函数参数
  我依然是定义全局变量二维数组result来记录最终结果。

  参数n是棋盘的大小，然后用row来记录当前遍历到棋盘的第几层了。

  vector<vector<string>> result;
  void dfs(int n, int row, vector<string>& chessboard) 
  1
  2

• 确定终止条件
  当递归到棋盘最底层（也就是叶子节点）的时候，就可以收集结果并返回了

  if (row == n) {
  	result.push_back(chessboard);
  	return;
  }
  1
  2
  3
  4

• 确定单层遍历逻辑
  递归深度就是 row 控制棋盘的行，每一层里 for 循环的 col 控制棋盘的列，一行一列，确定了放置皇后的位置。

  每次都是要从新的一行的起始位置开始搜，所以都是从0开始。

  for (int col = 0; col < n; col++) {
  	if (isValid(row, col, chessboard, n)) { // 验证合法就可以放
      	chessboard[row][col] = 'Q'; // 放置皇后
      	dfs(n, row + 1, chessboard);
      	chessboard[row][col] = '.'; // 回溯，撤销皇后
  	}
  }
  1
  2
  3
  4
  5
  6
  7

• 验证棋盘是否合法
  按照如下标准去检验：

  1. 不能同行
  2. 不能同列
  3. 不能同斜线（45 度和 135 度角）

代码

class Solution {
public:
    vector<vector<string>> result;
    bool isValid(int row, int col, vector<string>& chessboard, int n) {
        // 检查列
        for(int i = 0; i < row; i++)
            if(chessboard[i][col] == 'Q')
                return false;
        // 检查45度角是否有皇后
        for(int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--)
            if(chessboard[i][j] == 'Q')
                return false;
        // 检查135度角是否有皇后
        for(int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++)
            if(chessboard[i][j] == 'Q')
                return false;
        return true;
    }
    void dfs(int n, int row, vector<string>& chessboard) {
        if(row == n) {
            result.push_back(chessboard);
            return;
        } 
        for(int col = 0; col < n; col++) {
            if(isValid(row, col, chessboard, n)) {
                chessboard[row][col] = 'Q';
                dfs(n, row + 1, chessboard);
                chessboard[row][col] = '.';
            }
        }
    }
    vector<vector<string>> solveNQueens(int n) {
        vector<string> chessboard(n, string(n, '.'));
        dfs(n, 0, chessboard);
        return result;
    }
};
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