0

n-queens 向けのこのプログラムは、バックトラックに奇妙なロジックを使用しています。コードを何度も追跡しようとしましたが、いつも混乱してしまいます。Place(int pos)関数と本当に混同しています。

#include<stdio.h>
#include<conio.h>
int a[30],count=0;
int place(int pos)
{
    int i;
    for(i=1;i<pos;i++)
    {
        if( (a[i]==a[pos]) || ((abs(a[i]-a[pos])==abs(i-pos))) )
        {
            return 0;
        }
    }
    return 1;
}

void print_sol(int n)
{
    int i,j;
    count++;
    printf("\nSOLUTION #%d\n",count);
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            if(a[i]==j)
                printf("Q\t");
            else
                printf("*\t");
        }
        printf("\n");
    }
}



void queen(n)
{
    int k=1;
    a[k]=0;
    while(k!=0)
    {
        a[k]++;
        while(a[k]<=n && !place(k))
            a[k]++;
        if(a[k]<=n)
        {
            if(k==n)
                print_sol(n);
            else
            {
                k++;
                a[k]=0;
            }
        }
        else
            k--;
    }
}

void main()
{
    int n;
    clrscr();
    printf("\nEnter the number of queens:");
    scanf("%d",&n);
    queen(n);
    getch();
}

自動的にバックトラックする方法を知りたいだけですか?

4

2 に答える 2

2

place行のクイーンを列posに配置できるかどうかを確認するだけa[pos]です。

クイーンをrowqueensに配置しようとするとk、最初a[k]は 0 です。これは、クイーンの有効な位置ではありません。

a[k]++;     // here, a[k] was not a valid position and no smaller was valid, so increment
while(a[k]<=n && !place(k))  // while the position is invalid, check next
    a[k]++;
if(a[k]<=n)  // if a valid column was found
{
    if(k==n) // that was the last row, done
        print_sol(n);
    else     // next row
    {
        k++;
        a[k]=0;
    }
}
else  // no possible column found (a[k] > n), so backtrack
k--;  // check for next possible column in previous row
于 2012-10-14T18:04:13.987 に答える
0

クイーン番号が より小さい番号のクイーンによって攻撃できるかどうかをplace判断するだけです。これは、クイーン #pos が他の各クイーンと同じ列または対角線上にあるかどうかを順番にチェックすることによって行われます。したがって、 ifが返される場合は、 の値が、クイーンを合法的に配置できる列のゼロベースのインデックスであることを意味します。posposplace(pos)1a[pos]

于 2012-10-14T18:00:37.447 に答える