1

バックトラッキングを使用して、N クイーン問題の解決策を実装しました。すべてのクイーンの位置が安全かどうかを、左上、右上、上を確認してから列に配置することで確認しています。そうでない場合はバックトラックします。

4 や 8 などの N の一部の値については正しい解を示していますが、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;
}
4

2 に答える 2

2

バックトラッキングのアイデアの実装は正しいです。問題は、配列「ボード」の値を手動でゼロに初期化する必要があるという事実から生じます。デフォルトでは、配列には未定義の値が含まれています。そうすれば、正しい答えが得られるはずです。コードをテストしました。配列の初期化に関する詳細については、http://www.fredosaurus.com/notes-cpp/arrayptr/array-initialization.html を参照してください。

于 2012-06-27T02:08:17.200 に答える