comparison lab4/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+(N-1)-y] then
19 rank[y] := false; diagup[k+y] := false; diagdown[k+(N-1)-y] := false;
20 choice[k] := y; queens(k+1);
21 rank[y] := true; diagup[k+y] := true; diagdown[k+(N-1)-y] := 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 @ picoPascal compiler output
156 .include "fixup.s"
157 .global pmain
158
159 @ proc queens(k: integer);
160 .text
161 _queens:
162 mov ip, sp
163 stmfd sp!, {r0-r1}
164 stmfd sp!, {r4-r10, fp, ip, lr}
165 mov fp, sp
166 sub sp, sp, #8
167 @ if k = N then
168 ldr r0, [fp, #40]
169 cmp r0, #8
170 bne .L3
171 @ print()
172 bl _print
173 b .L1
174 .L3:
175 @ y := 0;
176 mov r4, #0
177 .L5:
178 @ while y < N do
179 cmp r4, #8
180 bge .L1
181 @ if rank[y] and diagup[k+y] and diagdown[k+(N-1)-y] then
182 set r0, _rank
183 add r7, r0, r4
184 ldrb r0, [r7]
185 cmp r0, #0
186 beq .L10
187 ldr r8, [fp, #40]
188 set r0, _diagup
189 add r0, r0, r8
190 add r9, r0, r4
191 ldrb r0, [r9]
192 cmp r0, #0
193 beq .L10
194 set r0, _diagdown
195 add r1, r8, #7
196 sub r1, r1, r4
197 add r0, r0, r1
198 ldrb r1, [r0]
199 cmp r1, #0
200 beq .L10
201 @ rank[y] := false; diagup[k+y] := false; diagdown[k+(N-1)-y] := false;
202 mov r1, #0
203 strb r1, [r7]
204 mov r1, #0
205 strb r1, [r9]
206 mov r1, #0
207 strb r1, [r0]
208 @ choice[k] := y; queens(k+1);
209 set r0, _choice
210 lsl r1, r8, #2
211 add r0, r0, r1
212 str r4, [r0]
213 add r0, r8, #1
214 bl _queens
215 @ rank[y] := true; diagup[k+y] := true; diagdown[k+(N-1)-y] := true;
216 mov r0, #1
217 set r1, _rank
218 add r1, r1, r4
219 strb r0, [r1]
220 ldr r7, [fp, #40]
221 mov r0, #1
222 set r1, _diagup
223 add r1, r1, r7
224 add r1, r1, r4
225 strb r0, [r1]
226 mov r0, #1
227 set r1, _diagdown
228 add r2, r7, #7
229 sub r2, r2, r4
230 add r1, r1, r2
231 strb r0, [r1]
232 .L10:
233 @ y := y+1
234 add r4, r4, #1
235 b .L5
236 .L1:
237 ldmfd fp, {r4-r10, fp, sp, pc}
238 .ltorg
239
240 @ proc print();
241 _print:
242 mov ip, sp
243 stmfd sp!, {r4-r10, fp, ip, lr}
244 mov fp, sp
245 @ x := 0;
246 mov r4, #0
247 .L14:
248 @ while x < N do
249 cmp r4, #8
250 bge .L16
251 @ print_num(choice[x]+1);
252 set r0, _choice
253 lsl r1, r4, #2
254 add r0, r0, r1
255 ldr r0, [r0]
256 add r0, r0, #1
257 bl print_num
258 @ x := x+1
259 add r4, r4, #1
260 b .L14
261 .L16:
262 @ newline()
263 bl newline
264 ldmfd fp, {r4-r10, fp, sp, pc}
265 .ltorg
266
267 @ proc init();
268 _init:
269 mov ip, sp
270 stmfd sp!, {r4-r10, fp, ip, lr}
271 mov fp, sp
272 @ i := 0;
273 mov r4, #0
274 .L18:
275 @ while i < N do
276 cmp r4, #8
277 bge .L20
278 @ rank[i] := true;
279 mov r0, #1
280 set r1, _rank
281 add r1, r1, r4
282 strb r0, [r1]
283 @ i := i+1
284 add r4, r4, #1
285 b .L18
286 .L20:
287 @ i := 0;
288 mov r4, #0
289 .L21:
290 @ while i < 2*N-1 do
291 cmp r4, #15
292 bge .L17
293 @ diagup[i] := true; diagdown[i] := true ;
294 mov r0, #1
295 set r1, _diagup
296 add r1, r1, r4
297 strb r0, [r1]
298 mov r0, #1
299 set r1, _diagdown
300 add r1, r1, r4
301 strb r0, [r1]
302 @ i := i+1
303 add r4, r4, #1
304 b .L21
305 .L17:
306 ldmfd fp, {r4-r10, fp, sp, pc}
307 .ltorg
308
309 pmain:
310 mov ip, sp
311 stmfd sp!, {r4-r10, fp, ip, lr}
312 mov fp, sp
313 @ init();
314 bl _init
315 @ queens(0)
316 mov r0, #0
317 bl _queens
318 ldmfd fp, {r4-r10, fp, sp, pc}
319 .ltorg
320
321 .comm _choice, 32, 4
322 .comm _rank, 8, 4
323 .comm _diagup, 15, 4
324 .comm _diagdown, 15, 4
325 @ End
326 ]]*)