PROGRAM MAGICSQUARE (INPUT,OUTPUT);                         
(* DIESES PROGRAMM SOLL DIE ZAHLEN VON 1 BIS N^2 SO IN    *)
(* EINEM N*N QUADRAT ANORDNEN, DASS JEDE ZEILEN- UND      *)
(* SPALTENSUMME SOWIE DIE ADDITION DER WERTE IN DEN BEIDEN*)
(* DIAGONALEN DEN WERT MAGIC ERGIBT.                      *)
(*           N (N^2 +1)                                   *)
(*  MAGIC =  ----------                                   *)
(*                2                                       *)
(* DA EIN REINER TRIAL & ERROR ALGORITHMUS VERWENDET WIRD,*)
(* STEIGT DIE LAUFZEIT FUER WACHSENDE N EXPONENTIELL AN!  *)
(* (FUER N=4 KOENNEN SIE SCHON EIN PAAR TAGE WARTEN)      *)
                                                            
  CONST N     =  3;                                         
        N2    =  9; (* = N^2     *)                         
        N21   =  8; (* = N^2-1   *)                         
        N22   =  7; (* = N * 2 - 1;  ZU PRUEFENDE SUMMEN: *)
        (* N ZEILEN, N SPALTEN + 2 DIAGONALEN             *)
        MAGIC = 15;                                         
                                                            
  TYPE  INDEX  = 0..N21;                                    
        ELEMENT= 1..N2;                                     
        SUMS   = 0..N22;                                    
                                                            
  VAR   SQUARE  : ARRAY [INDEX] OF ELEMENT;                 
        I       : INTEGER;                                  
        ORG     : ARRAY[SUMS] OF INDEX;                     
        STEP    : ARRAY[SUMS] OF INDEX;                     
        CHECKED : REAL;     (* EVTL. GROESSER ALS MAXINT! *)
        SOLUTION: INTEGER;                                  
                                                            
PROCEDURE PRINTSOLUTION(FOUND: BOOLEAN);                    
  VAR I:INDEX;                                              
BEGIN                                                       
  IF FOUND THEN                                             
    BEGIN SOLUTION:=SOLUTION+1;                             
      WRITELN(#7 #7 'LOESUNG ',SOLUTION)                   
    END;                                                    
 WRITELN('GETESTETE ANORDNUNGEN:',CHECKED:8:0);             
 FOR I:= 0 TO N21 DO                                        
   BEGIN                                                    
     WRITE(SQUARE[I]);                                      
     IF I MOD N = N-1 THEN WRITELN;                         
   END;                                                     
 WRITELN;                                                   
END; (* PRINTSOLUTION *)                                    
                                                            
PROCEDURE PERMUTE(POSITION1: INDEX);                        
(* PERMUTIERE DIE ANORDNUNG UND PRUEFE AUF LEGAL.         *)
 VAR HELP     : ELEMENT;                                    
     POSITION2: INDEX;                                      
     I,J,K,S  : INTEGER;                                    
                                                            
BEGIN                                                       
  IF POSITION1=N21 THEN               (* PRUEFE ANORDNUNG *)
    BEGIN                                                   
      K:=0; CHECKED:= CHECKED+1;                            
      REPEAT                                                
        S:=0; J:= ORG[K];                                   
        FOR I:= 1 TO N DO                                   
          BEGIN                                             
            S:= S + SQUARE[J]; J:= J + STEP[K];             
          END;                                              
        K:=K+1;                                             
      UNTIL (S<>MAGIC) OR (K>N22);                          
      IF KEYPRESSED OR (K>N22) THEN PRINTSOLUTION(K>N22);   
    END                                                     
  ELSE                                                      
    BEGIN                                                   
      PERMUTE(POSITION1+1);                                 
      FOR POSITION2:= POSITION1+1 TO N21 DO                 
       BEGIN                                                
         HELP             := SQUARE[POSITION2];             
         SQUARE[POSITION2]:= SQUARE[POSITION1];             
         SQUARE[POSITION1]:= HELP;                          
         PERMUTE(POSITION1+1);                              
         SQUARE[POSITION1]:= SQUARE[POSITION2];             
         SQUARE[POSITION2]:= HELP;                          
       END                                                  
    END                                                     
END; (* PERMUTE *)                                          
                                                            
BEGIN                                                       
 FOR I:= 0 TO N21 DO                                        
  SQUARE[I]:= I+1;                  (* QUADRAT VORBELEGEN *)
                                                            
 (* ZU PRUEFENDE SUMMEN DEFINIEREN: *)                      
 FOR I:=0 TO N-1 DO                       (* ZEILENSUMMEN *)
   BEGIN                                                    
     ORG[I]:=I*N; STEP[I]:= 1                               
   END;                                                     
 FOR I:=0 TO N-1 DO                      (* SPALTENSUMMEN *)
   BEGIN                                                    
     ORG[I+N]:=I; STEP[I+N]:= N                             
   END;                                                     
 (* DIAGONALE VON LINKS OBEN NACH RECHTS UNTEN:           *)
 ORG [N22-1]:= 0;                                           
 STEP[N22-1]:= N+1;                                         
 (* DIAGONALE VON RECHTS OBEN NACH LINKS UNTEN:           *)
 ORG [N22  ]:= N-1;                                         
 STEP[N22  ]:= N-1;                                         
                                                            
 (* JETZT KANN GEPRUEFT WERDEN *)                           
 WRITELN('ANZEIGE DER LAUFENDEN SUCHPOSITION');             
 WRITELN('BEI TASTENDRUCK');                                
                                                            
 (* BEI 80-ZEICHEN-BILDSCHIRM 2MHZ WAEHLEN: *)              
 IF RWINDOW(2)=80 THEN FAST;                                
                                                            
 CHECKED:=0; SOLUTION:=0;                                   
 PERMUTE(0);                                                
 WRITELN(SOLUTION, ' LOESUNGEN GEFUNDEN.');                 
END.