了解伪代码用于反向跟踪算法

Question

要启动反向跟踪算法，可以为i = 0调用以下伪代码; X [1..0]表示空元组。

ALGORITHM Backtrack(X[1..i]) 
    //Gives a template of a generic backtracking algorithm 
    //Input: X[1..i] specifies first i promising components of a solution. 
    //Output: Alll the tuples representing the problem's solutions 
    If X[1..i] is a solution write X[1..i] 
    else 
    for each element x belongs to Si+1 consistent with X[1..i] and constraints do 
     X[i+1] <- x 
     Backtrack(X[1..i+1]) 

我很难理解上面的逻辑。我试图用步骤来解决4皇后问题，但不是。请用你的帮助理解以上逻辑与4皇后问题的步骤。

谢谢！

Answer 1

看看这个PDF文件，第25页。它有一个步骤描述与图像约4皇后解决方案与回溯。

http://ce.sharif.edu/courses/90-91/2/ce417-1/resources/root/Lectures/Chapter-6.pdf

简言之：

该算法试图找到这与所有约束条件一致的阵列X的每个元素的分配。

要做到这一点与回溯，我们使用递归函数。在每一步中，我们检查当前变量的所有可用值（域集合S _{i + 1}），如果它与约束一致，我们会递归地转到下一个变量，直到我们到达解决方案。