ACHT DAMEN Beispiel zur Lösung des 8-Damen Problems SCR# Inhalt: 2 Variablendefinition Schreib- und Lesedefinitionen Initialisieren der Damenpositionen Printpos zur Ausgabe der Damenstellung 4 Prüfworte für waagerechte und diagonale Schlag- möglichkeit 6 Stellung möglich? ACHT DAMEN SCR# Inhalt: 8 Herz des Programms. Aufstellen der nächsten Dame, bei Unmöglichkeit Backtracking 10 Programm für eine Damenposition 12 Programm zum Ausdruck aller möglichen Lösungen ( Acht Damen ) create POSITION 0 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , : POS@ 2* position + @ ; ( Linie --- Reihe ) : POS! 2* position + ! ; ( Reihe Linie --- ) : INIT 9 0 do 1 i pos! loop ; : PRINTPOS 9 1 do i 64 + emit i pos@ . space loop cr ; --> ( Acht Damen Kommentare POSITION : Array, in dem die Stellungen der Damen gespeichert werden. Mit dem Einrichten werden die Stellungen auch initialisiert. POS@ & POS! : Worte zum Auslesen bzw. Setzen der Damen- positionen INIT : alle Stellungen initialisieren, d.h. Damen auf Reihe 1 Wird für die Suche nach allen Lösungen gebraucht PRINTPOS : druckt die Stellung der Damen aus, Linie als Buchstabe, Reihe numerisch ) --> ( Acht Damen cont ) : WAAGE? ( linie reihe --- linie 0 = unmögliche position linie reihe = OK ) over 1 do dup i pos@ = if drop 0 leave then loop ; : DIAGO? ( linie reihe --- s.o. ) over 1 do ( l r ) dup i pos@ - abs ( l r dist ) 2 pick ( l r dist l ) i - = if drop 0 leave then loop ; --> ( Acht Damen WAAGE? Überprüft, ob eine Dame zwischen der aktuellen und der ersten Linie auf der gleichen Reihe steht. Besteht eine Schlagmöglichkeit wird auf dem Stack Linie 0 übergeben. Keine Schlagmöglichkeit = Linie Reihe. DIAGO? Überprüft auf Schlagen in einer Diagonalen. Stackübergabe wie Waage?. ) --> ( Acht Damen cont ) : MOEGLICH? ( line --- line flag ) dup pos@ waage? dup if diago? then ; --> ( Acht Damen MOEGLICH? Überprüft Stellung einer Dame mittels Waage? und Diago?. Braucht Liniennummer, übergibt Linie und Flag. Bei Flag = True mögliche Damenstellung ) --> ( Acht Damen cont ) : REIHE+ ( line --- line ) begin dup pos@ 8 = if 0 over pos! dup 2 = if 1 pos@ dup 8 = if drop 0 then 1+ 1 pos! 0 2 pos! else 1- then then dup pos@ 8 < until dup pos@ 1+ over pos! ; --> ( Acht Damen REIHE+ Dame wird auf Linie eine Reihe hochgesetzt falls Ende -> Backtracking, d.h. Linie vorher bearbeiten begin Reihe der aktuellen Dame Dame auf letzter Reihe ? ja: Dame auf erste Reihe zurueck Linie=B ? ja: Linie A eine Reihe weiter oder zurueck Dame B nach 0 ! <damit es mit 1 weitergeht!> nein: Linie vorher nehmen bis Dame gefunden, die man weiterstellen kann Dame ein Feld weiter ) --> ( Acht Damen Finden einer Lösung ) : ACHT_DAMEN 1 pos! 2 begin moeglich? if 1+ else reihe+ then dup 9 = until drop ; --> ( Acht Damen Finden einer Lösung ACHT_DAMEN Aufruf: Reihe der A-Dame --- A-Dame laut Eingabe setzen Setzen der B-Dame begin ist die Stellung der aktuellen Dame möglich ? ja: nächste Dame nehmen nein: Dame auf nächste Reihe stellen until Linie = 9 d.h. Feld zu Ende Stack säubern ) --> ( Acht Damen Ausgabe aller Lösungen ) : NAECHSTE_LOESUNG 8 reihe+ drop 1 pos@ acht_damen ; variable LOESUNGEN 0 , : ALLE_LOESUNGEN 0 loesungen ! init cr 1 acht_damen begin 1 pos@ 0 pos@ - 0>= while loesungen @ 1+ dup 3 .r loesungen ! 3 spaces printpos 1 pos@ 0 pos! naechste_loesung repeat ; ( Acht Damen Ausgabe aller Lösungen NAECHSTE_LOESUNG Dame auf der H-Linie wird ein Feld weiter gesetzt, dann wird Acht_Damen aufgerufen LOESUNGEN enthält Anzahl der Lösungen ALLE_LOESUNGEN findet alle Lösungen Variable Loesungen auf 0 setzen Alle Damen auf erste Reihe setzen definierten Anfangszustand schaffen = 1te Lösung while Reihe A-Dame >= Reihe A-Dame vorherige Lösung Lösungsnummer hochzählen und ausgeben Lösung ausgeben Stellung A-Dame speichern nächste Lösung suchen repeat ) ;S
