comparison lab4/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 @ picoPascal compiler output
142 .include "fixup.s"
143 .global pmain
144
145 @ proc queens(k: integer; var choice: array N of integer);
146 .text
147 _queens:
148 mov ip, sp
149 stmfd sp!, {r0-r1}
150 stmfd sp!, {r4-r10, fp, ip, lr}
151 mov fp, sp
152 sub sp, sp, #8
153 @ if k = N then
154 ldr r0, [fp, #40]
155 cmp r0, #8
156 bne .L3
157 @ print(choice)
158 ldr r0, [fp, #44]
159 bl _print
160 b .L1
161 .L3:
162 @ y := 0;
163 mov r4, #0
164 .L5:
165 @ while y < N do
166 cmp r4, #8
167 bge .L1
168 @ j := 0; ok := true;
169 mov r5, #0
170 mov r0, #1
171 strb r0, [fp, #-1]
172 .L8:
173 @ while ok and (j < k) do
174 ldrb r0, [fp, #-1]
175 cmp r0, #0
176 beq .L10
177 ldr r7, [fp, #40]
178 cmp r5, r7
179 bge .L10
180 @ q := choice[j];
181 ldr r0, [fp, #44]
182 lsl r1, r5, #2
183 add r0, r0, r1
184 ldr r6, [r0]
185 @ ok := (q <> y) and (q+j <> y+k) and (q-j <> y-k);
186 cmp r6, r4
187 mov r0, #0
188 movne r0, #1
189 add r1, r6, r5
190 add r2, r4, r7
191 cmp r1, r2
192 mov r1, #0
193 movne r1, #1
194 and r0, r0, r1
195 sub r1, r6, r5
196 sub r2, r4, r7
197 cmp r1, r2
198 mov r1, #0
199 movne r1, #1
200 and r0, r0, r1
201 strb r0, [fp, #-1]
202 @ j := j+1
203 add r5, r5, #1
204 b .L8
205 .L10:
206 @ if ok then
207 ldrb r0, [fp, #-1]
208 cmp r0, #0
209 beq .L14
210 @ choice[k] := y;
211 ldr r0, [fp, #44]
212 ldr r1, [fp, #40]
213 lsl r1, r1, #2
214 add r0, r0, r1
215 str r4, [r0]
216 @ queens(k+1, choice)
217 ldr r1, [fp, #44]
218 ldr r0, [fp, #40]
219 add r0, r0, #1
220 bl _queens
221 .L14:
222 @ y := y+1
223 add r4, r4, #1
224 b .L5
225 .L1:
226 ldmfd fp, {r4-r10, fp, sp, pc}
227 .ltorg
228
229 @ proc print(var choice: array N of integer);
230 _print:
231 mov ip, sp
232 stmfd sp!, {r0-r1}
233 stmfd sp!, {r4-r10, fp, ip, lr}
234 mov fp, sp
235 @ x := 0;
236 mov r4, #0
237 .L16:
238 @ while x < N do
239 cmp r4, #8
240 bge .L18
241 @ print_num(choice[x]+1);
242 ldr r0, [fp, #40]
243 lsl r1, r4, #2
244 add r0, r0, r1
245 ldr r0, [r0]
246 add r0, r0, #1
247 bl print_num
248 @ x := x+1
249 add r4, r4, #1
250 b .L16
251 .L18:
252 @ newline()
253 bl newline
254 ldmfd fp, {r4-r10, fp, sp, pc}
255 .ltorg
256
257 pmain:
258 mov ip, sp
259 stmfd sp!, {r4-r10, fp, ip, lr}
260 mov fp, sp
261 @ queens(0, choice)
262 set r1, _choice
263 mov r0, #0
264 bl _queens
265 ldmfd fp, {r4-r10, fp, sp, pc}
266 .ltorg
267
268 .comm _choice, 32, 4
269 @ End
270 ]]*)