LISP Backtracking

Question

有人能指導我或解釋如何在LISP中執行回溯？任何示例或鏈接將不勝感激。 我曾嘗試谷歌，但是他們沒有一個簡單的例子足以讓我理解。

感謝

Answer 1

典型的方式是讓非可變狀態傳下來的調用堆棧，用輔助功能以目前的狀態，返回一個新的狀態爲「假」的突變。

一種可能的（雖然相當不理想的）數獨解算器將隨後是：

;;; Use a list of 81 integers to represent a sudoku board, 
;;; each number 1-9 represents itself, 0 represents a blank 
(defun sudoku-solver (board) 
    (cond ((notany #'zerop board) 
    (if (sudoku-solved-p board) 
     board 
     nil)) 
    (t (let ((positions (sudoku-all-blanks board))) 
     (loop for position in positions 
      do (loop for number in '(1 2 3 4 5 6 7 8 9) 
       do (let ((result (sudoku-solver 
         (sudoku-set board 
          position 
          number)))) 
        (when result 
       (return-from sudoku-solver result))))))))) 

這將自動回溯，直到找到一個解。我已經跳過模糊的演示與支持代碼，將演示變成實際工作代碼。