comparison lab4/test/queens.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 in functional form *)
2
3 const N = 8;
4
5 proc queens(k: integer; proc choice(x: integer): integer);
6 var y, j, q: integer; ok: boolean;
7
8 proc choice1(x: integer): integer;
9 begin
10 if x = k then
11 return y
12 else
13 return choice(x)
14 end;
15 end;
16
17 begin
18 if k > N then
19 print(choice)
20 else
21 y := 1;
22 while y <= N do
23 j := 1; ok := true;
24 while ok and (j < k) do
25 q := choice(j);
26 ok := (q <> y) and (q+j <> y+k) and (q-j <> y-k);
27 j := j+1
28 end;
29 if ok then queens(k+1, choice1) end;
30 y := y+1
31 end
32 end
33 end;
34
35 proc print(proc choice(x: integer): integer);
36 var x: integer;
37 begin
38 x := 1;
39 while x <= N do
40 print_num(choice(x));
41 x := x+1
42 end;
43 newline()
44 end;
45
46 proc choice0(x: integer): integer;
47 begin
48 return 0
49 end;
50
51 begin
52 queens(1, choice0)
53 end.
54
55 (*<<
56 15863724
57 16837425
58 17468253
59 17582463
60 24683175
61 25713864
62 25741863
63 26174835
64 26831475
65 27368514
66 27581463
67 28613574
68 31758246
69 35281746
70 35286471
71 35714286
72 35841726
73 36258174
74 36271485
75 36275184
76 36418572
77 36428571
78 36814752
79 36815724
80 36824175
81 37285146
82 37286415
83 38471625
84 41582736
85 41586372
86 42586137
87 42736815
88 42736851
89 42751863
90 42857136
91 42861357
92 46152837
93 46827135
94 46831752
95 47185263
96 47382516
97 47526138
98 47531682
99 48136275
100 48157263
101 48531726
102 51468273
103 51842736
104 51863724
105 52468317
106 52473861
107 52617483
108 52814736
109 53168247
110 53172864
111 53847162
112 57138642
113 57142863
114 57248136
115 57263148
116 57263184
117 57413862
118 58413627
119 58417263
120 61528374
121 62713584
122 62714853
123 63175824
124 63184275
125 63185247
126 63571428
127 63581427
128 63724815
129 63728514
130 63741825
131 64158273
132 64285713
133 64713528
134 64718253
135 68241753
136 71386425
137 72418536
138 72631485
139 73168524
140 73825164
141 74258136
142 74286135
143 75316824
144 82417536
145 82531746
146 83162574
147 84136275
148 >>*)
149
150 (*[[
151 @ picoPascal compiler output
152 .include "fixup.s"
153 .global pmain
154
155 @ proc queens(k: integer; proc choice(x: integer): integer);
156 .text
157 _queens:
158 mov ip, sp
159 stmfd sp!, {r0-r3}
160 stmfd sp!, {r4-r10, fp, ip, lr}
161 mov fp, sp
162 sub sp, sp, #8
163 @ if k > N then
164 ldr r0, [fp, #40]
165 cmp r0, #8
166 ble .L3
167 @ print(choice)
168 ldr r1, [fp, #48]
169 ldr r0, [fp, #44]
170 bl _print
171 b .L1
172 .L3:
173 @ y := 1;
174 mov r0, #1
175 str r0, [fp, #-4]
176 .L5:
177 @ while y <= N do
178 ldr r0, [fp, #-4]
179 cmp r0, #8
180 bgt .L1
181 @ j := 1; ok := true;
182 mov r4, #1
183 mov r6, #1
184 .L8:
185 @ while ok and (j < k) do
186 cmp r6, #0
187 beq .L10
188 ldr r0, [fp, #40]
189 cmp r4, r0
190 bge .L10
191 @ q := choice(j);
192 mov r0, r4
193 ldr r10, [fp, #48]
194 ldr r1, [fp, #44]
195 blx r1
196 mov r5, r0
197 @ ok := (q <> y) and (q+j <> y+k) and (q-j <> y-k);
198 ldr r7, [fp, #-4]
199 ldr r8, [fp, #40]
200 cmp r5, r7
201 mov r0, #0
202 movne r0, #1
203 add r1, r5, r4
204 add r2, r7, r8
205 cmp r1, r2
206 mov r1, #0
207 movne r1, #1
208 and r0, r0, r1
209 sub r1, r5, r4
210 sub r2, r7, r8
211 cmp r1, r2
212 mov r1, #0
213 movne r1, #1
214 and r6, r0, r1
215 @ j := j+1
216 add r4, r4, #1
217 b .L8
218 .L10:
219 @ if ok then queens(k+1, choice1) end;
220 cmp r6, #0
221 beq .L14
222 mov r2, fp
223 set r1, _choice1
224 ldr r0, [fp, #40]
225 add r0, r0, #1
226 bl _queens
227 .L14:
228 @ y := y+1
229 ldr r0, [fp, #-4]
230 add r0, r0, #1
231 str r0, [fp, #-4]
232 b .L5
233 .L1:
234 ldmfd fp, {r4-r10, fp, sp, pc}
235 .ltorg
236
237 @ proc choice1(x: integer): integer;
238 _choice1:
239 mov ip, sp
240 stmfd sp!, {r0-r1}
241 stmfd sp!, {r4-r10, fp, ip, lr}
242 mov fp, sp
243 @ if x = k then
244 ldr r4, [fp, #24]
245 ldr r0, [fp, #40]
246 ldr r1, [r4, #40]
247 cmp r0, r1
248 bne .L17
249 @ return y
250 ldr r0, [r4, #-4]
251 b .L15
252 .L17:
253 @ return choice(x)
254 ldr r4, [fp, #24]
255 ldr r0, [fp, #40]
256 ldr r10, [r4, #48]
257 ldr r1, [r4, #44]
258 blx r1
259 .L15:
260 ldmfd fp, {r4-r10, fp, sp, pc}
261 .ltorg
262
263 @ proc print(proc choice(x: integer): integer);
264 _print:
265 mov ip, sp
266 stmfd sp!, {r0-r1}
267 stmfd sp!, {r4-r10, fp, ip, lr}
268 mov fp, sp
269 @ x := 1;
270 mov r4, #1
271 .L20:
272 @ while x <= N do
273 cmp r4, #8
274 bgt .L22
275 @ print_num(choice(x));
276 mov r0, r4
277 ldr r10, [fp, #44]
278 ldr r1, [fp, #40]
279 blx r1
280 bl print_num
281 @ x := x+1
282 add r4, r4, #1
283 b .L20
284 .L22:
285 @ newline()
286 bl newline
287 ldmfd fp, {r4-r10, fp, sp, pc}
288 .ltorg
289
290 @ proc choice0(x: integer): integer;
291 _choice0:
292 mov ip, sp
293 stmfd sp!, {r0-r1}
294 stmfd sp!, {r4-r10, fp, ip, lr}
295 mov fp, sp
296 @ return 0
297 mov r0, #0
298 ldmfd fp, {r4-r10, fp, sp, pc}
299 .ltorg
300
301 pmain:
302 mov ip, sp
303 stmfd sp!, {r4-r10, fp, ip, lr}
304 mov fp, sp
305 @ queens(1, choice0)
306 mov r2, #0
307 set r1, _choice0
308 mov r0, #1
309 bl _queens
310 ldmfd fp, {r4-r10, fp, sp, pc}
311 .ltorg
312
313 @ End
314 ]]*)