gpt4 book ai didi

c - 使用回溯的 n 皇后算法的基本逻辑

转载 作者:塔克拉玛干 更新时间:2023-11-03 06:03:12 26 4
gpt4 key购买 nike

这个 n 皇后程序使用了一个奇怪的回溯逻辑。我多次尝试跟踪代码,但我总是对它感到困惑。我真的对 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();
}

我只想知道它是如何自动回溯的?

最佳答案

place 仅检查 pos 行中的皇后是否可以放置在 a[pos] 列中。

回溯在queens函数中,当尝试将皇后放在第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

关于c - 使用回溯的 n 皇后算法的基本逻辑,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12884865/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com