LeetCode 51 N-Queens

Tag: LeetCode 回溯法 Posted on 2020-06-07 13:46:25 Edited on 2020-06-07 16:14:10 Views: 9

https://leetcode.com/problems/n-queens/

回溯算法解题套路框架

result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return

    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

问题分析

对于该问题,我们无非两种角度:

  1. 为每一个皇后选择一个位置。
  2. 为每一个位置选择是否放置皇后。

为每一个皇后选择一个位置

首先想一下该思路的暴力解法: 每个皇后有 n*n 的选择(我们后续再考虑剪枝),一共 n 个皇后,亦即我们要选择 n 次,复杂度 O(n^(2n))。

但是这有个重复的问题,从搜索树的根节点到叶节点虽然路径可能不同,但是可以对应同一个解。

我们可以通过给皇后定义一个顺序来解决这个解重复的问题,考虑到每一行每一列都有且只有一个皇后,那么我们增加一个第 i 个皇后只能在第 i 行的限制就好。

这个时候每个皇后有 n 个选择,复杂度降到了 O(n^n)。

接下来我们考虑每一列有且只有一个皇后,那么根据这一点,一共有 n! 种选择, 这些选择已经满足所要求的不能同行列的要求了,之后我们再进行筛选,剔除在同一个斜线上有不止一个皇后的方案即可。

代码

class Solution {
public:
    vector<vector<string>> solutions;
    vector<vector<string>> solveNQueens(int n) {
        vector<string> board(n, string(n, '.'));
        backtrack(board, 0);
        return solutions;
    }

private:
    void backtrack(vector<string>& board, int row) {
        // Check the base case
        if(row == board.size()){
            solutions.push_back(board);
            return;
        }

        for(int col=0;col<board.size();++col){ // Each col is a choose
            if(!isValid(board, row, col)) continue;
            board[row][col] = 'Q';
            backtrack(board, row+1);
            board[row][col] = '.';
        }
    }

    bool isValid(vector<string>& board, int row, int col) {
        // No need to check the row
        // Check the col
        for(int i=0;i<row;++i){
            if(board[i][col] == 'Q') return false;
        }
        // Check the upper left 
        for(int i=row-1, j=col-1;i>=0 && j>=0;--i, --j){
            if(board[i][j] == 'Q') return false;
        }
        // Check the upprt right
        for(int i=row-1, j=col+1;i>=0 && j<board.size();--i, ++j){
            if(board[i][j] == 'Q') return false;
        }
        return true;
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/