;;; (8 doof.scm)
;;;
;;; Immer noch schlimme Version, bei der alle nachfolgenden Felder
;;; versucht werden, also immer noch GENERATE AND TEST.
;;;
;;; -----------------------------------------------------------------
(require-library "breakpoint.scm")
(define max-Zahl 4)
;;; ===== Suchraum ==================================================
(define
Suchraum
(let loop
((zeile max-Zahl)
(spalte max-Zahl)
(akku ()))
(cond
((zero? zeile)
akku)
((zero? spalte)
(loop (sub1 zeile) max-Zahl akku))
(else
(loop
zeile
(sub1 spalte)
(cons (cons zeile spalte) akku))))))
;;; ===== Nachfolger ================================================
; Die Nachfolgerfunktion liefert hier einfach alle nachfolgenden
; Felder aus dem Suchraum.
(define
(Nachfolger Feld Suchraum)
(cdr (member Feld Suchraum)))
;;; ===== Tiefensuche ===============================================
(define
(Tiefensuche Suchraum)
(let
t-s
((Alternativen Suchraum)
(besucht ()))
(cond
((and
(= (length besucht) max-Zahl)
(zulaessig? besucht (cdr besucht)))
(begin
(writeln besucht)
besucht))
((= (length besucht) max-Zahl)
#f)
((null? Alternativen) #f)
((member (car Alternativen) besucht)
(t-s
(cdr Alternativen)
besucht))
((t-s
(Nachfolger (car Alternativen) Suchraum)
(cons (car Alternativen) besucht)))
(else
(t-s
(cdr Alternativen)
besucht)))))
;;; ===== zulaessig? ================================================
; Es wird nacheinander geprueft, ob sich Zeilen- oder Spaltenindizes
; und Diagonalendifferenzen wiederholen.
(define
(zulaessig? L1 L2)
; (writeln 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)))))
;;;==============================================================
(Tiefensuche Suchraum)