在8x8国际象棋棋盘上的5个皇后

Question

我想找到可能的方法来在棋盘上设置5个皇后的方法，但他们不能互相攻击。我已经成功找到第一套。问题是我将如何能够找到5个皇后的下一组职位。在我的程序的过程是这样的：

• 基于电路板上
• 回路的电流皇后通过板上的所有位置
• 检查当前的位置是一个禁止位置的矢量主板上的不允许位置
• 如果不是，返回的位置，将其添加到皇后区的载体板上，并开始处理再次

继续，直到有没有更多的对可用的即osition所有其余的位置是不允许

#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; 
} 

的其余部分的源代码，其中我有其他功能，例如产生禁止和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