comparison ppc/test/queens3.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 bitmap arrays *)
2
3 const N = 8;
4
5 var
6 choice: array N of integer;
7 rank: array N of boolean;
8 diagup, diagdown: array 2 * N - 1 of boolean;
9
10 proc queens(k: integer);
11 var y, j, q: integer; ok: boolean;
12 begin
13 if k = N then
14 print()
15 else
16 y := 0;
17 while y < N do
18 if rank[y] and diagup[k+y] and diagdown[k-y+N-1] then
19 rank[y] := false; diagup[k+y] := false; diagdown[k-y+N-1] := false;
20 choice[k] := y; queens(k+1);
21 rank[y] := true; diagup[k+y] := true; diagdown[k-y+N-1] := true;
22 end;
23 y := y+1
24 end
25 end
26 end;
27
28 proc print();
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 proc init();
40 var i: integer;
41 begin
42 i := 0;
43 while i < N do
44 rank[i] := true;
45 i := i+1
46 end;
47 i := 0;
48 while i < 2*N-1 do
49 diagup[i] := true; diagdown[i] := true ;
50 i := i+1
51 end
52 end;
53
54 begin
55 init();
56 queens(0)
57 end.
58
59 (*<<
60 15863724
61 16837425
62 17468253
63 17582463
64 24683175
65 25713864
66 25741863
67 26174835
68 26831475
69 27368514
70 27581463
71 28613574
72 31758246
73 35281746
74 35286471
75 35714286
76 35841726
77 36258174
78 36271485
79 36275184
80 36418572
81 36428571
82 36814752
83 36815724
84 36824175
85 37285146
86 37286415
87 38471625
88 41582736
89 41586372
90 42586137
91 42736815
92 42736851
93 42751863
94 42857136
95 42861357
96 46152837
97 46827135
98 46831752
99 47185263
100 47382516
101 47526138
102 47531682
103 48136275
104 48157263
105 48531726
106 51468273
107 51842736
108 51863724
109 52468317
110 52473861
111 52617483
112 52814736
113 53168247
114 53172864
115 53847162
116 57138642
117 57142863
118 57248136
119 57263148
120 57263184
121 57413862
122 58413627
123 58417263
124 61528374
125 62713584
126 62714853
127 63175824
128 63184275
129 63185247
130 63571428
131 63581427
132 63724815
133 63728514
134 63741825
135 64158273
136 64285713
137 64713528
138 64718253
139 68241753
140 71386425
141 72418536
142 72631485
143 73168524
144 73825164
145 74258136
146 74286135
147 75316824
148 82417536
149 82531746
150 83162574
151 84136275
152 >>*)
153
154 (*[[
155 MODULE Main 0 0
156 IMPORT Lib 0
157 ENDHDR
158
159 PROC _queens 16 0 0
160 ! if k = N then
161 LDLW 16
162 CONST 8
163 JNEQ L2
164 ! print()
165 CONST 0
166 GLOBAL _print
167 PCALL 0
168 JUMP L3
169 LABEL L2
170 ! y := 0;
171 CONST 0
172 STLW -4
173 ! while y < N do
174 JUMP L5
175 LABEL L4
176 ! if rank[y] and diagup[k+y] and diagdown[k-y+N-1] then
177 GLOBAL _rank
178 LDLW -4
179 LDIC
180 JNEQZ L11
181 JUMP L9
182 LABEL L11
183 GLOBAL _diagup
184 LDLW 16
185 LDLW -4
186 PLUS
187 LDIC
188 JNEQZ L10
189 JUMP L9
190 LABEL L10
191 GLOBAL _diagdown
192 LDLW 16
193 LDLW -4
194 MINUS
195 CONST 8
196 PLUS
197 CONST 1
198 MINUS
199 LDIC
200 JNEQZ L7
201 JUMP L9
202 LABEL L7
203 ! rank[y] := false; diagup[k+y] := false; diagdown[k-y+N-1] := false;
204 CONST 0
205 GLOBAL _rank
206 LDLW -4
207 STIC
208 CONST 0
209 GLOBAL _diagup
210 LDLW 16
211 LDLW -4
212 PLUS
213 STIC
214 CONST 0
215 GLOBAL _diagdown
216 LDLW 16
217 LDLW -4
218 MINUS
219 CONST 8
220 PLUS
221 CONST 1
222 MINUS
223 STIC
224 ! choice[k] := y; queens(k+1);
225 LDLW -4
226 GLOBAL _choice
227 LDLW 16
228 STIW
229 LDLW 16
230 CONST 1
231 PLUS
232 CONST 0
233 GLOBAL _queens
234 PCALL 1
235 ! rank[y] := true; diagup[k+y] := true; diagdown[k-y+N-1] := true;
236 CONST 1
237 GLOBAL _rank
238 LDLW -4
239 STIC
240 CONST 1
241 GLOBAL _diagup
242 LDLW 16
243 LDLW -4
244 PLUS
245 STIC
246 CONST 1
247 GLOBAL _diagdown
248 LDLW 16
249 LDLW -4
250 MINUS
251 CONST 8
252 PLUS
253 CONST 1
254 MINUS
255 STIC
256 LABEL L9
257 ! y := y+1
258 LDLW -4
259 CONST 1
260 PLUS
261 STLW -4
262 LABEL L5
263 LDLW -4
264 CONST 8
265 JLT L4
266 LABEL L3
267 RETURN
268 END
269
270 PROC _print 4 0 0
271 ! x := 0;
272 CONST 0
273 STLW -4
274 ! while x < N do
275 JUMP L13
276 LABEL L12
277 ! print_num(choice[x]+1);
278 GLOBAL _choice
279 LDLW -4
280 LDIW
281 CONST 1
282 PLUS
283 CONST 0
284 GLOBAL lib.print_num
285 PCALL 1
286 ! x := x+1
287 LDLW -4
288 CONST 1
289 PLUS
290 STLW -4
291 LABEL L13
292 LDLW -4
293 CONST 8
294 JLT L12
295 ! newline()
296 CONST 0
297 GLOBAL lib.newline
298 PCALL 0
299 RETURN
300 END
301
302 PROC _init 4 0 0
303 ! i := 0;
304 CONST 0
305 STLW -4
306 ! while i < N do
307 JUMP L16
308 LABEL L15
309 ! rank[i] := true;
310 CONST 1
311 GLOBAL _rank
312 LDLW -4
313 STIC
314 ! i := i+1
315 LDLW -4
316 CONST 1
317 PLUS
318 STLW -4
319 LABEL L16
320 LDLW -4
321 CONST 8
322 JLT L15
323 ! i := 0;
324 CONST 0
325 STLW -4
326 ! while i < 2*N-1 do
327 JUMP L19
328 LABEL L18
329 ! diagup[i] := true; diagdown[i] := true ;
330 CONST 1
331 GLOBAL _diagup
332 LDLW -4
333 STIC
334 CONST 1
335 GLOBAL _diagdown
336 LDLW -4
337 STIC
338 ! i := i+1
339 LDLW -4
340 CONST 1
341 PLUS
342 STLW -4
343 LABEL L19
344 LDLW -4
345 CONST 15
346 JLT L18
347 RETURN
348 END
349
350 PROC MAIN 0 0 0
351 ! init();
352 CONST 0
353 GLOBAL _init
354 PCALL 0
355 ! queens(0)
356 CONST 0
357 CONST 0
358 GLOBAL _queens
359 PCALL 1
360 RETURN
361 END
362
363 GLOVAR _choice 32
364 GLOVAR _rank 8
365 GLOVAR _diagup 15
366 GLOVAR _diagdown 15
367 ! End
368 ]]*)