LeetCode 51 N-Queens

概述

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) 判断是否合法。

Links: LeetCode-51-N-Queens

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