### annotate lab4/test/sudoku.p @ 0:bfdcc3820b32

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