LISPバックトラッキング

Question

LISPでバックトラッキングを実行する方法を教えてもらえますか？すべての例やリンクが評価されます。 私はGoogleにしようとしましたが、誰も私が理解するのに十分な単純な例はありませんでした。

おかげ

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

。私はデモンストレーションから実際の作業コードに変わるサポートコードを使ってデモンストレーションを隠すのをやめました。