LeetCode 51 N-Queens

标签: 回溯法 LeetCode 发布于:2020-06-07 13:46:25 编辑于:2022-02-22 11:34:45 浏览量:870

概述

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

回溯算法解题套路框架

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

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

之前的笔记

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

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

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

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

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

我们可以通过给皇后定义一个顺序来解决这个解重复的问题,考虑到每一行每一列都有且只有一个皇后,那么我们增加一个第 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;
    }
};

2022年2月22日的解法

下面的解法越界了:

class Solution {
public:
    vector<vector<string>> ans;
    int n;
    vector<vector<string>> solveNQueens(int n) {
        this->n = n;
        string line = "";
        for (int i = 0; i < n; i ++) line += '.';
        vector<string> board(n, line);
        backtrack(board, 0);
        return ans;
    }
    
    void backtrack(vector<string>& board, int r) {
        if (r == n) {
            ans.push_back(board);
        }
        for (int c = 0; c < n; c ++) {
            if (isValid(board, r, c)) {
                board[r][c] = 'Q';
                backtrack(board, r + 1);
                board[r][c] = '.';
            }
        }
    }
    
    bool isValid(vector<string>& board, int r, int c) {
        for (int i = 0; i < n; i ++) {
            if (board[i][c] == 'Q' || board[r][i] == 'Q') return false;
        }
        return true;
    }
};

发现 bug 了,ans.push_back(board); 之后没 return 。。。

此外皇后也不能在斜的方向上共线。

class Solution {
public:
    vector<vector<string>> ans;
    int n;
    vector<vector<string>> solveNQueens(int n) {
        this->n = n;
        vector<string> board(n, string(n, '.'));
        backtrack(board, 0);
        return ans;
    }
    
    void backtrack(vector<string>& board, int r) {
        if (r == n) {
            ans.push_back(board);
            return;
        }
        for (int c = 0; c < n; c ++) {
            if (isValid(board, r, c)) {
                board[r][c] = 'Q';
                backtrack(board, r + 1);
                board[r][c] = '.';
            }
        }
    }
    
    bool isValid(vector<string>& board, int r, int c) {
        for (int i = 0; i <= r; i ++) {
            if (board[i][c] == 'Q') return false;
            if (r-i >= 0) {
                if (c-i >=0 && board[r-i][c-i] == 'Q') return false;
                if (c+i < n && board[r-i][c+i] == 'Q') return false;
            }
        }
        return true;
    }
};

时间复杂度:O(n*n*n) = O(n^3)

n 个皇后,每个 n 个选择,每次选择 O(n) 判断是否合法。

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