瞭解僞代碼用於反向跟蹤算法

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}），如果它與約束一致，我們會遞歸地轉到下一個變量，直到我們到達解決方案。