为什么 "if" 不起作用？（n 皇后问题）

Question

这是我的代码

#include <iostream>
#include <vector>
using namespace std;

int k = 4;
vector<int> QLocation(k,0);
vector<vector<string> > board(k, vector<string>(k, "."));

bool check(int row, int column)
{
    if (row == 0) return true;

    for (int m = row - 1, n = 1; m >= 0; m--, n++)
    {
        if (board[m][column] == "Q") return false;
        if (column + n < n && board[m][column + n] == "Q") return false;
        if (column - n >= 0 && board[m][column - n] == "Q") return false;
    }
    return true;
}

void solve(int row, int column)
{
    for (int i = row; i < k;i++)
    {
        for (int j = column; j < k; j++)
        {
            if (check(i, j))
            {
                board[i][j] = "Q";
                QLocation[i] = j;
                break;
            }
            else
                board[i][j] = ".";

            if (j == k - 1)
            {
                i -= 1;
                j = QLocation[i];
            }
        }
    }
}

int main()
{    
    solve(0, 0);
    for (int i = 0; i < k; i++)
    {
        for (int j = 0; j < k; j++)
            cout << board[i][j];
        cout << endl;
    }
}

输出是无限循环

我在第11、15、16、17、28行设置断点，一步步查看值的变化

当i=2,j=1时，输入check当m=1,n=1时，board[m][column + n] == "Q"但不returnfalse

为什么？

====== 2021/08/25 22:00更新======

当我删除这些代码并且 k=4

if (j == k - 1)
{
    i -= 1;
    j = QLocation[i];
}

输出是

Q...
..Q.
.Q..
....

当k=8时输出为

Q.......
..Q.....
.Q......
.....Q..
.......Q
...Q....
........
....Q...

第三行总是失败，但其他行都是正确的

Answer 1

你的问题我觉得是这个逻辑。

for (int m = row - 1, n = 1; m >= 0; m--, n++)

您正在检查 m 何时等于或大于 0。但是您从 -1 开始并在每次迭代中减去 1。这意味着除非 returned.

否则你永远不会停止

而且我猜 m 对于 board[m][column] 没有 board[-10][5] 而它可能有 board[10][5]。所以你永远不会return false.

Answer 2

天哪……我的眼睛坏了。虽然查了很多遍，还是没有找到第16行

if (column + n <n && board[m][column + n] == "Q") return false;

column + n < n应该改为column + n < k

感谢molbdnilo，很抱歉浪费大家的时间

====== 2021/08/26 00:05更新======

我终于修好了，这是代码

（我知道它很丑并且有异常（比如 k=3）和多个解决方案（比如 k=4 有两个解决方案）要处理）

#include <iostream>
#include <vector>
using namespace std;

int k = 4;
vector<int> QLocation(k,0);
vector<vector<string> > board(k, vector<string>(k, "."));

bool check(int row, int column)
{
    if (row == 0) return true;

    for (int m = row - 1, n = 1; m >= 0; m--, n++)
    {
        if (board[m][column] == "Q") return false;
        if (column + n < k && board[m][column + n] == "Q") return false;
        if (column - n >= 0 && board[m][column - n] == "Q") return false;
    }
    return true;
}

void solve(int row, int column)
{
    bool rowFail = false;

    for (int i = row; i < k; i++)
    {
        for (int j = column; j < k; j++)
        {
            if (check(i, j))
            {
                board[i][j] = "Q";
                QLocation[i] = j;
                rowFail = false;
                break;
            }
            else
            {
                board[i][j] = ".";
                rowFail = true;
            }
        }

        if (rowFail)
        {
            column = QLocation[i -= 1];
            board[i][column] = ".";
            i -= 1;
            column += 1;
        }
        else
            column = 0;
    }
}

int main()
{    
    solve(0, 0);
    for (int x = 0; x < k; x++)
    {
        for (int y = 0; y < k; y++)
            cout << board[x][y];
        cout << endl;
    }
}

Answer 3

编辑：此答案假定您已将 if(column + n < n ...) 中的拼写错误更正为 if(column + n < k ...)

问题出在这部分

if(j == k-1){
   i -= 1;
   j = Qlocation[i];
}

考虑迭代中k = 4和i = 2的情况。届时董事会将看起来像这样。

Q...
..Q.
....
....

这里 check(i, j) 对于 i = 2 总是假的，所以 i 回到 1。但是你没有改变 board[i][Qlocation[i]] 的值回来到 '。'。这是一个错误（即使你更正了这个，它也不会起作用。我会告诉你为什么假设你通过在 j = Qlocation[i]; 之后添加 board[i][j] = "." 来更正它）。现在值是 i = 1，j = 3（for 循环中的 j++）。检查 return 为真，你在那里放置一个皇后，然后 i 增加到 2。

棋盘：

Q...
...Q
....
....

这里，检查 (i, j) returns true for j = 1. The board:

Q...
...Q
.Q..
....

现在 i = 3。check(i, j) 对所有 j 都失败。 i 减少到 2，j 减少到 2(j = Qlocation(i), j++)。 check(i, j) 对于 (2, 2) 和 (2, 3) 失败，在这一点上 i 进一步减少到 1，j 减少到 4 (j = Qlocation(1), j++).

棋盘：

Q...
....
....
....
because of board[i][j] = ".";

现在j = 4不满足条件j < k，所以内层for循环中断，外层for循环迭代增加i到2。 check(i, j) return j = 1 时为真。棋盘：

Q...
....
.Q..
....

现在 i = 3，check(i, j) 对所有 j 都失败，i 变为 2。check(i, j) returns true for j = 3.The board:

Q...
....
...Q
....

现在再次 i = 3，检查 (i, j) return对于 j = 1 为真。最终答案：

Q...
....
...Q
.Q..

这是错误的。因此，您必须添加一个检查 for 循环是否在行中没有任何 Q 的情况下退出。

为什么 "if" 不起作用？（n 皇后问题）

Why the "if" didn't work ? (n queen problem)

c++

n-queens

为什么 "if" 不起作用？ （n 皇后问题）

Why the "if" didn't work ? (n queen problem)

c++

n-queens

为什么 "if" 不起作用？（n 皇后问题）