0

私は、2人の女王が互いに攻撃できないように4人の女王を4X4のチェス盤に配置する必要があるN女王の問題を解決していました。以前にこれを試しましたが、私のアプローチにはバックトラックが含まれていなかったため、再試行しました。コードスニペットは

int size=4,i,j;
int arr[4][4];
int lastjindex[4]; // to store the last location which we may need to backtrack



void placeQueen(int i,int j)
{
    int availableornot=0;

    for(j=0;j<size;j++)
    {
        if(isAvailable(i,j)==1)
        {
            availableornot=1;
            break;
        }
    }

    if(availableornot==1)
    {
        arr[i][j]=1;
        lastjindex[i]=j;

        if((i+1)!=size)
        {
            placeQueen(i+1,0);
        }
    }

    else
    {
        // no column was availabe so we backtrack
        arr[i-1][lastjindex[i-1]]=0;
        placeQueen(i-1,lastjindex[i-1]+1);
    }
}

isAvailable（）メソッドは、arr [i] [j]が攻撃を受けていない場合は1を返し、そうでない場合は0を返します。

int isAvailable(int i,int j)
{
    int m,n,flag=0;

    for(m=0;m<i;m++)
    {
        for(n=0;n<size;n++)
        {
            int k=abs(i-m);
            int l=abs(j-n);

            if(arr[m][j]==0 || arr[k][l]==0)
            {
                flag=1;
                break;
                // means that spot is available
            }
        }
    }
    return flag;
}

上記のメソッドをmainから呼び出します。

placeQueen(0,0);

私のプログラムは正常にコンパイルされますが、すべてゼロが出力されます。

再帰に問題はありますか？バックトラッキングアルゴリズムを実装する方法を学ぼうとしているので、コードを修正するのを手伝ってください！

また、再帰を終了するための基本条件を決定できません。ここでどのように選択しますか？

4

2 に答える 2

1 
#include <stdio.h>

#define SIZE 4
int size=SIZE;
int arr[SIZE][SIZE] = { 0 };

void placeQueen(int col){
    int r,c;
    if(col == size){//all queen put!
        //print out
        for(r = 0;r<size;++r){
            for(c = 0;c<size;++c)
                printf("%d", arr[c][r]);
            printf("\n");
        }
        printf("\n");
        return ;
    }
    for(r=0;r<size;++r){
        if(isAvailable(col, r)==1){
            arr[col][r]=1;
            placeQueen(col+1);
            arr[col][r]=0;//reset
        }
    }
}

int isAvailable(int col,int row){
    int c;

    for(c=0;c<col;++c){
        int d = col - c;
        if(arr[c][row]==1)
            return 0;//queen already same row
        if(row+d < size && arr[c][row+d]==1 || row-d >= 0 && arr[c][row-d]==1)
            return 0;//queen already same slanting position
    }
    return 1;
}

int main(){
    placeQueen(0);
    return 0;
}
于 2012-07-14T13:37:14.300 に答える
1

投稿したコードには印刷がありません。バックトラックした後に印刷すると、ボードにクイーンがない初期状態に戻ります。N個のクイーンを配置した後に印刷します。これは再帰の終了条件でもあります。1つのソリューションのみを印刷する場合は、印刷後に終了するか、終了したことを発信者に通知するフラグを設定して、完全にポップアウトします。すべてのソリューションを印刷すると、反射と回転が含まれます。最初のレベルでサイズ/2以内にクイーンを配置するだけで、1つの反射軸を排除できます。

また、コードには次のような明確な論理エラーがあります。

arr[m][j]==0 || arr[k][l]==0

クイーンは、ファイルに対して攻撃されておらず、対角線に沿って攻撃されていない場合にのみ配置できます。デバッガーを使用するか、コードにprintfsを追加して、クイーンを配置しようとしている場所をトレースします。これは、何が間違っているのかを把握するのに役立ちます。

そして、間違っていることを除けば、あなたisAvailableは非常に非効率的です。[i、j]の正方形がファイルに沿って攻撃されているのか、対角線に沿って攻撃されているのかを知りたいとします。そのためには、前のクイーンの行に対して単一のループがfor (m = 0; m < i; m++)必要ですが、ファイルと対角線をチェックするために必要なテストは、ループではなく3つだけです。ファイルまたは対角線上に前のクイーンが見つかるとすぐに完了し、正方形は使用できなくなります。falseを返します。（そして、関数は1つのリターンしか持たないはずだと言う人を無視してください-彼らは間違っています、そしてここSOで長い議論があり、これを裏付けるコードのエラー率の科学的研究さえあります。）前の女王がいない場合のみ見つかったのは利用可能な正方形です。

あなたplaceQueenも間違っています。行の利用可能な正方形ごとに、クイーンを配置してから再帰する必要がありますが、最初に利用可能な正方形を見つけるだけです。そして、バックトラックは、配置したクイーンを削除してから戻るだけで実現されます...前のレベルのplaceQueenは、次に利用可能なスポットを試します。

繰り返しますが、コードをトレースして、コードが何をしているのかを確認します。そして、さらに重要なのは、何が必要かという論理を通して考えることです。アルゴリズムを言葉で書き、それが問題を解決することを確信してから、アルゴリズムを実行するためのコードを書きます。

于 2012-07-14T09:45:15.190 に答える