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