zurück
;;; ===== Suchraum =========================================
; Die Funktion erzeugt den Suchraum: '((1 . 1) (1 . 2) ... )'
(define
  Suchraum
  (let loop
    ((zeile 8)
     (spalte 8)
     (akku ()))

    (cond

      ((zero? zeile)
       akku)

      ((zero? spalte)
       (loop (sub1 zeile) 8 akku))

      (else

       (loop
        zeile
        (sub1 spalte)
        (cons (cons zeile spalte) akku))))))


;;; ===== zulaessig? =================================
; Es wird nacheinander geprueft, ob sich Zeilen- oder Spaltenindizes
; und Diagonalendifferenzen wiederholen.
(define
  (zulaessig? L1 L2)
  (cond
    ((null? (cdr L1)) #t)
    ((null? L2) (zulaessig? (cdr L1) (cddr L1)))
    ((= (caar L1) (caar L2)) #f)
    ((= (cdar L1) (cdar L2)) #f)
    ((= (- (caar L1) (caar L2)) (- (cdar L1) (cdar L2))) #f)
    ((= (- (caar L1) (caar L2)) (- (cdar L2) (cdar L1))) #f)
    (else
     (zulaessig? L1 (cdr L2)))))


;;; ----- Die Nachfolgerfunktion entfällt ---------------------------------
; Die Nachfolgerfunktion liefert hier einfach alle Felder,
; also den Suchraum.


;;; ===== Tiefensuche ========================================
; Standardversion der Tiefensuche mit backtracking.

(define
  (Tiefensuche)

  (let
      t-s
    ((Alternativen Suchraum)
     (besucht ()))

    (cond

      ((and
        (= (length besucht) 8)        ; Liste ist vollständig, nun testen !
        (zulaessig? besucht (cdr besucht)))
       (begin
         (writeln besucht)
         besucht))

      ((= (length besucht) 8)
       #f)

      ((null? Alternativen) #f)

      ((member (car Alternativen) besucht)        ; Besuchtliste verhindert Zyklen
       (t-s
        (cdr Alternativen)
        besucht))

      ((t-s                                      ; einfache Suche
        Suchraum                                 ; siehe Text
        (cons (car Alternativen) besucht)))

      (else
       (t-s
        (cdr Alternativen)
        besucht)))))

 
 
 

Anmerkung: Es handelt sich hierbei eigentlich nicht um eine Funktion, sondern um eine Variable. Sie wird beim Übersetzungsvorgang des Programmes mit dem beschriebenen Wert belegt und ihr Wert kann dann von den anderen Prozeduren aufgerufen werden.

Die Programmtechnik ist ein typisches Beispiel einer geschachtelten, doppelten Schleife in Scheme.

Im Kopf werden zwei Schleifenvariable definiert, nämlich die für den Spaltenindex und die für den Zeilenindex. Die lokale Variable akku ist notwendig, da nicht normal rekursiv, sondern endrekursiv (also prinzipiell iterativ) gearbeitet wird.

Eine doppelte Schleife entsteht dadurch, dass der Körper der Schleife zwei Abfragen enthält, nämlich nach den Werten der beiden lokalen Variablen zeile und spalte. Die äußere Schleife muss dabei zuerst abgefragt werden - allgemeine Regel: immer erst den Abbruchfall testen!

Entsprechend muss der Abbruchfall der inneren Schleife danach getestet werden, damit zur nächsten Zeile gewechselt werden kann, bevor der "Normalfall" des Aufrufs des nächsten Spaltenelementes durchgeführt werden kann.