comparison ppc/test/queens2.p @ 0:bfdcc3820b32

Basis
author Mike Spivey <mike@cs.ox.ac.uk>
date Thu, 05 Oct 2017 08:04:15 +0100
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:bfdcc3820b32
1 (* N queens with array of choices *)
2
3 const N = 8;
4
5 proc queens(k: integer; var choice: array N of integer);
6 var y, j, q: integer; ok: boolean;
7 begin
8 if k = N then
9 print(choice)
10 else
11 y := 0;
12 while y < N do
13 j := 0; ok := true;
14 while ok and (j < k) do
15 q := choice[j];
16 ok := (q <> y) and (q+j <> y+k) and (q-j <> y-k);
17 j := j+1
18 end;
19 if ok then
20 choice[k] := y;
21 queens(k+1, choice)
22 end;
23 y := y+1
24 end
25 end
26 end;
27
28 proc print(var choice: array N of integer);
29 var x: integer;
30 begin
31 x := 0;
32 while x < N do
33 print_num(choice[x]+1);
34 x := x+1
35 end;
36 newline()
37 end;
38
39 var choice: array N of integer;
40
41 begin
42 queens(0, choice)
43 end.
44
45 (*<<
46 15863724
47 16837425
48 17468253
49 17582463
50 24683175
51 25713864
52 25741863
53 26174835
54 26831475
55 27368514
56 27581463
57 28613574
58 31758246
59 35281746
60 35286471
61 35714286
62 35841726
63 36258174
64 36271485
65 36275184
66 36418572
67 36428571
68 36814752
69 36815724
70 36824175
71 37285146
72 37286415
73 38471625
74 41582736
75 41586372
76 42586137
77 42736815
78 42736851
79 42751863
80 42857136
81 42861357
82 46152837
83 46827135
84 46831752
85 47185263
86 47382516
87 47526138
88 47531682
89 48136275
90 48157263
91 48531726
92 51468273
93 51842736
94 51863724
95 52468317
96 52473861
97 52617483
98 52814736
99 53168247
100 53172864
101 53847162
102 57138642
103 57142863
104 57248136
105 57263148
106 57263184
107 57413862
108 58413627
109 58417263
110 61528374
111 62713584
112 62714853
113 63175824
114 63184275
115 63185247
116 63571428
117 63581427
118 63724815
119 63728514
120 63741825
121 64158273
122 64285713
123 64713528
124 64718253
125 68241753
126 71386425
127 72418536
128 72631485
129 73168524
130 73825164
131 74258136
132 74286135
133 75316824
134 82417536
135 82531746
136 83162574
137 84136275
138 >>*)
139
140 (*[[
141 MODULE Main 0 0
142 IMPORT Lib 0
143 ENDHDR
144
145 PROC _queens 16 0 0
146 ! if k = N then
147 LDLW 16
148 CONST 8
149 JNEQ L2
150 ! print(choice)
151 LDLW 20
152 CONST 0
153 GLOBAL _print
154 PCALL 1
155 JUMP L3
156 LABEL L2
157 ! y := 0;
158 CONST 0
159 STLW -4
160 ! while y < N do
161 JUMP L5
162 LABEL L4
163 ! j := 0; ok := true;
164 CONST 0
165 STLW -8
166 CONST 1
167 STLC -13
168 ! while ok and (j < k) do
169 JUMP L8
170 LABEL L7
171 ! q := choice[j];
172 LDLW 20
173 LDLW -8
174 LDIW
175 STLW -12
176 ! ok := (q <> y) and (q+j <> y+k) and (q-j <> y-k);
177 LDLW -12
178 LDLW -4
179 JEQ L12
180 LDLW -12
181 LDLW -8
182 PLUS
183 LDLW -4
184 LDLW 16
185 PLUS
186 JEQ L12
187 LDLW -12
188 LDLW -8
189 MINUS
190 LDLW -4
191 LDLW 16
192 MINUS
193 JEQ L12
194 CONST 1
195 JUMP L13
196 LABEL L12
197 CONST 0
198 LABEL L13
199 STLC -13
200 ! j := j+1
201 LDLW -8
202 CONST 1
203 PLUS
204 STLW -8
205 LABEL L8
206 LDLC -13
207 JNEQZ L10
208 JUMP L9
209 LABEL L10
210 LDLW -8
211 LDLW 16
212 JLT L7
213 LABEL L9
214 ! if ok then
215 LDLC -13
216 JNEQZ L16
217 JUMP L18
218 LABEL L16
219 ! choice[k] := y;
220 LDLW -4
221 LDLW 20
222 LDLW 16
223 STIW
224 ! queens(k+1, choice)
225 LDLW 20
226 LDLW 16
227 CONST 1
228 PLUS
229 CONST 0
230 GLOBAL _queens
231 PCALL 2
232 LABEL L18
233 ! y := y+1
234 LDLW -4
235 CONST 1
236 PLUS
237 STLW -4
238 LABEL L5
239 LDLW -4
240 CONST 8
241 JLT L4
242 LABEL L3
243 RETURN
244 END
245
246 PROC _print 4 0 0
247 ! x := 0;
248 CONST 0
249 STLW -4
250 ! while x < N do
251 JUMP L20
252 LABEL L19
253 ! print_num(choice[x]+1);
254 LDLW 16
255 LDLW -4
256 LDIW
257 CONST 1
258 PLUS
259 CONST 0
260 GLOBAL lib.print_num
261 PCALL 1
262 ! x := x+1
263 LDLW -4
264 CONST 1
265 PLUS
266 STLW -4
267 LABEL L20
268 LDLW -4
269 CONST 8
270 JLT L19
271 ! newline()
272 CONST 0
273 GLOBAL lib.newline
274 PCALL 0
275 RETURN
276 END
277
278 PROC MAIN 0 0 0
279 ! queens(0, choice)
280 GLOBAL _choice
281 CONST 0
282 CONST 0
283 GLOBAL _queens
284 PCALL 2
285 RETURN
286 END
287
288 GLOVAR _choice 32
289 ! End
290 ]]*)