algorithm - 理解回溯算法的伪代码

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])

我很难理解上面的逻辑。我试图通过 step thorugh 来理解 4 queen 问题，但没有。请您帮助理解上述逻辑与 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)的所有可用值，如果它符合约束条件，我们将递归地转到下一个变量，直到找到解决方案。