projects / unix-history / blame
| Commit | Line | Data |
|---|---|---|
| 5bd13011 BJ |
1 | UNIX Pascal PI -- Version 1.0 (September 6, 1977) |
| 2 | ||
| 3 | Tue Sep 6 10:40 1977 eightqueens.p | |
| 4 | ||
| 5 | 1 program eightqueens(output); | |
| 6 | 2 label 13; | |
| 7 | 3 var i : integer; | |
| 8 | 4 a : array [ 1..8 ] of boolean; | |
| 9 | 5 b : array [ 2..16] of boolean; | |
| 10 | 6 c : array [-7..7 ] of boolean; | |
| 11 | 7 x : array [ 1..8 ] of integer; | |
| 12 | 8 safe : boolean; | |
| 13 | ||
| 14 | 10 procedure print; | |
| 15 | 11 var k, l: integer; | |
| 16 | 12 begin | |
| 17 | 13 writeln; | |
| 18 | 14 writeln('*** Solution to the Eight Queens Problem ***'); | |
| 19 | 15 writeln; | |
| 20 | 16 for l := 1 to 8 do begin | |
| 21 | 17 write(tab, 9 - l : 1, ' '); | |
| 22 | 18 for k := 1 to 8 do begin | |
| 23 | 19 if x[l] = k then | |
| 24 | 20 write('Q ') | |
| 25 | 21 else if odd (k + l) then | |
| 26 | 22 write('* ') | |
| 27 | 23 else | |
| 28 | 24 write('- ') | |
| 29 | 25 end; | |
| 30 | 26 writeln | |
| 31 | 27 end; | |
| 32 | 28 writeln; | |
| 33 | 29 writeln(tab, ' q q q q k k k k'); | |
| 34 | 30 writeln(tab, ' r n b b n r'); | |
| 35 | 31 writeln; | |
| 36 | 32 goto 13 | |
| 37 | 33 end ; | |
| 38 | ||
| 39 | 35 procedure trycol(j : integer); | |
| 40 | 36 var i : integer; | |
| 41 | ||
| 42 | 38 procedure setqueen; | |
| 43 | 39 begin a[i] := false; b[i+j] := false; c[i-j] := false; | |
| 44 | 40 end ; | |
| 45 | ||
| 46 | 42 procedure removequeen; | |
| 47 | 43 begin a[i] := true; b[i+j] := true; c[i-j] := true; | |
| 48 | 44 end ; | |
| 49 | ||
| 50 | 46 begin | |
| 51 | 47 repeat i := i+1; safe := a[i] and b[i+j] and c[i-j]; | |
| 52 | 48 if safe then | |
| 53 | 49 begin setqueen; x[j] := i; | |
| 54 | 50 if j < 8 then trycol(j+1) else print; | |
| 55 | 51 removequeen | |
| 56 | 52 end | |
| 57 | 53 until i = 8 | |
| 58 | 54 end; | |
| 59 | ||
| 60 | 56 begin | |
| 61 | 57 for i := 1 to 8 do a[i] := true; | |
| 62 | 58 for i := 2 to 16 do b[i] := true; | |
| 63 | 59 for i := -7 to 7 do c[i] := true; | |
| 64 | 60 trycol(1); | |
| 65 | 61 writeln('No solutions!'); | |
| 66 | 62 halt; | |
| 67 | 63 13: | |
| 68 | 64 end. | |
| 69 | Execution begins... | |
| 70 | ||
| 71 | *** Solution to the Eight Queens Problem *** | |
| 72 | ||
| 73 | 8 Q * - * - * - * | |
| 74 | 7 * - * - Q - * - | |
| 75 | 6 - * - * - * - Q | |
| 76 | 5 * - * - * Q * - | |
| 77 | 4 - * Q * - * - * | |
| 78 | 3 * - * - * - Q - | |
| 79 | 2 - Q - * - * - * | |
| 80 | 1 * - * Q * - * - | |
| 81 | ||
| 82 | q q q q k k k k | |
| 83 | r n b b n r | |
| 84 | ||
| 85 | Execution terminated | |
| 86 | 4208 statements executed in 0.52 seconds cpu time |