c - N皇后使用回溯

Question

我已经通过使用回溯实现了 N 皇后问题的解决方案。我正在检查每个皇后的位置是否安全，方法是检查其左上角、右上角和顶部，然后将其放在行中，否则我回溯。

它对 N 的某些值(例如 4 和 8)给出了正确的解决方案，但对其他值(例如 6)则不正确。

我不知道我错过了什么。任何帮助将不胜感激。

代码如下:

int S;
static int cnt=0;

int safepos(int board[][S+1],int i,int j)
{
    if(i==1)        
    return 1;

    int a,b;
    a=i-1;
    b=j-1;

    //checking for top-left side
    while(a>0 && b>0 )
    {
        if(board[a--][b--]==1)
        return 0;
    }

    a=i-1;
    b=j+1;
    //checking for top-right side    
    while(a>0 && b<=S )
    {
        if(board[a--][b++]==1)
        return 0;
    }

    //checking for the same column        
    for(a=1;a<i;a++)
        if(board[a][j]==1)
            return 0;
    return 1;
}

void Nqueens(int board[][S+1],int N,int n)  //n is the number of the rows
{
    if(n==N+1) //for those which reaches the last position we will have a solution
    {
        cnt++;
        return;    
    }
    int i;    
    for(i=1;i<=N;i++)  //for every column
    {
        if( safepos(board,n,i) )
        {
            board[n][i]=1;    
            Nqueens(board,N,n+1);  //checking for next row
        }
        board[n][i]=0;
    }
}

int main()
{
    int N=6;
    S=N;
    int board[N+1][N+1];    
    Nqueens(board,N,1);
    printf("%d",cnt);
    return 0;
}

Answer 1

您对回溯思想的实现是正确的，问题在于数组“board”的值必须手动初始化为零，默认情况下，数组带有未定义的值。如果你这样做，你应该得到正确的答案，我测试了代码。有关数组初始化的更多信息，请参阅 http://www.fredosaurus.com/notes-cpp/arrayptr/array-initialization.html