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