C++ 逻辑错误 [N-Queen]

Question

这是我第一次在这里发布问题，所以请放轻松。

我最近遇到了 n-queen/8 queen 问题，觉得很有趣就试了一下

我为这个问题编写了一个基本代码，但它没有给出任何输出。当我尝试调试它时，它表明流程没有超出某个点并且会返回到其父函数以进行进一步的迭代。

因此在花了一些时间之后，我似乎无法理解这个问题，因此决定寻求帮助。

此外，似乎我需要在函数头中为 2-D/3-D 数组等定​​义数组的大小......

P.S 我是一名学生，所以我可能会弄错一些概念。对不起，如果他们中的一些人太愚蠢了。

代码如下:

//------------------------------------------------------------------------
#include<iostream>
#include<conio.h>
#include<stdlib.h>

using namespace std;

#define RED -1
#define BLACK 0
#define OCCUPIED 1

//RED = Cell attackable by queen(s)
//BLACK = Cell safe from attack and hence a piece may be placed there
//OCCUPIED = Cell where a queen resides


void display(int,int[20][20]);
void nqueen(int,int[20][20],int=0);

int main()
{
    //clrscr();
    int n,board[20][20];
    cout<<"Enter value of n:";
    cin>>n;

    for(int i=0;i<n;++i)
        for(int j=0;j<n;++j)
            board[i][j]=BLACK; //Initializing the board to black

    nqueen(n,board); //Calling function
    return 0;
}


void display(int n,int board[20][20])  //Gives an error if i dont define size of board
{
    for(int i=0;i<n;++i)
    {
        for(int j=0;j<n;++j)
            if(board[i][j]==OCCUPIED)
                cout<<"O";
            else
                cout<<"X";

        cout<<endl;
    }
    cout<<"\nPress 0 to exit....";    //Allows the program ot be terminated mid-way
    int ch;
    cin>>ch;
    if(ch==0)
        exit(1);
    //clrscr();
}

//Displays all the boards contents O = Occupied while X = Not occupied

void nqueen(int n,int board[20][20],int row) //row is given a default value 0
{
    if(row==n)              //End Statement
    {
        display(n,board);
        return;
    }

    for(int i=0;i<n;++i)          //Looping within row's columns to check for BLACK cells
        if(board[row][i]==BLACK)  //condition
        {

            //-------Puts attack (RED) on the board------
            for(int j=0;j<n;++j)
                board[j][i]=RED; //all cells in column turned red . Not done for row so as to allow further ilteation .
            for(int k=0;(k+row)<n&&(k+i)<n;++k)
                board[row+k][i+k]=RED; //This reds out the diagonal right cells. Left upper rows unaltered as its too much of a useless bother
            for(int k=0;(k+row)<n&&(i-k)>=0;++k)
                                    board[row+k][i-k]=RED; //This reds out the diagonal left cells. Left upper rows unaltered as its too much of a useless bother

            //------Done putting reds-----------
            board[row][i]=OCCUPIED; //Placed queen on cell
            nqueen(n,board,row+1);//Recursion continues
            board[row][i]=BLACK; //Returns back to black for further iltertions
         }
}

//-------------------------------------------- ---

感谢您的建议，我仍然无法相信我在那个循环中犯了如此愚蠢的错误，我将左侧单元格红色更改为以下内容:

    for(int k=0;(k+row)<n&&(i-k)>=0;++k)
                     board[row+k][i-k]=RED; //This reds out the diagonal left cells. Left upper rows unaltered as its too much of a useless bother

本来忘记放了，后来没来得及看，抱歉。

无论如何，在将其更改为正常工作后，我发现它确实为我提供了一个输出，但仅限于 n=5。接下来，它只给我 1 个输出，即使有 2 个输出 [如果我是正确的满足 n=5 条件]。对于其余的输入，它仍然在做同样的事情

---

至于编译器，我目前使用的是代码块，但我已经在 Turbo 中对其进行了调试。我意识到 Turbo 有一些问题，所以我在代码块中做了最后几处更改。

至于 Visual Studio，我不会用。它是一个付费软件，因为这只是一种爱好，我 parent 会因为我花钱买它而杀了我。

这样的流程在 n=5 的 i=2 和 n=7 的 i=4 上终止，依此类推。n=5 的流程现在似乎在第一次通过后中断，而其余的仍然中断

Answer 1

首先，我强烈建议阅读 Program Development By Stepwise Refinement .作为奖励，Wirth 先生文章的主要样本是 8 皇后问题，许多概念在今天仍然适用，距该论文首次发表约 42 年。

关于您的特定代码，立即弹出的一件事如下:

for(int k=(row>i?row:i);(row-k)>=0&&(i-k)>=0;--k)
    board[row-k][i-k]=RED; 

当这在 i 和 row 循环的第一次 迭代中执行时会发生什么？嗯，

int k=(row>i?row:i);

k 将为零 (0)。接下来，测试条件将成立，因为...

(row-k)>=0 && (i-k)>=0;

由于所有三个值(row、i 和 k)都为零 (0)，因此这等同于:

(0-0)>=0 && (0-0)>=0

这当然是真的..这将我们带到循环体，一条语句:

board[row-k][i-k]=RED;

除了将 [0][0] 的空间设置为 RED 外，没有做太多事情。但是现在，看看在 for 循环的递增步骤中发生了什么:

--k

现在k为(-1)，则条件表达式为

(0-(-1))>=0 && (0-(-1))>=0

这仍然是正确的，因为 1>=0 && 1>=0 成立。因此，我们回到循环体并...

board[0-(-1)][i-(-1)]=RED;

这就是...

board[1][1]=RED;

再一次，我们遇到了 for 循环的增量子句，它将 (-2) 赋值给 k。条件子句仍然成立:

(0-(-2))>=0 && (0-(-2))>=0

所以又一次，我们又回到了 body ，最终......

board[2][2]=RED;

这一直持续到 --k 足以使您的 board[][] 索引完全超过数组限制的末尾并进入 未定义的行为。

我建议您重新检查算法实现的正确性。