本文共 1727 字，大约阅读时间需要 5 分钟。

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 the number of distinct solutions to the n-queens puzzle.

Example:

Input: 4Output: 2Explanation: There are two distinct solutions to the 4-queens puzzle as shown below.[ [".Q..",  // Solution 1  "...Q",  "Q...",  "..Q."], ["..Q.",  // Solution 2  "Q...",  "...Q",  ".Q.."]]

题意：计算合法的N皇后方案个数。

解法1 回溯法

这种题目做过很多次了，代码如下：

class Solution {
   private:    vector
   
     colExist;    vector
    
      colOfRows; //colOfRows记录每一行使用的列号    int ans = 0, maxRow, maxCol;    //通过curRow的变化防止行的重复,通过colExist防止列的重复,通过check和colOfRows防止对角线的重复    bool check(int curRow, int col) {
            for (int i = 0; i < curRow; ++i)             if (abs(colOfRows[i] - col) == abs(i - curRow)) return true;        return false;    }    void dfs(int curRow) {
           if (curRow >= maxRow) {
    ++ans; return; }        for (int i = 0; i < maxCol; ++i) {
               if (colExist[i] || check(curRow, i)) continue;            colExist[i] = true;     //选择了第i列             colOfRows[curRow] = i;  //记录第i列的使用             dfs(curRow + 1);            colExist[i] = false;        }    }public:    int totalNQueens(int n) {
            maxRow = maxCol = n;        colExist.resize(n);        colOfRows.resize(n);        dfs(0);        return ans;    }};
    
   

提交后结果如下：

执行用时：4 ms, 在所有 C++ 提交中击败了82.83% 的用户内存消耗：6.3 MB, 在所有 C++ 提交中击败了30.69% 的用户

解法二 打表

最快的方法：

class Solution {
    public:    const int table[20] = {
   0, 1, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680, 14200, 73712};    int totalNQueens(int n) {
    return table[n]; }};

提交后结果如下：

执行用时：0 ms, 在所有 C++ 提交中击败了100.00% 的用户内存消耗：5.9 MB, 在所有 C++ 提交中击败了67.39% 的用户

转载地址：https://memcpy0.blog.csdn.net/article/details/109140148 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！