文章/答案/技术大牛

发布

社区首页 >问答首页 >计算N个皇后可以放置在N✕N国际象棋棋盘上的次数

问计算N个皇后可以放置在N✕N国际象棋棋盘上的次数
EN

Code Review用户

提问于 2023-04-06 14:06:18

回答 2查看 162关注 0票数 1

N皇后之谜是将n个皇后放在n个✕n个棋盘上的问题，这样就不会有两个皇后互相攻击。

给定整数n，这段代码将返回n皇后谜题的不同解决方案的数目。

如何进一步优化(在时间和空间上)下面的解决方案，以解决leetcode的solution 2问题？该解决方案的运行时为8ms，超过了提交量的42.55%，消耗了6MB内存，超过了所有提交的82.99%。我相信应该有一个方法来提高性能，但我正在努力实施必要的修改。

class Solution {
public:
     typedef pair<int,int> ii;

    void solveNQtrav(int N, int row, vector<ii>& Pos, int& ct){
        if(N == row){
            ++ct;
        }
        
        for(int col = 0; col < N; ++col){
            bool safe = true;
            for(int j = 0; j < row; ++j){
                if(Pos[j].second == col||Pos[j].first-Pos[j].second == row-col
                ||Pos[j].first+Pos[j].second == row+col){
                    safe = false;
                    break;
                }
            }
            if(safe){
                Pos[row] = ii(row, col);
                solveNQtrav(N, row+1, Pos, ct);
            }
        }
    }

    int totalNQueens(int n) {
        vector<ii> pos(n);
        int count = 0;
        solveNQtrav(n, 0, pos, count);
        return count;
    }
};

c++

performance

algorithm

backtracking

n-queens

回答 2

Code Review用户

发布于 2023-04-06 14:36:53

优化代码

考虑到LeetCode站点提到了1 \leq n \leq 9，最佳解决方案将是预先计算该解决方案：

#include <array>

class Solution {
public:
    int totalNQueens(int n) {
        return std::array{1, 1, 0, 0, 2, 10, 4, 40, 92, 352}[n];
    }
};

这根本不使用堆内存，应该只需要几个CPU周期即可执行。

如果您认为这违背了LeetCode的精神，那么请考虑制作您的解决方案constexpr，这样您就可以在编译时使用解决方案构建一个数组。这样，您就可以以编程的方式计算值，但只需执行一个简单的表查找即可获得可执行文件的好处。

命名事物

有些类型和变量的名称太短了，比如ii和ct。你也不一致:为什么有ct和count，pos和Pos，n和N？

名称应该简洁，但不需要不必要的缩写，所以更喜欢count而不是ct。对于非常常见的事物，只使用一个或两个字母的变量名，比如n表示"number"，或者i用于循环索引。

我不使用ii，而是使用position或coordinates。

还可以使用一个名称来描述变量的用途，而不仅仅是描述它所持有的数据类型。因此，与pos不同，queens或queen_positions可能会更好，因为这个矢量在董事会中保留了皇后的位置。

更喜欢创建一个`struct`而不是使用`std::pair`

创建struct比使用std::pair或std::tuple好得多。结构的优点是您可以命名它所包含的单个值。例如：

struct position {
    int row;
    int col;
};

允许您编写如下代码：

void solveNQtrav(int n, int row, std::vector<position>& queens, int& count) {
    …
    if (queens[j].col == col ||
        queens[j].row - queens[j].col == row - col ||
        queens[j].row + queens[j].col == row + col) {
        …
    }
    …
}

因此，现在您不必再记住.first是行还是列。

创建辅助函数以降低代码复杂度

if-statement in solveNQtrav()看起来相当复杂，如果您还不知道它应该做什么，那么很难理解它的含义。即使是少量的代码，有时也会帮助创建一个助手函数：

bool attacks(position queen, position pos) {
    return queen.col == pos.col ||
           queen.row - queen.col == pos.row - pos.col ||
           queen.row + queen.col == pos.row + pos.col;
}

void solveNQtrav(int n, int row, std::vector<position>& queens, int& count) {
    …
    if (attacks(queens[j], {row, col}) {
        …
    }
    …
}

现在，如果我阅读“if-statement”，它几乎是自动记录的，它检查给定的女王是否攻击给定的位置。您还可以创建更多的助手函数，比如检查给定列是否安全地放置皇后，这样您就可以编写：

void solveNQtrav(int n, int row, std::vector<position>& queens, int& count) {
    if (n == row) {
        ++count;
    }
        
    for (int col = 0; col < N; ++col) {
        if (column_is_safe(queens, row, col)) {
              queens[row] = {row, col};
              solveNQtrav(n, row + 1, queens, count);
            }
        }
    }
}

参数和返回值

您不需要将n传递给solveNQtrav；位置向量已经知道其大小，因此可以使用它。此外，您可以让solveNQtrav() return获得解决方案的数量，而不是使用引用参数。最后，您可以使row成为最后一个参数，并给它一个默认值：

int solveNQtrav(std::vector<position>& queens, int row = 0) {
    if (queens.size() == row) {
        return 1;
    }
    
    int count = 0;
 
    for (int col = 0; col < N; ++col) {
        if (column_is_safe(queens, row, col)) {
              queens[row] = {row, col};
              count += solveNQtrav(n, row + 1, queens, count);
            }
        }
    }

    return count;
}

这个简化的totalNQueens()：

int totalNQueens(int n) {
    vector<position> queens(n);
    return solveNQtrav(queens);
}

--你不需要一个`std::pair`向量就可以从

开始

考虑到女王的位置向量是这样的，在i行上的女王总是在索引i，您根本不需要在向量中存储行号；ints的一个简单向量只存储每个女王出现的列就足够了。

票数 3

Code Review用户

发布于 2023-04-07 07:54:12

密码不完整。我推断出你在某个地方

#include <pair>
#include <vector>

using std::pair;
using std::vector;

我不认为usings会增加任何价值(它们甚至不会使代码变小)。我建议删除它们，并在代码中简单地使用限定的类型名。这也使读者的生活变得更容易，因为他们不需要掌握太多的上下文。

还不清楚为什么类的内部都公开(public)。就这一点而言，似乎根本不需要一个类:它不包含任何状态，这两个函数很可能是自由函数(或者，几乎相当于static)。

票数 2

页面原文内容由Code Review提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://codereview.stackexchange.com/questions/284339

复制

相似问题

问计算N个皇后可以放置在N✕N国际象棋棋盘上的次数
EN

回答 2

Code Review用户

优化代码

命名事物

更喜欢创建一个`struct`而不是使用`std::pair`

创建辅助函数以降低代码复杂度

参数和返回值

--你不需要一个`std::pair`向量就可以从

Code Review用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问计算N个皇后可以放置在N✕N国际象棋棋盘上的次数EN

回答 2

Code Review用户

优化代码

命名事物

更喜欢创建一个struct而不是使用std::pair

创建辅助函数以降低代码复杂度

参数和返回值

--你不需要一个std::pair向量就可以从

Code Review用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问计算N个皇后可以放置在N✕N国际象棋棋盘上的次数
EN

更喜欢创建一个`struct`而不是使用`std::pair`

--你不需要一个`std::pair`向量就可以从