c++ - 8x8 棋盘上的 5 个皇后

Question

我正在尝试找出在棋盘上设置 5 个皇后而又不会互相攻击的可能方法的数量。我已经成功地找到了第一组。问题是我如何才能找到 5 个皇后的下一组位置。我程序中的流程是这样的:

• 根据棋盘上的当前皇后生成不允许位置的 vector
• 遍历棋盘上的所有位置
• 检查当前位置是否是棋盘上不允许的位置之一
• 如果不是，则返回位置，将其添加到棋盘上的皇后 vector 中，然后重新开始该过程

继续，直到没有更多位置可用，即所有剩余位置都不允许

#include <iostream>
#include <vector>

using namespace std;
const int BSIZE = 8;
char chessBoard[BSIZE][BSIZE];

struct qPos
{
    qPos() : h(0), v(0), found(true) {}
    int h; //horizontal pos
    int v; //vertical pos
    bool found; //if position is available
};

qPos findNextQPos(vector<qPos> Qs);
void fillBoard(vector<qPos> Qs);
void print();
vector<qPos> generateDisallowed(vector<qPos> Qs);
bool isDisallowed(qPos nextPos, vector<qPos> disallowedPos);

int main(int argc, char **argv){
    vector<qPos> QsOnBoard; //Position of all the queens on board
    qPos nextQ; //next possible position
    while (nextQ.found)
    {
        nextQ = findNextQPos(QsOnBoard);
        if (nextQ.found)
        {
            QsOnBoard.push_back(nextQ); //If the nextQ is available i.e. not disallowed, add it to the queens vector
        }
    }
    fillBoard(QsOnBoard); //Fill the board with queens positions
    print(); // print the board
    return 0;
}

qPos findNextQPos(vector<qPos> Qs) {
    // Generate disallowed positions based on all the queens on board
    vector <qPos> disallowedPos = generateDisallowed(Qs);
    qPos nextQ;
    for (size_t i = 0; i < BSIZE; i++)
    {
        for (size_t j = 0; j < BSIZE; j++)
        {
            nextQ.h = i;
            nextQ.v = j;
            if (!isDisallowed(nextQ, disallowedPos)) { //Check if next possible position is a disallowed position
                //cout << "Next available:\n" << nextQ.h << ", " << nextQ.v << endl;
                return nextQ; // if it is avaible return the position, break the loop
            }
        }
    }
    nextQ.found = false; // No available position is found to return, found is set to false, return the position
    return nextQ;
}

我有其他功能的源代码的其余部分，例如 generate disallowed 和 isDisallowed 等在 this pastebin 上.我认为它不会与问题真正相关，并且此处的代码不应太长。

第一组的结果如下所示: 那么我应该如何继续才能找到所有解决方案集？这就是我卡住的地方。

Answer 1

首先，将这两个循环合并为一个:

for (size_t i = 0; i < BSIZE; i++)
{
    for (size_t j = 0; j < BSIZE; j++)
    {

相反:

for (size_t n = 0; n < (BSIZE * BSIZE); ++n)
{
    size_t i = n % BSIZE;
    size_t j = n / BSIZE;

现在您的函数可以轻松地使用起始 n。要找到“下一个”解决方案，只需移除最后一个皇后(注意其位置)并调用 FindNextQPos，告诉它从该皇后后一位的位置开始。如果该皇后已经在最后一个位置，则返回并删除另一个皇后。

如果找不到解决方案，请执行与找到解决方案相同的操作。移除最后一个皇后并调用 FindNextQPos，再次从您移除的皇后的位置开始。

当您没有要移除的皇后时，您就完成了。

您可以使用一个“继续”功能来完成此操作。无论您找到解决方案还是找不到解决方案，都可以调用此函数。它的逻辑是:

1. 找到最后一个女王。如果没有最后一个女王，就停止。我们完成了。

2. 记下它的位置。将其删除。

3. 调用 FindNextQPos 从我们记下的位置之后的位置开始。如果我们放置了一个皇后，从零位置开始不断尝试放置更多的皇后，直到我们找到解决方案或无法放置皇后。

4. 如果我们找到解决方案，输出它。

5. 转到第 1 步。