私は、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);
私のプログラムは正常にコンパイルされますが、すべてゼロが出力されます。
再帰に問題はありますか?バックトラッキングアルゴリズムを実装する方法を学ぼうとしているので、コードを修正するのを手伝ってください!
また、再帰を終了するための基本条件を決定できません。ここでどのように選択しますか?