c++ - 8 皇后拼图冲突检查

Question

我最近读到了 8 个皇后问题，并尝试用 C++ 自己解决它。我创建了一个名为 eq.h 的类、一个名为 eq.cpp 的实现文件和一个 main.cpp。

我不确定的是，如何检查行、列和对角线冲突？我在想的是，使用嵌套的 for 循环进行冲突检查。那怎么应用？为此，我创建了一个 valid() 函数。以下是我到目前为止所得到的。

1) eq.h

#ifndef 8QUEEN_H
#define 8QUEEN_H

#include <iostream>
#include <algorithm>

using namespace std;

class 8queen
{
        public:
            8queen();
            ~8queen();
            int solve();//solve problem using next_permutation
            void display();

        private:
            bool valid();
            int queens[8]; //array to store 8 integers that represent 8 queens
};
#endif

2) eq.cpp

#include "eq.h"
#include <iostream>
#include <algorithm>

using namespace std;

8queen::8queen()
{
    for(int i=0;i<0;i++)
    {
        queens[i]=i;
    }
}

8queen::~8queen()
{

}

//using next_perm, return all possible positions of the queens
int 8queen::solve()
{
    int count=0;
    do{
        if(valid())
        {
            count++;
            display();
        }
    }
    while(next_permutation(queens,queens+8));
    return count;
}

//display the positions of the queens
void 8queen::display()
{
    for(int i=0; i<0;i++)
    {
        cout<<queens[i]<<' ';
    cout<<endl;
    }
}

//check if position is valid or not
bool 8queen::valid()
{
    return true;
}

3) main.cpp

#include "eq.h"
#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    8queen object;


    cout<<object.solve()<<endl;
}

Answer 1

好的

假设你有国际象棋网格。

对于水平和垂直冲突，您可以使用皇后位置的set存储i和（行和列）。j如果另一个皇后有相同的i或j- 冲突。

基调：

SET
row_set contains? (i) - conflict

column_set contains? (j) - conflict

对角线冲突（从左角到右角）
更复杂的情况。假设你有皇后(1,1)并且想把新的皇后放在上面(8,8) 所以这种情况可能是冲突的。当然。
如果差值(j - i)相同，就会发生这种情况。

假设你已经打开了 Queen(1,7)并且想要(2,8)
再次打开 Queen，这里的差异值(j - i)是相同的。

对角线冲突（从右角到左角）

假设你有皇后(8,1)并且想把新的皇后放在(1,8)
冲突上。
如果总和值(j + i)相同，则会发生这种情况。
假设你有皇后(1,2)并且想把新的皇后放在(2,1)
冲突上！
它发生导致总和值相同(j + i)

基调：

SET
left_to_right_set contains? (j - i)- 冲突
right_to_left_set contains? (j + i)- 冲突

我希望这能帮到您

Answer 2

请考虑以下代码。c[0][i]在一行中c[1][i]包含 # 个皇后，在一列中d[0][i]包含 # 个皇后，对于反向对角线d[1][i]包含 # 个皇后，对于主对角线包含 # 个皇后。编辑它以处理 8x8 网格而不是 4x4 网格。

int c[2][4] = {}, d[2][7] = {};
for (int i = 0; i < 4; ++i) {
    for (int j = 0; j < 4; ++j) {
        char x;
        cin >> x;
        if (x != 'x') continue;
        ++c[0][i], ++c[1][j];
        ++d[0][i + j], ++d[1][i + (3 - j)];
    }
}
for (int i = 0; i < 4; ++i)
    if (c[0][i] > 1 || c[1][i] > 1)
        return true;
for (int i = 0; i < 7; ++i)
    if (d[0][i] > 1 || d[1][i] > 1)
        return true;
return false;

活生生的例子。