HelloKenLee

Leetcode 51. N-Queens 解题报告

Posted on By KenLee

题目信息

题目: 51. N-Queens
难度: Hard
正确率: 30.43%
问题描述:

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens’ placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

For example, There exist two distinct solutions to the 4-queens puzzle:

[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

问题分析

  经典的8皇后问题。扩展为N皇后

解题思路

  主要使用DFS+回溯法解决。分别使用3个数组记录使用了的行,列,对角线。

结果分析

  • 时间复杂度: $ O(2^N) $。
  • 空间复杂度: $ O(N^2) $。
  • 通过时间: 6 ms
  • 击败: 33.42%

源代码

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        //init
        results.resize(0);
        
        usedCols.resize(0);
        usedCols.resize(n,false);
        
        usedDiags.resize(0);
        usedDiags.resize(n*2,false);
        
        usedBackDiags.resize(0);
        usedBackDiags.resize(n*2,false);
        
        board.resize(0);
        board.resize(n,string(n,'.'));
        
        this->n=n;
        search(0);
        return results;
    }
private:
    vector<vector<string>> results;
    vector<bool> usedCols;
    vector<bool> usedDiags;
    vector<bool> usedBackDiags;
    vector<string> board;
    int n;
    //按行DFS搜索
    void search(int r){
        if(r>=n){
            results.push_back(board);
            return;
        }
        for(int c=0;c<n;++c){
            if(!usedCols[c] && !usedDiags[r-c+n] && !usedBackDiags[r+c]){
                //r行c列和上面无冲突,向下搜索
                usedCols[c]=true;
                usedDiags[r-c+n]=true;
                usedBackDiags[r+c]=true;
                board[r][c]='Q';
                search(r+1);
                //恢复
                usedCols[c]=false;
                usedDiags[r-c+n]=false;
                usedBackDiags[r+c]=false;
                board[r][c]='.';
            }
        }
    }
};