annotate ppc/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-y+N-1] then
mike@0 19 rank[y] := false; diagup[k+y] := false; diagdown[k-y+N-1] := false;
mike@0 20 choice[k] := y; queens(k+1);
mike@0 21 rank[y] := true; diagup[k+y] := true; diagdown[k-y+N-1] := 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 MODULE Main 0 0
mike@0 156 IMPORT Lib 0
mike@0 157 ENDHDR
mike@0 158
mike@0 159 PROC _queens 16 0 0
mike@0 160 ! if k = N then
mike@0 161 LDLW 16
mike@0 162 CONST 8
mike@0 163 JNEQ L2
mike@0 164 ! print()
mike@0 165 CONST 0
mike@0 166 GLOBAL _print
mike@0 167 PCALL 0
mike@0 168 JUMP L3
mike@0 169 LABEL L2
mike@0 170 ! y := 0;
mike@0 171 CONST 0
mike@0 172 STLW -4
mike@0 173 ! while y < N do
mike@0 174 JUMP L5
mike@0 175 LABEL L4
mike@0 176 ! if rank[y] and diagup[k+y] and diagdown[k-y+N-1] then
mike@0 177 GLOBAL _rank
mike@0 178 LDLW -4
mike@0 179 LDIC
mike@0 180 JNEQZ L11
mike@0 181 JUMP L9
mike@0 182 LABEL L11
mike@0 183 GLOBAL _diagup
mike@0 184 LDLW 16
mike@0 185 LDLW -4
mike@0 186 PLUS
mike@0 187 LDIC
mike@0 188 JNEQZ L10
mike@0 189 JUMP L9
mike@0 190 LABEL L10
mike@0 191 GLOBAL _diagdown
mike@0 192 LDLW 16
mike@0 193 LDLW -4
mike@0 194 MINUS
mike@0 195 CONST 8
mike@0 196 PLUS
mike@0 197 CONST 1
mike@0 198 MINUS
mike@0 199 LDIC
mike@0 200 JNEQZ L7
mike@0 201 JUMP L9
mike@0 202 LABEL L7
mike@0 203 ! rank[y] := false; diagup[k+y] := false; diagdown[k-y+N-1] := false;
mike@0 204 CONST 0
mike@0 205 GLOBAL _rank
mike@0 206 LDLW -4
mike@0 207 STIC
mike@0 208 CONST 0
mike@0 209 GLOBAL _diagup
mike@0 210 LDLW 16
mike@0 211 LDLW -4
mike@0 212 PLUS
mike@0 213 STIC
mike@0 214 CONST 0
mike@0 215 GLOBAL _diagdown
mike@0 216 LDLW 16
mike@0 217 LDLW -4
mike@0 218 MINUS
mike@0 219 CONST 8
mike@0 220 PLUS
mike@0 221 CONST 1
mike@0 222 MINUS
mike@0 223 STIC
mike@0 224 ! choice[k] := y; queens(k+1);
mike@0 225 LDLW -4
mike@0 226 GLOBAL _choice
mike@0 227 LDLW 16
mike@0 228 STIW
mike@0 229 LDLW 16
mike@0 230 CONST 1
mike@0 231 PLUS
mike@0 232 CONST 0
mike@0 233 GLOBAL _queens
mike@0 234 PCALL 1
mike@0 235 ! rank[y] := true; diagup[k+y] := true; diagdown[k-y+N-1] := true;
mike@0 236 CONST 1
mike@0 237 GLOBAL _rank
mike@0 238 LDLW -4
mike@0 239 STIC
mike@0 240 CONST 1
mike@0 241 GLOBAL _diagup
mike@0 242 LDLW 16
mike@0 243 LDLW -4
mike@0 244 PLUS
mike@0 245 STIC
mike@0 246 CONST 1
mike@0 247 GLOBAL _diagdown
mike@0 248 LDLW 16
mike@0 249 LDLW -4
mike@0 250 MINUS
mike@0 251 CONST 8
mike@0 252 PLUS
mike@0 253 CONST 1
mike@0 254 MINUS
mike@0 255 STIC
mike@0 256 LABEL L9
mike@0 257 ! y := y+1
mike@0 258 LDLW -4
mike@0 259 CONST 1
mike@0 260 PLUS
mike@0 261 STLW -4
mike@0 262 LABEL L5
mike@0 263 LDLW -4
mike@0 264 CONST 8
mike@0 265 JLT L4
mike@0 266 LABEL L3
mike@0 267 RETURN
mike@0 268 END
mike@0 269
mike@0 270 PROC _print 4 0 0
mike@0 271 ! x := 0;
mike@0 272 CONST 0
mike@0 273 STLW -4
mike@0 274 ! while x < N do
mike@0 275 JUMP L13
mike@0 276 LABEL L12
mike@0 277 ! print_num(choice[x]+1);
mike@0 278 GLOBAL _choice
mike@0 279 LDLW -4
mike@0 280 LDIW
mike@0 281 CONST 1
mike@0 282 PLUS
mike@0 283 CONST 0
mike@0 284 GLOBAL lib.print_num
mike@0 285 PCALL 1
mike@0 286 ! x := x+1
mike@0 287 LDLW -4
mike@0 288 CONST 1
mike@0 289 PLUS
mike@0 290 STLW -4
mike@0 291 LABEL L13
mike@0 292 LDLW -4
mike@0 293 CONST 8
mike@0 294 JLT L12
mike@0 295 ! newline()
mike@0 296 CONST 0
mike@0 297 GLOBAL lib.newline
mike@0 298 PCALL 0
mike@0 299 RETURN
mike@0 300 END
mike@0 301
mike@0 302 PROC _init 4 0 0
mike@0 303 ! i := 0;
mike@0 304 CONST 0
mike@0 305 STLW -4
mike@0 306 ! while i < N do
mike@0 307 JUMP L16
mike@0 308 LABEL L15
mike@0 309 ! rank[i] := true;
mike@0 310 CONST 1
mike@0 311 GLOBAL _rank
mike@0 312 LDLW -4
mike@0 313 STIC
mike@0 314 ! i := i+1
mike@0 315 LDLW -4
mike@0 316 CONST 1
mike@0 317 PLUS
mike@0 318 STLW -4
mike@0 319 LABEL L16
mike@0 320 LDLW -4
mike@0 321 CONST 8
mike@0 322 JLT L15
mike@0 323 ! i := 0;
mike@0 324 CONST 0
mike@0 325 STLW -4
mike@0 326 ! while i < 2*N-1 do
mike@0 327 JUMP L19
mike@0 328 LABEL L18
mike@0 329 ! diagup[i] := true; diagdown[i] := true ;
mike@0 330 CONST 1
mike@0 331 GLOBAL _diagup
mike@0 332 LDLW -4
mike@0 333 STIC
mike@0 334 CONST 1
mike@0 335 GLOBAL _diagdown
mike@0 336 LDLW -4
mike@0 337 STIC
mike@0 338 ! i := i+1
mike@0 339 LDLW -4
mike@0 340 CONST 1
mike@0 341 PLUS
mike@0 342 STLW -4
mike@0 343 LABEL L19
mike@0 344 LDLW -4
mike@0 345 CONST 15
mike@0 346 JLT L18
mike@0 347 RETURN
mike@0 348 END
mike@0 349
mike@0 350 PROC MAIN 0 0 0
mike@0 351 ! init();
mike@0 352 CONST 0
mike@0 353 GLOBAL _init
mike@0 354 PCALL 0
mike@0 355 ! queens(0)
mike@0 356 CONST 0
mike@0 357 CONST 0
mike@0 358 GLOBAL _queens
mike@0 359 PCALL 1
mike@0 360 RETURN
mike@0 361 END
mike@0 362
mike@0 363 GLOVAR _choice 32
mike@0 364 GLOVAR _rank 8
mike@0 365 GLOVAR _diagup 15
mike@0 366 GLOVAR _diagdown 15
mike@0 367 ! End
mike@0 368 ]]*)