N Queens Puzzle - 此解决方案中的回溯在哪里?
N Queens Puzzle - Where is the Backtracking in this solution?
在研究众所周知的 N Queens puzzle, I came across this C:
中简单易懂的实现时
#include<stdio.h>
#include<math.h>
int board[20],count;
int main()
{
int n,i,j;
void queen(int row,int n);
printf(" - N Queens Problem Using Backtracking -");
printf("\n\nEnter number of Queens:");
scanf("%d",&n);
queen(1,n);
return 0;
}
//function for printing the solution
void print(int n)
{
int i,j;
printf("\n\nSolution %d:\n\n",++count);
for(i=1;i<=n;++i)
printf("\t%d",i);
for(i=1;i<=n;++i)
{
printf("\n\n%d",i);
for(j=1;j<=n;++j) //for nxn board
{
if(board[i]==j)
printf("\tQ"); //queen at i,j position
else
printf("\t-"); //empty slot
}
}
}
/*funtion to check conflicts
If no conflict for desired postion returns 1 otherwise returns 0*/
int place(int row,int column)
{
int i;
for(i=1;i<=row-1;++i)
{
//checking column and digonal conflicts
if(board[i]==column)
return 0;
else
if(abs(board[i]-column)==abs(i-row))
return 0;
}
return 1; //no conflicts
}
//function to check for proper positioning of queen
void queen(int row,int n)
{
int column;
for(column=1;column<=n;++column)
{
if(place(row,column))
{
board[row]=column; //no conflicts so place queen
if(row==n) //dead end
print(n); //printing the board configuration
else //try queen with next position
queen(row+1,n);
}
}
}
然而,尽管大部分内容对我来说都是正确的,但我看不到其中的 回溯。我错过了什么?
在我看来,在 queen()
函数中,应该在 for
循环之后进行检查,以查看针对特定 row/queen 的搜索是否已耗尽但没有成功,如果所以,通过简单地用 row-1 调用自己来回溯。这个假设是否正确?
让我们深入了解这段代码:
void queen(int row,int n)
{
int column;
for(column=1;column<=n;++column)
{
if(place(row,column))
{
board[row]=column; //no conflicts so place queen
if(row==n) //dead end
print(n); //printing the board configuration
else //try queen with next position
queen(row+1,n);
}
}
}
是的,这是回溯。因为它会尝试所有可能的候选解决方案,直到达到某个完成条件。在某些 row
值上,for(column=1;column<=n;++column)
将确保尝试 column
的每个可能值并检查 place(row,column)
是否可行,然后更深入 row
+1 .完成后,该算法将继续下一栏。
换句话说,该算法将打印 n
-queen.
的所有可能的解决方案
回溯隐藏在函数的递归调用中queen()
。它通过尝试和错误来逐列检查列,如果发现命中则放置皇后。然后用下一行递归调用函数queen()
,遍历这个下一行一列一列,直到找到不能打败皇后的地方。并重复此递归调用,直到所有皇后都被放置。
回溯的主要思想是试错法。如果不能放置所有皇后,则算法跳回一个树枝并从下一列重新开始。
回溯是通过 queens
函数末尾隐含的 return
语句完成的。它是在检查所有列之后出现的,即您提到的详尽搜索。
为了看得更清楚,重写函数以使用显式堆栈数据结构代替隐式调用堆栈。那么回溯将明确表示为pop(stack)
.
在研究众所周知的 N Queens puzzle, I came across this C:
中简单易懂的实现时#include<stdio.h>
#include<math.h>
int board[20],count;
int main()
{
int n,i,j;
void queen(int row,int n);
printf(" - N Queens Problem Using Backtracking -");
printf("\n\nEnter number of Queens:");
scanf("%d",&n);
queen(1,n);
return 0;
}
//function for printing the solution
void print(int n)
{
int i,j;
printf("\n\nSolution %d:\n\n",++count);
for(i=1;i<=n;++i)
printf("\t%d",i);
for(i=1;i<=n;++i)
{
printf("\n\n%d",i);
for(j=1;j<=n;++j) //for nxn board
{
if(board[i]==j)
printf("\tQ"); //queen at i,j position
else
printf("\t-"); //empty slot
}
}
}
/*funtion to check conflicts
If no conflict for desired postion returns 1 otherwise returns 0*/
int place(int row,int column)
{
int i;
for(i=1;i<=row-1;++i)
{
//checking column and digonal conflicts
if(board[i]==column)
return 0;
else
if(abs(board[i]-column)==abs(i-row))
return 0;
}
return 1; //no conflicts
}
//function to check for proper positioning of queen
void queen(int row,int n)
{
int column;
for(column=1;column<=n;++column)
{
if(place(row,column))
{
board[row]=column; //no conflicts so place queen
if(row==n) //dead end
print(n); //printing the board configuration
else //try queen with next position
queen(row+1,n);
}
}
}
然而,尽管大部分内容对我来说都是正确的,但我看不到其中的 回溯。我错过了什么?
在我看来,在 queen()
函数中,应该在 for
循环之后进行检查,以查看针对特定 row/queen 的搜索是否已耗尽但没有成功,如果所以,通过简单地用 row-1 调用自己来回溯。这个假设是否正确?
让我们深入了解这段代码:
void queen(int row,int n)
{
int column;
for(column=1;column<=n;++column)
{
if(place(row,column))
{
board[row]=column; //no conflicts so place queen
if(row==n) //dead end
print(n); //printing the board configuration
else //try queen with next position
queen(row+1,n);
}
}
}
是的,这是回溯。因为它会尝试所有可能的候选解决方案,直到达到某个完成条件。在某些 row
值上,for(column=1;column<=n;++column)
将确保尝试 column
的每个可能值并检查 place(row,column)
是否可行,然后更深入 row
+1 .完成后,该算法将继续下一栏。
换句话说,该算法将打印 n
-queen.
回溯隐藏在函数的递归调用中queen()
。它通过尝试和错误来逐列检查列,如果发现命中则放置皇后。然后用下一行递归调用函数queen()
,遍历这个下一行一列一列,直到找到不能打败皇后的地方。并重复此递归调用,直到所有皇后都被放置。
回溯的主要思想是试错法。如果不能放置所有皇后,则算法跳回一个树枝并从下一列重新开始。
回溯是通过 queens
函数末尾隐含的 return
语句完成的。它是在检查所有列之后出现的,即您提到的详尽搜索。
为了看得更清楚,重写函数以使用显式堆栈数据结构代替隐式调用堆栈。那么回溯将明确表示为pop(stack)
.