home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD1.mdf / elan / demo / nqueens.eln < prev    next >
Text File  |  1987-08-18  |  2KB  |  119 lines
  1.  
  2. PROC report (INT CONST a, TEXT CONST msg):
  3.   put (a);
  4.   put (msg)
  5. ENDPROC report;
  6.  
  7. PROC position queens from (INT CONST this row):
  8.   IF this row > n
  9.   THEN report solution
  10.   ELSE
  11.     INT VAR i;
  12.     FOR i UPTO n
  13.     REP
  14.       IF location i unchallenged
  15.       THEN
  16.         take location i;
  17.         position queens from (this row + 1);
  18.         free location i
  19.       FI
  20.     ENDREP
  21.   FI.
  22.   
  23.   take location i:
  24.     queen column [this row] := i.
  25.   
  26.   free location i:.
  27.   
  28.   location i unchallenged:
  29.     INT VAR j :: 1;
  30.     WHILE j < this row
  31.     REP
  32.       IF jth queen threatens i
  33.       THEN
  34.         LEAVE location i unchallenged WITH false
  35.       FI;
  36.       j INCR 1
  37.     ENDREP;
  38.     true.
  39.   
  40.   jth queen threatens i:
  41.     INT CONST that column :: queen column [j];
  42.     IF same column
  43.     THEN true
  44.     ELIF same diagonal to the right
  45.     THEN true
  46.     ELSE same diagonal to the left
  47.     FI.
  48.   
  49.   same column:
  50.     that column = i.
  51.   
  52.   same diagonal to the right:
  53.     that column - i = this row - j.
  54.   
  55.   same diagonal to the left:
  56.     that column - i = j - this row.
  57.   
  58.   report solution:
  59.     page;
  60.     display chessboard;
  61.     line;
  62.     INT CONST time :: exectime;
  63.     total time INCR time;
  64.     number of solutions INCR 1;
  65.     report (number of solutions, " solutions in");
  66.     report (total time, " seconds.");
  67.     line.
  68. ENDPROC position queens from;
  69.  
  70. PROC display chessboard:
  71.   INT VAR k;
  72.   FOR k UPTO n
  73.   REP
  74.     display row;
  75.     line
  76.   ENDREP.
  77.   
  78.   display row:
  79.     INT VAR l;
  80.     FOR l UPTO n
  81.     REP display position
  82.     ENDREP.
  83.   
  84.   display position:
  85.     TEXT CONST colour :: IF odd (k + l)
  86.     THEN ""176""
  87.     ELSE ""219""
  88.     FI;
  89.     IF l = queen column [k]
  90.     THEN put (colour + "Q" + colour)
  91.     ELSE put (3 * colour)
  92.     FI.
  93. ENDPROC display chessboard;
  94.  
  95. program:
  96.   how many queens;
  97.   start counting;
  98.   position queens from (1);
  99.   those were all solutions.
  100.  
  101.   how many queens:
  102.     put ("n Queens problem");
  103.     INT VAR n;
  104.     REP
  105.       line;
  106.       put ("How many queens (1<=n<10)? ");
  107.       get (n)
  108.     UNTIL n >= 1 AND n <= 10
  109.     ENDREP;
  110.     ROW 10 INT VAR queen column.
  111.   
  112.   start counting:
  113.     INT VAR total time :: 0, number of solutions :: 0.
  114.   
  115.   those were all solutions:
  116.     line;
  117.     put ("Those are all solutions.").
  118.   
  119.