annotate lab4/test/sudoku.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 (* Sudoku solved with Knuth's dancing links *)
mike@0 2
mike@0 3 (* The Boolean matrix has:
mike@0 4
mike@0 5 * 81 columns Q11 .. Q99, one for each cell, since each cell must
mike@0 6 contain exactly one digit.
mike@0 7
mike@0 8 * Nine columns Cn1 .. Cn9 for each column n of the puzzle grid, since
mike@0 9 each column must contain each digit exactly once.
mike@0 10
mike@0 11 * Nine columns Rn1 .. Rn9 for each row of the puzzle grid.
mike@0 12
mike@0 13 * Nine columns Bn1 .. Bn9 for each block of the puzzle grid.
mike@0 14
mike@0 15 Each row corresponds to placing a digit in a single cell, and contains
mike@0 16 four 1's, one in each of the four groups of columns above. *)
mike@0 17
mike@0 18 type
mike@0 19 Cell = pointer to CellRec;
mike@0 20 Column = pointer to ColRec;
mike@0 21
mike@0 22 CellRec = record
mike@0 23 up, down, left, right: Cell; (* Neighbours *)
mike@0 24 column: Column; (* Top of the column *)
mike@0 25 end;
mike@0 26
mike@0 27 ColRec = record
mike@0 28 name: char; (* Column code: C, R, B, Q *)
mike@0 29 x, y: integer; (* Two digits to identify column *)
mike@0 30 size: integer; (* No. of intersecting rows *)
mike@0 31 covered: boolean; (* Whether covered *)
mike@0 32 prev, next: Column; (* Links to adjacent columns *)
mike@0 33 head: Cell; (* Dummy node for this column *)
mike@0 34 end;
mike@0 35
mike@0 36 var
mike@0 37 root: Column; (* Root of the entire matrix *)
mike@0 38
mike@0 39 (* |PrintCol| -- print the name of a column *)
mike@0 40 proc PrintCol(c: Column);
mike@0 41 begin
mike@0 42 print_char(c^.name); print_num(c^.x); print_num(c^.y)
mike@0 43 end (* PrintCol *);
mike@0 44
mike@0 45 (* |PrintRow| -- print all columns in a given row *)
mike@0 46 proc PrintRow(p: Cell);
mike@0 47 var q: Cell; n: integer;
mike@0 48 begin
mike@0 49 (* Print the columns that intersect the row *)
mike@0 50 q := p;
mike@0 51 repeat
mike@0 52 print_string(" "); PrintCol(q^.column); q := q^.right
mike@0 53 until q = p;
mike@0 54
mike@0 55 (* Print position in column *)
mike@0 56 n := 0; q := p^.column^.head;
mike@0 57 while q <> p do n := n+1; q := q^.down end;
mike@0 58 print_string("; # "); print_num(n); print_string(" of ");
mike@0 59 print_num(p^.column^.size); print_string(" choices for ");
mike@0 60 PrintCol(p^.column); newline()
mike@0 61 end (* PrintRow *);
mike@0 62
mike@0 63
mike@0 64 (* Creating the puzzle *)
mike@0 65
mike@0 66 const sqrtN = 3; N = sqrtN * sqrtN;
mike@0 67
mike@0 68 var
mike@0 69 boardCell: array N of array N of Column;
mike@0 70 boardColumn: array N of array N of Column;
mike@0 71 boardRow: array N of array N of Column;
mike@0 72 boardBlock: array N of array N of Column;
mike@0 73 boardMove: array N of array N of array N of Cell;
mike@0 74
mike@0 75 proc ColumnLink(r: Column; var p: Cell);
mike@0 76 var q: Cell;
mike@0 77 begin
mike@0 78 new(q);
mike@0 79 if p = nil then
mike@0 80 q^.right := q; q^.left := q; p := q
mike@0 81 else
mike@0 82 q^.left := p^.left; q^.right := p;
mike@0 83 p^.left^.right := q; p^.left := q
mike@0 84 end;
mike@0 85 q^.up := r^.head^.up; q^.down := r^.head;
mike@0 86 r^.head^.up^.down := q; r^.head^.up := q;
mike@0 87 q^.column := r; r^.size := r^.size+1
mike@0 88 end (* ColumnLink *);
mike@0 89
mike@0 90 proc MakeArray(var a: array N of array N of Column;
mike@0 91 name: char; m, n: integer);
mike@0 92 var
mike@0 93 i, j: integer;
mike@0 94 p: Column;
mike@0 95 begin
mike@0 96 for i := 0 to m-1 do
mike@0 97 for j := 0 to n-1 do
mike@0 98 new(p); p^.name := name; p^.x := i+1; p^.y := j+1;
mike@0 99 p^.size := 0; p^.covered := false;
mike@0 100 new(p^.head); p^.head^.down := p^.head; p^.head^.up := p^.head;
mike@0 101 p^.prev := root^.prev; p^.next := root;
mike@0 102 root^.prev^.next := p; root^.prev := p;
mike@0 103 a[i][j] := p
mike@0 104 end
mike@0 105 end
mike@0 106 end (* MakeArray *);
mike@0 107
mike@0 108 proc MakeMove(i, j, k: integer);
mike@0 109 var p: Cell;
mike@0 110 begin
mike@0 111 p := nil;
mike@0 112 ColumnLink(boardCell[i][j], p);
mike@0 113 ColumnLink(boardColumn[j][k], p);
mike@0 114 ColumnLink(boardRow[i][k], p);
mike@0 115 ColumnLink(boardBlock[sqrtN * (i div sqrtN) + j div sqrtN][k], p);
mike@0 116 boardMove[i][j][k] := p
mike@0 117 end (* MakeMove *);
mike@0 118
mike@0 119 proc MakePuzzle();
mike@0 120 var i, j, k: integer;
mike@0 121 begin
mike@0 122 new(root);
mike@0 123 root^.prev := root; root^.next := root;
mike@0 124
mike@0 125 MakeArray(boardCell, 'Q', N, N);
mike@0 126 MakeArray(boardColumn, 'C', N, N);
mike@0 127 MakeArray(boardRow, 'R', N, N);
mike@0 128 MakeArray(boardBlock, 'B', N, N);
mike@0 129
mike@0 130 for i := 0 to N-1 do
mike@0 131 for j := 0 to N-1 do
mike@0 132 for k := 0 to N-1 do
mike@0 133 MakeMove(i, j, k);
mike@0 134 end
mike@0 135 end
mike@0 136 end
mike@0 137 end (* MakePuzzle *);
mike@0 138
mike@0 139
mike@0 140 (* Exact cover problem *)
mike@0 141
mike@0 142 var
mike@0 143 choice: array N*N of Cell; (* Current set of choices *)
mike@0 144
mike@0 145 (* |Cover| -- temporarily remove a column *)
mike@0 146 proc Cover(p: Column);
mike@0 147 var q, r: Cell;
mike@0 148 begin
mike@0 149 p^.covered := true;
mike@0 150
mike@0 151 (* Remove p from the list of columns *)
mike@0 152 p^.prev^.next := p^.next; p^.next^.prev := p^.prev;
mike@0 153
mike@0 154 (* Block each row that intersects p *)
mike@0 155 q := p^.head^.down;
mike@0 156 while q <> p^.head do
mike@0 157 r := q^.right;
mike@0 158 while r <> q do
mike@0 159 r^.up^.down := r^.down; r^.down^.up := r^.up;
mike@0 160 r^.column^.size := r^.column^.size-1; r := r^.right
mike@0 161 end;
mike@0 162 q := q^.down
mike@0 163 end
mike@0 164 end (* Cover *);
mike@0 165
mike@0 166 (* |Uncover| -- reverse the effect of |Cover| *)
mike@0 167 proc Uncover(p: Column);
mike@0 168 var q, r: Cell;
mike@0 169 begin
mike@0 170 (* Restore p to the list of columns *)
mike@0 171 p^.prev^.next := p; p^.next^.prev := p;
mike@0 172
mike@0 173 (* Unblock each row that intersects p *)
mike@0 174 q := p^.head^.up;
mike@0 175 while q <> p^.head do
mike@0 176 r := q^.left;
mike@0 177 while r <> q do
mike@0 178 r^.up^.down := r; r^.down^.up := r;
mike@0 179 r^.column^.size := r^.column^.size+1; r := r^.left
mike@0 180 end;
mike@0 181 q := q^.up
mike@0 182 end;
mike@0 183
mike@0 184 p^.covered := false
mike@0 185 end (* Uncover *);
mike@0 186
mike@0 187 (* |ChooseColumn| -- select a column according to stratregy *)
mike@0 188 proc ChooseColumn(): Column;
mike@0 189 var c, col: Column;
mike@0 190 begin
mike@0 191 (* Find smallest column |col| *)
mike@0 192 col := root^.next;
mike@0 193 c := col^.next;
mike@0 194 while c <> root do
mike@0 195 if c^.size < col^.size then col := c end;
mike@0 196 c := c^.next
mike@0 197 end;
mike@0 198 return col
mike@0 199 end (* ChooseColumn *);
mike@0 200
mike@0 201 proc PrintState(level: integer);
mike@0 202 var
mike@0 203 i, j, k: integer;
mike@0 204 p: Cell;
mike@0 205 board: array N of array N of char;
mike@0 206 begin
mike@0 207 for i := 0 to N-1 do
mike@0 208 for j := 0 to N-1 do
mike@0 209 board[i][j] := '.'
mike@0 210 end
mike@0 211 end;
mike@0 212
mike@0 213 for k := 0 to level-1 do
mike@0 214 p := choice[k];
mike@0 215 while p^.column^.name <> 'Q' do p := p^.right end;
mike@0 216 i := p^.column^.x - 1; j := p^.column^.y - 1;
mike@0 217 board[i][j] := chr(p^.right^.column^.y + ord('0'))
mike@0 218 end;
mike@0 219
mike@0 220 for i := 0 to N-1 do
mike@0 221 print_string(board[i]); newline()
mike@0 222 end
mike@0 223 end (* PrintState *);
mike@0 224
mike@0 225 (* |Solve| -- find an exact cover by backtracking search *)
mike@0 226 proc Solve(level: integer);
mike@0 227 var col: Column; p, q: Cell;
mike@0 228 begin
mike@0 229 if root^.next = root then
mike@0 230 print_string("Solution:"); newline();
mike@0 231 PrintState(level); return
mike@0 232 end;
mike@0 233
mike@0 234 col := ChooseColumn();
mike@0 235 if col^.size = 0 then return end;
mike@0 236 Cover(col);
mike@0 237
mike@0 238 (* Try each row that intersects column col *)
mike@0 239 p := col^.head^.down;
mike@0 240 while p <> col^.head do
mike@0 241 choice[level] := p;
mike@0 242
mike@0 243 print_num(level); print_string(":"); PrintRow(p);
mike@0 244
mike@0 245 (* Cover other columns in row |p| *)
mike@0 246 q := p^.right;
mike@0 247 while q <> p do Cover(q^.column); q := q^.right end;
mike@0 248
mike@0 249 Solve(level+1);
mike@0 250
mike@0 251 (* Uncover other columns in row |p| *)
mike@0 252 q := p^.left;
mike@0 253 while q <> p do Uncover(q^.column); q := q^.left end;
mike@0 254
mike@0 255 p := p^.down
mike@0 256 end;
mike@0 257
mike@0 258 Uncover(col)
mike@0 259 end (* Solve *);
mike@0 260
mike@0 261 proc ChooseRow(var level: integer; p: Cell);
mike@0 262 var q: Cell;
mike@0 263 begin
mike@0 264 choice[level] := p; level := level+1;
mike@0 265 q := p;
mike@0 266 repeat
mike@0 267 if q^.column^.covered then
mike@0 268 print_string("Conflict for "); PrintCol(q^.column); newline()
mike@0 269 end;
mike@0 270 Cover(q^.column); q := q^.right
mike@0 271 until q = p
mike@0 272 end (* ChooseRow *);
mike@0 273
mike@0 274 const input =
mike@0 275 "..3....51/5.2..64../..7.5..../...63.7../2..7.8..6/..4.21.../....7.8../..81..6.9/17....5..";
mike@0 276
mike@0 277 proc Input(var level: integer);
mike@0 278 var i, j, k: integer; ch: char;
mike@0 279 begin
mike@0 280 for i := 0 to N-1 do
mike@0 281 for j := 0 to N-1 do
mike@0 282 ch := input[10*i+j];
mike@0 283 print_char(ch);
mike@0 284 if ch <> '.' then
mike@0 285 k := ord(ch) - ord('1');
mike@0 286 ChooseRow(level, boardMove[i][j][k])
mike@0 287 end
mike@0 288 end;
mike@0 289 newline()
mike@0 290 end
mike@0 291 end (* Input *);
mike@0 292
mike@0 293 (* Main program *)
mike@0 294 var level: integer;
mike@0 295
mike@0 296 begin
mike@0 297 MakePuzzle();
mike@0 298 level := 0;
mike@0 299 Input(level);
mike@0 300 Solve(level)
mike@0 301 end (* tSudoku *).
mike@0 302
mike@0 303 (*<<
mike@0 304 ..3....51
mike@0 305 5.2..64..
mike@0 306 ..7.5....
mike@0 307 ...63.7..
mike@0 308 2..7.8..6
mike@0 309 ..4.21...
mike@0 310 ....7.8..
mike@0 311 ..81..6.9
mike@0 312 17....5..
mike@0 313 28: Q85 C54 R84 B84; # 1 of 1 choices for Q85
mike@0 314 29: Q55 C59 R59 B59; # 1 of 1 choices for Q55
mike@0 315 30: Q15 C58 R18 B28; # 1 of 1 choices for Q15
mike@0 316 31: Q25 C51 R21 B21; # 1 of 1 choices for Q25
mike@0 317 32: Q64 C45 R65 B55; # 1 of 1 choices for Q64
mike@0 318 33: Q46 C64 R44 B54; # 1 of 1 choices for Q46
mike@0 319 34: Q81 C13 R83 B73; # 1 of 1 choices for Q81
mike@0 320 35: Q95 C56 R96 B86; # 1 of 1 choices for Q95
mike@0 321 36: Q93 C39 R99 B79; # 1 of 1 choices for Q93
mike@0 322 37: C17 R67 B47 Q61; # 1 of 1 choices for C17
mike@0 323 38: C36 R76 B76 Q73; # 1 of 1 choices for C36
mike@0 324 39: Q71 C14 R74 B74; # 1 of 1 choices for Q71
mike@0 325 40: C48 R98 B88 Q94; # 1 of 1 choices for C48
mike@0 326 41: C67 R17 B27 Q16; # 1 of 1 choices for C67
mike@0 327 42: C71 R51 B61 Q57; # 1 of 1 choices for C71
mike@0 328 43: Q53 C35 R55 B45; # 1 of 1 choices for Q53
mike@0 329 44: Q43 C31 R41 B41; # 1 of 1 choices for Q43
mike@0 330 45: Q52 C23 R53 B43; # 1 of 1 choices for Q52
mike@0 331 46: Q58 C84 R54 B64; # 1 of 1 choices for Q58
mike@0 332 47: C21 R31 B11 Q32; # 1 of 1 choices for C21
mike@0 333 48: C24 R14 B14 Q12; # 1 of 1 choices for C24
mike@0 334 49: C26 R66 B46 Q62; # 1 of 1 choices for C26
mike@0 335 50: C44 R34 B24 Q34; # 1 of 1 choices for C44
mike@0 336 51: C81 R71 B91 Q78; # 1 of 1 choices for C81
mike@0 337 52: C86 R36 B36 Q38; # 1 of 1 choices for C86
mike@0 338 53: C16 R16 B16 Q11; # 1 of 1 choices for C16
mike@0 339 54: C94 R94 B94 Q99; # 1 of 1 choices for C94
mike@0 340 55: C95 R45 B65 Q49; # 1 of 1 choices for C95
mike@0 341 56: C97 R27 B37 Q29; # 1 of 1 choices for C97
mike@0 342 57: C87 R87 B97 Q88; # 1 of 1 choices for C87
mike@0 343 58: R42 B62 Q48 C82; # 1 of 1 choices for R42
mike@0 344 59: Q98 C83 R93 B93; # 1 of 1 choices for Q98
mike@0 345 60: Q79 C92 R72 B92; # 1 of 1 choices for Q79
mike@0 346 61: Q72 C25 R75 B75; # 1 of 1 choices for Q72
mike@0 347 62: Q82 C22 R82 B72; # 1 of 1 choices for Q82
mike@0 348 63: Q86 C65 R85 B85; # 1 of 1 choices for Q86
mike@0 349 64: Q96 C62 R92 B82; # 1 of 1 choices for Q96
mike@0 350 65: C42 R12 B22 Q14; # 1 of 1 choices for C42
mike@0 351 66: Q17 C79 R19 B39; # 1 of 1 choices for Q17
mike@0 352 67: Q28 C88 R28 B38; # 1 of 1 choices for Q28
mike@0 353 68: Q22 C29 R29 B19; # 1 of 1 choices for Q22
mike@0 354 69: Q24 C43 R23 B23; # 1 of 1 choices for Q24
mike@0 355 70: Q31 C18 R38 B18; # 1 of 1 choices for Q31
mike@0 356 71: Q36 C69 R39 B29; # 1 of 1 choices for Q36
mike@0 357 72: Q39 C93 R33 B33; # 1 of 1 choices for Q39
mike@0 358 73: Q37 C72 R32 B32; # 1 of 1 choices for Q37
mike@0 359 74: Q41 C19 R49 B49; # 1 of 1 choices for Q41
mike@0 360 75: Q42 C28 R48 B48; # 1 of 1 choices for Q42
mike@0 361 76: Q67 C73 R63 B63; # 1 of 1 choices for Q67
mike@0 362 77: Q68 C89 R69 B69; # 1 of 1 choices for Q68
mike@0 363 78: Q69 C98 R68 B68; # 1 of 1 choices for Q69
mike@0 364 79: Q74 C49 R79 B89; # 1 of 1 choices for Q74
mike@0 365 80: Q76 C63 R73 B83; # 1 of 1 choices for Q76
mike@0 366 Solution:
mike@0 367 643287951
mike@0 368 592316487
mike@0 369 817459263
mike@0 370 981634725
mike@0 371 235798146
mike@0 372 764521398
mike@0 373 456973812
mike@0 374 328145679
mike@0 375 179862534
mike@0 376 >>*)
mike@0 377
mike@0 378 (*[[
mike@0 379 @ picoPascal compiler output
mike@0 380 .include "fixup.s"
mike@0 381 .global pmain
mike@0 382
mike@0 383 @ proc PrintCol(c: Column);
mike@0 384 .text
mike@0 385 _PrintCol:
mike@0 386 mov ip, sp
mike@0 387 stmfd sp!, {r0-r1}
mike@0 388 stmfd sp!, {r4-r10, fp, ip, lr}
mike@0 389 mov fp, sp
mike@0 390 @ print_char(c^.name); print_num(c^.x); print_num(c^.y)
mike@0 391 ldr r0, [fp, #40]
mike@0 392 ldrb r0, [r0]
mike@0 393 bl print_char
mike@0 394 ldr r0, [fp, #40]
mike@0 395 ldr r0, [r0, #4]
mike@0 396 bl print_num
mike@0 397 ldr r0, [fp, #40]
mike@0 398 ldr r0, [r0, #8]
mike@0 399 bl print_num
mike@0 400 ldmfd fp, {r4-r10, fp, sp, pc}
mike@0 401 .ltorg
mike@0 402
mike@0 403 @ proc PrintRow(p: Cell);
mike@0 404 _PrintRow:
mike@0 405 mov ip, sp
mike@0 406 stmfd sp!, {r0-r1}
mike@0 407 stmfd sp!, {r4-r10, fp, ip, lr}
mike@0 408 mov fp, sp
mike@0 409 @ q := p;
mike@0 410 ldr r4, [fp, #40]
mike@0 411 .L11:
mike@0 412 @ print_string(" "); PrintCol(q^.column); q := q^.right
mike@0 413 mov r1, #1
mike@0 414 set r0, g1
mike@0 415 bl print_string
mike@0 416 ldr r0, [r4, #16]
mike@0 417 bl _PrintCol
mike@0 418 ldr r4, [r4, #12]
mike@0 419 ldr r6, [fp, #40]
mike@0 420 cmp r4, r6
mike@0 421 bne .L11
mike@0 422 @ n := 0; q := p^.column^.head;
mike@0 423 mov r5, #0
mike@0 424 ldr r0, [r6, #16]
mike@0 425 ldr r4, [r0, #28]
mike@0 426 .L13:
mike@0 427 @ while q <> p do n := n+1; q := q^.down end;
mike@0 428 ldr r0, [fp, #40]
mike@0 429 cmp r4, r0
mike@0 430 beq .L15
mike@0 431 add r5, r5, #1
mike@0 432 ldr r4, [r4, #4]
mike@0 433 b .L13
mike@0 434 .L15:
mike@0 435 @ print_string("; # "); print_num(n); print_string(" of ");
mike@0 436 mov r1, #4
mike@0 437 set r0, g2
mike@0 438 bl print_string
mike@0 439 mov r0, r5
mike@0 440 bl print_num
mike@0 441 mov r1, #4
mike@0 442 set r0, g3
mike@0 443 bl print_string
mike@0 444 @ print_num(p^.column^.size); print_string(" choices for ");
mike@0 445 ldr r0, [fp, #40]
mike@0 446 ldr r0, [r0, #16]
mike@0 447 ldr r0, [r0, #12]
mike@0 448 bl print_num
mike@0 449 mov r1, #13
mike@0 450 set r0, g4
mike@0 451 bl print_string
mike@0 452 @ PrintCol(p^.column); newline()
mike@0 453 ldr r0, [fp, #40]
mike@0 454 ldr r0, [r0, #16]
mike@0 455 bl _PrintCol
mike@0 456 bl newline
mike@0 457 ldmfd fp, {r4-r10, fp, sp, pc}
mike@0 458 .ltorg
mike@0 459
mike@0 460 @ proc ColumnLink(r: Column; var p: Cell);
mike@0 461 _ColumnLink:
mike@0 462 mov ip, sp
mike@0 463 stmfd sp!, {r0-r1}
mike@0 464 stmfd sp!, {r4-r10, fp, ip, lr}
mike@0 465 mov fp, sp
mike@0 466 @ new(q);
mike@0 467 mov r0, #20
mike@0 468 bl new
mike@0 469 mov r4, r0
mike@0 470 @ if p = nil then
mike@0 471 ldr r0, [fp, #44]
mike@0 472 ldr r0, [r0]
mike@0 473 cmp r0, #0
mike@0 474 bne .L18
mike@0 475 @ q^.right := q; q^.left := q; p := q
mike@0 476 str r4, [r4, #12]
mike@0 477 str r4, [r4, #8]
mike@0 478 ldr r0, [fp, #44]
mike@0 479 str r4, [r0]
mike@0 480 b .L19
mike@0 481 .L18:
mike@0 482 @ q^.left := p^.left; q^.right := p;
mike@0 483 ldr r0, [fp, #44]
mike@0 484 ldr r0, [r0]
mike@0 485 ldr r0, [r0, #8]
mike@0 486 str r0, [r4, #8]
mike@0 487 ldr r0, [fp, #44]
mike@0 488 ldr r0, [r0]
mike@0 489 str r0, [r4, #12]
mike@0 490 @ p^.left^.right := q; p^.left := q
mike@0 491 ldr r0, [fp, #44]
mike@0 492 ldr r0, [r0]
mike@0 493 ldr r0, [r0, #8]
mike@0 494 str r4, [r0, #12]
mike@0 495 ldr r0, [fp, #44]
mike@0 496 ldr r0, [r0]
mike@0 497 str r4, [r0, #8]
mike@0 498 .L19:
mike@0 499 @ q^.up := r^.head^.up; q^.down := r^.head;
mike@0 500 ldr r0, [fp, #40]
mike@0 501 ldr r0, [r0, #28]
mike@0 502 ldr r0, [r0]
mike@0 503 str r0, [r4]
mike@0 504 ldr r0, [fp, #40]
mike@0 505 ldr r0, [r0, #28]
mike@0 506 str r0, [r4, #4]
mike@0 507 @ r^.head^.up^.down := q; r^.head^.up := q;
mike@0 508 ldr r0, [fp, #40]
mike@0 509 ldr r0, [r0, #28]
mike@0 510 ldr r0, [r0]
mike@0 511 str r4, [r0, #4]
mike@0 512 ldr r0, [fp, #40]
mike@0 513 ldr r0, [r0, #28]
mike@0 514 str r4, [r0]
mike@0 515 @ q^.column := r; r^.size := r^.size+1
mike@0 516 ldr r0, [fp, #40]
mike@0 517 str r0, [r4, #16]
mike@0 518 ldr r0, [fp, #40]
mike@0 519 add r5, r0, #12
mike@0 520 ldr r0, [r5]
mike@0 521 add r0, r0, #1
mike@0 522 str r0, [r5]
mike@0 523 ldmfd fp, {r4-r10, fp, sp, pc}
mike@0 524 .ltorg
mike@0 525
mike@0 526 @ proc MakeArray(var a: array N of array N of Column;
mike@0 527 _MakeArray:
mike@0 528 mov ip, sp
mike@0 529 stmfd sp!, {r0-r3}
mike@0 530 stmfd sp!, {r4-r10, fp, ip, lr}
mike@0 531 mov fp, sp
mike@0 532 sub sp, sp, #8
mike@0 533 @ for i := 0 to m-1 do
mike@0 534 mov r4, #0
mike@0 535 ldr r0, [fp, #48]
mike@0 536 sub r0, r0, #1
mike@0 537 str r0, [fp, #-8]
mike@0 538 .L21:
mike@0 539 ldr r0, [fp, #-8]
mike@0 540 cmp r4, r0
mike@0 541 bgt .L20
mike@0 542 @ for j := 0 to n-1 do
mike@0 543 mov r5, #0
mike@0 544 ldr r0, [fp, #52]
mike@0 545 sub r0, r0, #1
mike@0 546 str r0, [fp, #-4]
mike@0 547 .L23:
mike@0 548 ldr r0, [fp, #-4]
mike@0 549 cmp r5, r0
mike@0 550 bgt .L24
mike@0 551 @ new(p); p^.name := name; p^.x := i+1; p^.y := j+1;
mike@0 552 mov r0, #32
mike@0 553 bl new
mike@0 554 mov r6, r0
mike@0 555 ldrb r0, [fp, #44]
mike@0 556 strb r0, [r6]
mike@0 557 add r0, r4, #1
mike@0 558 str r0, [r6, #4]
mike@0 559 add r0, r5, #1
mike@0 560 str r0, [r6, #8]
mike@0 561 @ p^.size := 0; p^.covered := false;
mike@0 562 mov r0, #0
mike@0 563 str r0, [r6, #12]
mike@0 564 mov r0, #0
mike@0 565 strb r0, [r6, #16]
mike@0 566 @ new(p^.head); p^.head^.down := p^.head; p^.head^.up := p^.head;
mike@0 567 mov r0, #20
mike@0 568 bl new
mike@0 569 str r0, [r6, #28]
mike@0 570 ldr r7, [r6, #28]
mike@0 571 str r7, [r7, #4]
mike@0 572 ldr r7, [r6, #28]
mike@0 573 str r7, [r7]
mike@0 574 @ p^.prev := root^.prev; p^.next := root;
mike@0 575 set r7, _root
mike@0 576 ldr r0, [r7]
mike@0 577 ldr r0, [r0, #20]
mike@0 578 str r0, [r6, #20]
mike@0 579 ldr r0, [r7]
mike@0 580 str r0, [r6, #24]
mike@0 581 @ root^.prev^.next := p; root^.prev := p;
mike@0 582 ldr r0, [r7]
mike@0 583 ldr r0, [r0, #20]
mike@0 584 str r6, [r0, #24]
mike@0 585 ldr r0, [r7]
mike@0 586 str r6, [r0, #20]
mike@0 587 @ a[i][j] := p
mike@0 588 ldr r0, [fp, #40]
mike@0 589 mov r1, #36
mike@0 590 mul r1, r4, r1
mike@0 591 add r0, r0, r1
mike@0 592 lsl r1, r5, #2
mike@0 593 add r0, r0, r1
mike@0 594 str r6, [r0]
mike@0 595 add r5, r5, #1
mike@0 596 b .L23
mike@0 597 .L24:
mike@0 598 add r4, r4, #1
mike@0 599 b .L21
mike@0 600 .L20:
mike@0 601 ldmfd fp, {r4-r10, fp, sp, pc}
mike@0 602 .ltorg
mike@0 603
mike@0 604 @ proc MakeMove(i, j, k: integer);
mike@0 605 _MakeMove:
mike@0 606 mov ip, sp
mike@0 607 stmfd sp!, {r0-r3}
mike@0 608 stmfd sp!, {r4-r10, fp, ip, lr}
mike@0 609 mov fp, sp
mike@0 610 sub sp, sp, #8
mike@0 611 @ p := nil;
mike@0 612 mov r0, #0
mike@0 613 str r0, [fp, #-4]
mike@0 614 @ ColumnLink(boardCell[i][j], p);
mike@0 615 add r1, fp, #-4
mike@0 616 set r0, _boardCell
mike@0 617 ldr r2, [fp, #40]
mike@0 618 mov r3, #36
mike@0 619 mul r2, r2, r3
mike@0 620 add r0, r0, r2
mike@0 621 ldr r2, [fp, #44]
mike@0 622 lsl r2, r2, #2
mike@0 623 add r0, r0, r2
mike@0 624 ldr r0, [r0]
mike@0 625 bl _ColumnLink
mike@0 626 @ ColumnLink(boardColumn[j][k], p);
mike@0 627 add r1, fp, #-4
mike@0 628 set r0, _boardColumn
mike@0 629 ldr r2, [fp, #44]
mike@0 630 mov r3, #36
mike@0 631 mul r2, r2, r3
mike@0 632 add r0, r0, r2
mike@0 633 ldr r2, [fp, #48]
mike@0 634 lsl r2, r2, #2
mike@0 635 add r0, r0, r2
mike@0 636 ldr r0, [r0]
mike@0 637 bl _ColumnLink
mike@0 638 @ ColumnLink(boardRow[i][k], p);
mike@0 639 add r1, fp, #-4
mike@0 640 set r0, _boardRow
mike@0 641 ldr r2, [fp, #40]
mike@0 642 mov r3, #36
mike@0 643 mul r2, r2, r3
mike@0 644 add r0, r0, r2
mike@0 645 ldr r2, [fp, #48]
mike@0 646 lsl r2, r2, #2
mike@0 647 add r0, r0, r2
mike@0 648 ldr r0, [r0]
mike@0 649 bl _ColumnLink
mike@0 650 @ ColumnLink(boardBlock[sqrtN * (i div sqrtN) + j div sqrtN][k], p);
mike@0 651 mov r1, #3
mike@0 652 ldr r0, [fp, #40]
mike@0 653 bl int_div
mike@0 654 mov r1, #3
mike@0 655 mov r4, r0
mike@0 656 ldr r0, [fp, #44]
mike@0 657 bl int_div
mike@0 658 add r1, fp, #-4
mike@0 659 mov r5, r0
mike@0 660 set r0, _boardBlock
mike@0 661 mov r2, #3
mike@0 662 mul r2, r4, r2
mike@0 663 add r2, r2, r5
mike@0 664 mov r3, #36
mike@0 665 mul r2, r2, r3
mike@0 666 add r0, r0, r2
mike@0 667 ldr r2, [fp, #48]
mike@0 668 lsl r2, r2, #2
mike@0 669 add r0, r0, r2
mike@0 670 ldr r0, [r0]
mike@0 671 bl _ColumnLink
mike@0 672 @ boardMove[i][j][k] := p
mike@0 673 ldr r0, [fp, #-4]
mike@0 674 set r1, _boardMove
mike@0 675 ldr r2, [fp, #40]
mike@0 676 mov r3, #324
mike@0 677 mul r2, r2, r3
mike@0 678 add r1, r1, r2
mike@0 679 ldr r2, [fp, #44]
mike@0 680 mov r3, #36
mike@0 681 mul r2, r2, r3
mike@0 682 add r1, r1, r2
mike@0 683 ldr r2, [fp, #48]
mike@0 684 lsl r2, r2, #2
mike@0 685 add r1, r1, r2
mike@0 686 str r0, [r1]
mike@0 687 ldmfd fp, {r4-r10, fp, sp, pc}
mike@0 688 .ltorg
mike@0 689
mike@0 690 @ proc MakePuzzle();
mike@0 691 _MakePuzzle:
mike@0 692 mov ip, sp
mike@0 693 stmfd sp!, {r4-r10, fp, ip, lr}
mike@0 694 mov fp, sp
mike@0 695 sub sp, sp, #16
mike@0 696 @ new(root);
mike@0 697 mov r0, #32
mike@0 698 bl new
mike@0 699 set r7, _root
mike@0 700 str r0, [r7]
mike@0 701 @ root^.prev := root; root^.next := root;
mike@0 702 str r0, [r0, #20]
mike@0 703 ldr r7, [r7]
mike@0 704 str r7, [r7, #24]
mike@0 705 @ MakeArray(boardCell, 'Q', N, N);
mike@0 706 mov r3, #9
mike@0 707 mov r2, #9
mike@0 708 mov r1, #81
mike@0 709 set r0, _boardCell
mike@0 710 bl _MakeArray
mike@0 711 @ MakeArray(boardColumn, 'C', N, N);
mike@0 712 mov r3, #9
mike@0 713 mov r2, #9
mike@0 714 mov r1, #67
mike@0 715 set r0, _boardColumn
mike@0 716 bl _MakeArray
mike@0 717 @ MakeArray(boardRow, 'R', N, N);
mike@0 718 mov r3, #9
mike@0 719 mov r2, #9
mike@0 720 mov r1, #82
mike@0 721 set r0, _boardRow
mike@0 722 bl _MakeArray
mike@0 723 @ MakeArray(boardBlock, 'B', N, N);
mike@0 724 mov r3, #9
mike@0 725 mov r2, #9
mike@0 726 mov r1, #66
mike@0 727 set r0, _boardBlock
mike@0 728 bl _MakeArray
mike@0 729 @ for i := 0 to N-1 do
mike@0 730 mov r4, #0
mike@0 731 mov r0, #8
mike@0 732 str r0, [fp, #-12]
mike@0 733 .L27:
mike@0 734 ldr r0, [fp, #-12]
mike@0 735 cmp r4, r0
mike@0 736 bgt .L26
mike@0 737 @ for j := 0 to N-1 do
mike@0 738 mov r5, #0
mike@0 739 mov r0, #8
mike@0 740 str r0, [fp, #-8]
mike@0 741 .L29:
mike@0 742 ldr r0, [fp, #-8]
mike@0 743 cmp r5, r0
mike@0 744 bgt .L30
mike@0 745 @ for k := 0 to N-1 do
mike@0 746 mov r6, #0
mike@0 747 mov r0, #8
mike@0 748 str r0, [fp, #-4]
mike@0 749 .L31:
mike@0 750 ldr r0, [fp, #-4]
mike@0 751 cmp r6, r0
mike@0 752 bgt .L32
mike@0 753 @ MakeMove(i, j, k);
mike@0 754 mov r2, r6
mike@0 755 mov r1, r5
mike@0 756 mov r0, r4
mike@0 757 bl _MakeMove
mike@0 758 @ end
mike@0 759 add r6, r6, #1
mike@0 760 b .L31
mike@0 761 .L32:
mike@0 762 add r5, r5, #1
mike@0 763 b .L29
mike@0 764 .L30:
mike@0 765 add r4, r4, #1
mike@0 766 b .L27
mike@0 767 .L26:
mike@0 768 ldmfd fp, {r4-r10, fp, sp, pc}
mike@0 769 .ltorg
mike@0 770
mike@0 771 @ proc Cover(p: Column);
mike@0 772 _Cover:
mike@0 773 mov ip, sp
mike@0 774 stmfd sp!, {r0-r1}
mike@0 775 stmfd sp!, {r4-r10, fp, ip, lr}
mike@0 776 mov fp, sp
mike@0 777 @ p^.covered := true;
mike@0 778 mov r0, #1
mike@0 779 ldr r1, [fp, #40]
mike@0 780 strb r0, [r1, #16]
mike@0 781 @ p^.prev^.next := p^.next; p^.next^.prev := p^.prev;
mike@0 782 ldr r6, [fp, #40]
mike@0 783 ldr r0, [r6, #24]
mike@0 784 ldr r1, [r6, #20]
mike@0 785 str r0, [r1, #24]
mike@0 786 ldr r6, [fp, #40]
mike@0 787 ldr r0, [r6, #20]
mike@0 788 ldr r1, [r6, #24]
mike@0 789 str r0, [r1, #20]
mike@0 790 @ q := p^.head^.down;
mike@0 791 ldr r0, [fp, #40]
mike@0 792 ldr r0, [r0, #28]
mike@0 793 ldr r4, [r0, #4]
mike@0 794 .L34:
mike@0 795 @ while q <> p^.head do
mike@0 796 ldr r0, [fp, #40]
mike@0 797 ldr r0, [r0, #28]
mike@0 798 cmp r4, r0
mike@0 799 beq .L33
mike@0 800 @ r := q^.right;
mike@0 801 ldr r5, [r4, #12]
mike@0 802 .L37:
mike@0 803 @ while r <> q do
mike@0 804 cmp r5, r4
mike@0 805 beq .L39
mike@0 806 @ r^.up^.down := r^.down; r^.down^.up := r^.up;
mike@0 807 ldr r0, [r5, #4]
mike@0 808 ldr r1, [r5]
mike@0 809 str r0, [r1, #4]
mike@0 810 ldr r0, [r5]
mike@0 811 ldr r1, [r5, #4]
mike@0 812 str r0, [r1]
mike@0 813 @ r^.column^.size := r^.column^.size-1; r := r^.right
mike@0 814 ldr r0, [r5, #16]
mike@0 815 add r6, r0, #12
mike@0 816 ldr r0, [r6]
mike@0 817 sub r0, r0, #1
mike@0 818 str r0, [r6]
mike@0 819 ldr r5, [r5, #12]
mike@0 820 b .L37
mike@0 821 .L39:
mike@0 822 @ q := q^.down
mike@0 823 ldr r4, [r4, #4]
mike@0 824 b .L34
mike@0 825 .L33:
mike@0 826 ldmfd fp, {r4-r10, fp, sp, pc}
mike@0 827 .ltorg
mike@0 828
mike@0 829 @ proc Uncover(p: Column);
mike@0 830 _Uncover:
mike@0 831 mov ip, sp
mike@0 832 stmfd sp!, {r0-r1}
mike@0 833 stmfd sp!, {r4-r10, fp, ip, lr}
mike@0 834 mov fp, sp
mike@0 835 @ p^.prev^.next := p; p^.next^.prev := p;
mike@0 836 ldr r6, [fp, #40]
mike@0 837 ldr r0, [r6, #20]
mike@0 838 str r6, [r0, #24]
mike@0 839 ldr r6, [fp, #40]
mike@0 840 ldr r0, [r6, #24]
mike@0 841 str r6, [r0, #20]
mike@0 842 @ q := p^.head^.up;
mike@0 843 ldr r0, [fp, #40]
mike@0 844 ldr r0, [r0, #28]
mike@0 845 ldr r4, [r0]
mike@0 846 .L41:
mike@0 847 @ while q <> p^.head do
mike@0 848 ldr r0, [fp, #40]
mike@0 849 ldr r0, [r0, #28]
mike@0 850 cmp r4, r0
mike@0 851 beq .L43
mike@0 852 @ r := q^.left;
mike@0 853 ldr r5, [r4, #8]
mike@0 854 .L44:
mike@0 855 @ while r <> q do
mike@0 856 cmp r5, r4
mike@0 857 beq .L46
mike@0 858 @ r^.up^.down := r; r^.down^.up := r;
mike@0 859 ldr r0, [r5]
mike@0 860 str r5, [r0, #4]
mike@0 861 ldr r0, [r5, #4]
mike@0 862 str r5, [r0]
mike@0 863 @ r^.column^.size := r^.column^.size+1; r := r^.left
mike@0 864 ldr r0, [r5, #16]
mike@0 865 add r6, r0, #12
mike@0 866 ldr r0, [r6]
mike@0 867 add r0, r0, #1
mike@0 868 str r0, [r6]
mike@0 869 ldr r5, [r5, #8]
mike@0 870 b .L44
mike@0 871 .L46:
mike@0 872 @ q := q^.up
mike@0 873 ldr r4, [r4]
mike@0 874 b .L41
mike@0 875 .L43:
mike@0 876 @ p^.covered := false
mike@0 877 mov r0, #0
mike@0 878 ldr r1, [fp, #40]
mike@0 879 strb r0, [r1, #16]
mike@0 880 ldmfd fp, {r4-r10, fp, sp, pc}
mike@0 881 .ltorg
mike@0 882
mike@0 883 @ proc ChooseColumn(): Column;
mike@0 884 _ChooseColumn:
mike@0 885 mov ip, sp
mike@0 886 stmfd sp!, {r4-r10, fp, ip, lr}
mike@0 887 mov fp, sp
mike@0 888 @ col := root^.next;
mike@0 889 set r0, _root
mike@0 890 ldr r0, [r0]
mike@0 891 ldr r5, [r0, #24]
mike@0 892 @ c := col^.next;
mike@0 893 ldr r4, [r5, #24]
mike@0 894 .L48:
mike@0 895 @ while c <> root do
mike@0 896 set r0, _root
mike@0 897 ldr r0, [r0]
mike@0 898 cmp r4, r0
mike@0 899 beq .L50
mike@0 900 @ if c^.size < col^.size then col := c end;
mike@0 901 ldr r0, [r4, #12]
mike@0 902 ldr r1, [r5, #12]
mike@0 903 cmp r0, r1
mike@0 904 bge .L53
mike@0 905 mov r5, r4
mike@0 906 .L53:
mike@0 907 @ c := c^.next
mike@0 908 ldr r4, [r4, #24]
mike@0 909 b .L48
mike@0 910 .L50:
mike@0 911 @ return col
mike@0 912 mov r0, r5
mike@0 913 ldmfd fp, {r4-r10, fp, sp, pc}
mike@0 914 .ltorg
mike@0 915
mike@0 916 @ proc PrintState(level: integer);
mike@0 917 _PrintState:
mike@0 918 mov ip, sp
mike@0 919 stmfd sp!, {r0-r1}
mike@0 920 stmfd sp!, {r4-r10, fp, ip, lr}
mike@0 921 mov fp, sp
mike@0 922 sub sp, sp, #104
mike@0 923 @ for i := 0 to N-1 do
mike@0 924 mov r4, #0
mike@0 925 mov r0, #8
mike@0 926 str r0, [fp, #-96]
mike@0 927 .L55:
mike@0 928 ldr r0, [fp, #-96]
mike@0 929 cmp r4, r0
mike@0 930 bgt .L56
mike@0 931 @ for j := 0 to N-1 do
mike@0 932 mov r5, #0
mike@0 933 mov r0, #8
mike@0 934 str r0, [fp, #-92]
mike@0 935 .L57:
mike@0 936 ldr r0, [fp, #-92]
mike@0 937 cmp r5, r0
mike@0 938 bgt .L58
mike@0 939 @ board[i][j] := '.'
mike@0 940 mov r0, #46
mike@0 941 add r1, fp, #-85
mike@0 942 mov r2, #9
mike@0 943 mul r2, r4, r2
mike@0 944 add r1, r1, r2
mike@0 945 add r1, r1, r5
mike@0 946 strb r0, [r1]
mike@0 947 add r5, r5, #1
mike@0 948 b .L57
mike@0 949 .L58:
mike@0 950 add r4, r4, #1
mike@0 951 b .L55
mike@0 952 .L56:
mike@0 953 @ for k := 0 to level-1 do
mike@0 954 mov r6, #0
mike@0 955 ldr r0, [fp, #40]
mike@0 956 sub r0, r0, #1
mike@0 957 str r0, [fp, #-100]
mike@0 958 .L59:
mike@0 959 ldr r0, [fp, #-100]
mike@0 960 cmp r6, r0
mike@0 961 bgt .L60
mike@0 962 @ p := choice[k];
mike@0 963 set r0, _choice
mike@0 964 lsl r1, r6, #2
mike@0 965 add r0, r0, r1
mike@0 966 ldr r0, [r0]
mike@0 967 str r0, [fp, #-4]
mike@0 968 .L61:
mike@0 969 @ while p^.column^.name <> 'Q' do p := p^.right end;
mike@0 970 ldr r7, [fp, #-4]
mike@0 971 ldr r0, [r7, #16]
mike@0 972 ldrb r0, [r0]
mike@0 973 cmp r0, #81
mike@0 974 beq .L63
mike@0 975 ldr r0, [r7, #12]
mike@0 976 str r0, [fp, #-4]
mike@0 977 b .L61
mike@0 978 .L63:
mike@0 979 @ i := p^.column^.x - 1; j := p^.column^.y - 1;
mike@0 980 ldr r7, [fp, #-4]
mike@0 981 ldr r8, [r7, #16]
mike@0 982 ldr r0, [r8, #4]
mike@0 983 sub r4, r0, #1
mike@0 984 ldr r0, [r8, #8]
mike@0 985 sub r5, r0, #1
mike@0 986 @ board[i][j] := chr(p^.right^.column^.y + ord('0'))
mike@0 987 ldr r0, [r7, #12]
mike@0 988 ldr r0, [r0, #16]
mike@0 989 ldr r0, [r0, #8]
mike@0 990 add r0, r0, #48
mike@0 991 add r1, fp, #-85
mike@0 992 mov r2, #9
mike@0 993 mul r2, r4, r2
mike@0 994 add r1, r1, r2
mike@0 995 add r1, r1, r5
mike@0 996 strb r0, [r1]
mike@0 997 add r6, r6, #1
mike@0 998 b .L59
mike@0 999 .L60:
mike@0 1000 @ for i := 0 to N-1 do
mike@0 1001 mov r4, #0
mike@0 1002 mov r0, #8
mike@0 1003 str r0, [fp, #-104]
mike@0 1004 .L64:
mike@0 1005 ldr r0, [fp, #-104]
mike@0 1006 cmp r4, r0
mike@0 1007 bgt .L54
mike@0 1008 @ print_string(board[i]); newline()
mike@0 1009 mov r1, #9
mike@0 1010 add r0, fp, #-85
mike@0 1011 mov r2, #9
mike@0 1012 mul r2, r4, r2
mike@0 1013 add r0, r0, r2
mike@0 1014 bl print_string
mike@0 1015 bl newline
mike@0 1016 add r4, r4, #1
mike@0 1017 b .L64
mike@0 1018 .L54:
mike@0 1019 ldmfd fp, {r4-r10, fp, sp, pc}
mike@0 1020 .ltorg
mike@0 1021
mike@0 1022 @ proc Solve(level: integer);
mike@0 1023 _Solve:
mike@0 1024 mov ip, sp
mike@0 1025 stmfd sp!, {r0-r1}
mike@0 1026 stmfd sp!, {r4-r10, fp, ip, lr}
mike@0 1027 mov fp, sp
mike@0 1028 @ if root^.next = root then
mike@0 1029 set r0, _root
mike@0 1030 ldr r7, [r0]
mike@0 1031 ldr r0, [r7, #24]
mike@0 1032 cmp r0, r7
mike@0 1033 bne .L69
mike@0 1034 @ print_string("Solution:"); newline();
mike@0 1035 mov r1, #9
mike@0 1036 set r0, g5
mike@0 1037 bl print_string
mike@0 1038 bl newline
mike@0 1039 @ PrintState(level); return
mike@0 1040 ldr r0, [fp, #40]
mike@0 1041 bl _PrintState
mike@0 1042 b .L66
mike@0 1043 .L69:
mike@0 1044 @ col := ChooseColumn();
mike@0 1045 bl _ChooseColumn
mike@0 1046 mov r4, r0
mike@0 1047 @ if col^.size = 0 then return end;
mike@0 1048 ldr r0, [r4, #12]
mike@0 1049 cmp r0, #0
mike@0 1050 beq .L66
mike@0 1051 @ Cover(col);
mike@0 1052 mov r0, r4
mike@0 1053 bl _Cover
mike@0 1054 @ p := col^.head^.down;
mike@0 1055 ldr r0, [r4, #28]
mike@0 1056 ldr r5, [r0, #4]
mike@0 1057 .L73:
mike@0 1058 @ while p <> col^.head do
mike@0 1059 ldr r0, [r4, #28]
mike@0 1060 cmp r5, r0
mike@0 1061 beq .L75
mike@0 1062 @ choice[level] := p;
mike@0 1063 ldr r7, [fp, #40]
mike@0 1064 set r0, _choice
mike@0 1065 lsl r1, r7, #2
mike@0 1066 add r0, r0, r1
mike@0 1067 str r5, [r0]
mike@0 1068 @ print_num(level); print_string(":"); PrintRow(p);
mike@0 1069 mov r0, r7
mike@0 1070 bl print_num
mike@0 1071 mov r1, #1
mike@0 1072 set r0, g6
mike@0 1073 bl print_string
mike@0 1074 mov r0, r5
mike@0 1075 bl _PrintRow
mike@0 1076 @ q := p^.right;
mike@0 1077 ldr r6, [r5, #12]
mike@0 1078 .L76:
mike@0 1079 @ while q <> p do Cover(q^.column); q := q^.right end;
mike@0 1080 cmp r6, r5
mike@0 1081 beq .L78
mike@0 1082 ldr r0, [r6, #16]
mike@0 1083 bl _Cover
mike@0 1084 ldr r6, [r6, #12]
mike@0 1085 b .L76
mike@0 1086 .L78:
mike@0 1087 @ Solve(level+1);
mike@0 1088 ldr r0, [fp, #40]
mike@0 1089 add r0, r0, #1
mike@0 1090 bl _Solve
mike@0 1091 @ q := p^.left;
mike@0 1092 ldr r6, [r5, #8]
mike@0 1093 .L79:
mike@0 1094 @ while q <> p do Uncover(q^.column); q := q^.left end;
mike@0 1095 cmp r6, r5
mike@0 1096 beq .L81
mike@0 1097 ldr r0, [r6, #16]
mike@0 1098 bl _Uncover
mike@0 1099 ldr r6, [r6, #8]
mike@0 1100 b .L79
mike@0 1101 .L81:
mike@0 1102 @ p := p^.down
mike@0 1103 ldr r5, [r5, #4]
mike@0 1104 b .L73
mike@0 1105 .L75:
mike@0 1106 @ Uncover(col)
mike@0 1107 mov r0, r4
mike@0 1108 bl _Uncover
mike@0 1109 .L66:
mike@0 1110 ldmfd fp, {r4-r10, fp, sp, pc}
mike@0 1111 .ltorg
mike@0 1112
mike@0 1113 @ proc ChooseRow(var level: integer; p: Cell);
mike@0 1114 _ChooseRow:
mike@0 1115 mov ip, sp
mike@0 1116 stmfd sp!, {r0-r1}
mike@0 1117 stmfd sp!, {r4-r10, fp, ip, lr}
mike@0 1118 mov fp, sp
mike@0 1119 @ choice[level] := p; level := level+1;
mike@0 1120 ldr r5, [fp, #40]
mike@0 1121 ldr r0, [fp, #44]
mike@0 1122 set r1, _choice
mike@0 1123 ldr r2, [r5]
mike@0 1124 lsl r2, r2, #2
mike@0 1125 add r1, r1, r2
mike@0 1126 str r0, [r1]
mike@0 1127 ldr r0, [r5]
mike@0 1128 add r0, r0, #1
mike@0 1129 str r0, [r5]
mike@0 1130 @ q := p;
mike@0 1131 ldr r4, [fp, #44]
mike@0 1132 .L83:
mike@0 1133 @ if q^.column^.covered then
mike@0 1134 ldr r0, [r4, #16]
mike@0 1135 ldrb r0, [r0, #16]
mike@0 1136 cmp r0, #0
mike@0 1137 beq .L87
mike@0 1138 @ print_string("Conflict for "); PrintCol(q^.column); newline()
mike@0 1139 mov r1, #13
mike@0 1140 set r0, g7
mike@0 1141 bl print_string
mike@0 1142 ldr r0, [r4, #16]
mike@0 1143 bl _PrintCol
mike@0 1144 bl newline
mike@0 1145 .L87:
mike@0 1146 @ Cover(q^.column); q := q^.right
mike@0 1147 ldr r0, [r4, #16]
mike@0 1148 bl _Cover
mike@0 1149 ldr r4, [r4, #12]
mike@0 1150 ldr r0, [fp, #44]
mike@0 1151 cmp r4, r0
mike@0 1152 bne .L83
mike@0 1153 ldmfd fp, {r4-r10, fp, sp, pc}
mike@0 1154 .ltorg
mike@0 1155
mike@0 1156 @ proc Input(var level: integer);
mike@0 1157 _Input:
mike@0 1158 mov ip, sp
mike@0 1159 stmfd sp!, {r0-r1}
mike@0 1160 stmfd sp!, {r4-r10, fp, ip, lr}
mike@0 1161 mov fp, sp
mike@0 1162 sub sp, sp, #16
mike@0 1163 @ for i := 0 to N-1 do
mike@0 1164 mov r4, #0
mike@0 1165 mov r0, #8
mike@0 1166 str r0, [fp, #-12]
mike@0 1167 .L89:
mike@0 1168 ldr r0, [fp, #-12]
mike@0 1169 cmp r4, r0
mike@0 1170 bgt .L88
mike@0 1171 @ for j := 0 to N-1 do
mike@0 1172 mov r5, #0
mike@0 1173 mov r0, #8
mike@0 1174 str r0, [fp, #-8]
mike@0 1175 .L91:
mike@0 1176 ldr r0, [fp, #-8]
mike@0 1177 cmp r5, r0
mike@0 1178 bgt .L92
mike@0 1179 @ ch := input[10*i+j];
mike@0 1180 set r0, g8
mike@0 1181 mov r1, #10
mike@0 1182 mul r1, r4, r1
mike@0 1183 add r0, r0, r1
mike@0 1184 add r0, r0, r5
mike@0 1185 ldrb r7, [r0]
mike@0 1186 strb r7, [fp, #-1]
mike@0 1187 @ print_char(ch);
mike@0 1188 mov r0, r7
mike@0 1189 bl print_char
mike@0 1190 @ if ch <> '.' then
mike@0 1191 ldrb r7, [fp, #-1]
mike@0 1192 cmp r7, #46
mike@0 1193 beq .L95
mike@0 1194 @ k := ord(ch) - ord('1');
mike@0 1195 sub r6, r7, #49
mike@0 1196 @ ChooseRow(level, boardMove[i][j][k])
mike@0 1197 set r0, _boardMove
mike@0 1198 mov r1, #324
mike@0 1199 mul r1, r4, r1
mike@0 1200 add r0, r0, r1
mike@0 1201 mov r1, #36
mike@0 1202 mul r1, r5, r1
mike@0 1203 add r0, r0, r1
mike@0 1204 lsl r1, r6, #2
mike@0 1205 add r0, r0, r1
mike@0 1206 ldr r1, [r0]
mike@0 1207 ldr r0, [fp, #40]
mike@0 1208 bl _ChooseRow
mike@0 1209 .L95:
mike@0 1210 add r5, r5, #1
mike@0 1211 b .L91
mike@0 1212 .L92:
mike@0 1213 @ newline()
mike@0 1214 bl newline
mike@0 1215 add r4, r4, #1
mike@0 1216 b .L89
mike@0 1217 .L88:
mike@0 1218 ldmfd fp, {r4-r10, fp, sp, pc}
mike@0 1219 .ltorg
mike@0 1220
mike@0 1221 pmain:
mike@0 1222 mov ip, sp
mike@0 1223 stmfd sp!, {r4-r10, fp, ip, lr}
mike@0 1224 mov fp, sp
mike@0 1225 @ MakePuzzle();
mike@0 1226 bl _MakePuzzle
mike@0 1227 @ level := 0;
mike@0 1228 set r4, _level
mike@0 1229 mov r0, #0
mike@0 1230 str r0, [r4]
mike@0 1231 @ Input(level);
mike@0 1232 mov r0, r4
mike@0 1233 bl _Input
mike@0 1234 @ Solve(level)
mike@0 1235 set r0, _level
mike@0 1236 ldr r0, [r0]
mike@0 1237 bl _Solve
mike@0 1238 ldmfd fp, {r4-r10, fp, sp, pc}
mike@0 1239 .ltorg
mike@0 1240
mike@0 1241 .comm _root, 4, 4
mike@0 1242 .comm _boardCell, 324, 4
mike@0 1243 .comm _boardColumn, 324, 4
mike@0 1244 .comm _boardRow, 324, 4
mike@0 1245 .comm _boardBlock, 324, 4
mike@0 1246 .comm _boardMove, 2916, 4
mike@0 1247 .comm _choice, 324, 4
mike@0 1248 .comm _level, 4, 4
mike@0 1249 .data
mike@0 1250 g1:
mike@0 1251 .byte 32
mike@0 1252 .byte 0
mike@0 1253 g2:
mike@0 1254 .byte 59, 32, 35, 32
mike@0 1255 .byte 0
mike@0 1256 g3:
mike@0 1257 .byte 32, 111, 102, 32
mike@0 1258 .byte 0
mike@0 1259 g4:
mike@0 1260 .byte 32, 99, 104, 111, 105, 99, 101, 115, 32, 102
mike@0 1261 .byte 111, 114, 32
mike@0 1262 .byte 0
mike@0 1263 g5:
mike@0 1264 .byte 83, 111, 108, 117, 116, 105, 111, 110, 58
mike@0 1265 .byte 0
mike@0 1266 g6:
mike@0 1267 .byte 58
mike@0 1268 .byte 0
mike@0 1269 g7:
mike@0 1270 .byte 67, 111, 110, 102, 108, 105, 99, 116, 32, 102
mike@0 1271 .byte 111, 114, 32
mike@0 1272 .byte 0
mike@0 1273 g8:
mike@0 1274 .byte 46, 46, 51, 46, 46, 46, 46, 53, 49, 47
mike@0 1275 .byte 53, 46, 50, 46, 46, 54, 52, 46, 46, 47
mike@0 1276 .byte 46, 46, 55, 46, 53, 46, 46, 46, 46, 47
mike@0 1277 .byte 46, 46, 46, 54, 51, 46, 55, 46, 46, 47
mike@0 1278 .byte 50, 46, 46, 55, 46, 56, 46, 46, 54, 47
mike@0 1279 .byte 46, 46, 52, 46, 50, 49, 46, 46, 46, 47
mike@0 1280 .byte 46, 46, 46, 46, 55, 46, 56, 46, 46, 47
mike@0 1281 .byte 46, 46, 56, 49, 46, 46, 54, 46, 57, 47
mike@0 1282 .byte 49, 55, 46, 46, 46, 46, 53, 46, 46
mike@0 1283 .byte 0
mike@0 1284 @ End
mike@0 1285 ]]*)