PROGRAM EIGHTQUEEN (INPUT,OUTPUT);                
(* PROBLEM: STELLE 8 DAMEN SO AUF EIN SCHACH-   *)
(*          BRETT, DASS SIE SICH NICHT BEDROHEN *)
(* DAS PROGRAMM STAMMT AUS DEM BUCH ALGORITHMEN *)
(* UND DATENSTRUKTUREN VON N. WIRTH (S.ANHANG 4)*)
(* UND FINDET DIE LOESUNG MIT EINER REKURSIVEN  *)
(* BACKTRACKING PROZEDUR (TRY)                  *)
                                                  
VAR     I: INTEGER;                               
    ZAEHL: INTEGER;       (* NUMMER DER LOESUNG *)
 A: ARRAY [1..8]  OF BOOLEAN;                     
    (* A[K]=TRUE, FALLS SPALTE K FREI IST       *)
 B: ARRAY [2..16] OF BOOLEAN;                     
    (* B[K]=TRUE, FALLS DIAGONALE K FREI IST    *)
 C: ARRAY [-7..7] OF BOOLEAN;                     
    (* C[K]=TRUE, FALLS DIAGONALE K FREI IST    *)
 X: ARRAY [1..8]  OF INTEGER;                     
    (* X[I]=SPALTE DER DAME IN ZEILE I          *)
                                                  
 PROCEDURE PRINT;                                 
 (* ZEIGE POSITION DER DAMEN AN:                *)
   VAR K,L: INTEGER;                              
 BEGIN                                            
  WRITELN; ZAEHL:= ZAEHL+1;                       
  WRITELN("LOESUNG:",ZAEHL:4);                    
  FOR K:=1 TO 8 DO                                
   BEGIN                                          
    FOR L:=1 TO 8 DO                              
     IF L=X[K] THEN WRITE("×")                    
     ELSE WRITE("Û");                             
    WRITELN                                       
   END                                            
 END; (* PRINT *)                                 
                                                  
 PROCEDURE TRY(I:INTEGER);                        
 (* FINDE POSITION FUER DAME IN ZEILE I         *)
   VAR J:INTEGER;                                 
 BEGIN                                            
  FOR J:= 1 TO 8 DO                               
   IF A[J] AND B[I+J] AND C[I-J] THEN             
    BEGIN (* SETZE DAME AN UNBEDROHTE POSITION: *)
     X[I]:=J;                                     
     (* NOTIERE BEDROHTE SPALTEN UND DIAGONALEN:*)
     A[J]:=FALSE;B[I+J]:=FALSE;C[I-J]:=FALSE;     
     (* FERTIG, FALLS IN ZEILE 8, SONST PROBIERE*)
     (* IN DER NAECHSTEN ZEILE WEITER:          *)
     IF I<8 THEN TRY(I+1) ELSE PRINT;             
     (* MACHE DEN ZUG RUECKGAENGIG:             *)
     A[J]:=TRUE; B[I+J]:=TRUE;C[I-J]:=TRUE        
    END                                           
 END; (* TRY *)                                   
                                                  
BEGIN                                             
 WRITELN("ACHT KOENIGINNEN:");                    
 WRITELN("=================");                    
 WRITELN;                                         
 WRITELN("(BITTE WARTEN)");                       
 ZAEHL:=0;                                        
 (* ALLE SPALTEN UND DIAGONALEN SIND UNBEDROHT: *)
 FOR I:=1  TO 8  DO A[I]:=TRUE;                   
 FOR I:=2  TO 16 DO B[I]:=TRUE;                   
 FOR I:=-7 TO 7  DO C[I]:=TRUE;                   
 (* STARTE DIE REKURSIVE SUCHE:                 *)
 TRY(1);                                          
END.