1 #include <u.h>
2 #include <libc.h>
3 #include <draw.h>
4
5 #include "sudoku.h"
6
7 int allowbits[Brdsize] = {
8 0x00100,
9 0x00200,
10 0x00400,
11 0x00800,
12 0x01000,
13 0x02000,
14 0x04000,
15 0x08000,
16 0x10000
17 };
18
19 int boxind[Brdsize][Brdsize] = {
20 {0,1,2,9,10,11,18,19,20},
21 {3,4,5,12,13,14,21,22,23},
22 {6,7,8,15,16,17,24,25,26},
23 {27,28,29,36,37,38,45,46,47},
24 {30,31,32,39,40,41,48,49,50},
25 {33,34,35,42,43,44,51,52,53},
26 {54,55,56,63,64,65,72,73,74},
27 {57,58,59,66,67,68,75,76,77},
28 {60,61,62,69,70,71,78,79,80},
29 };
30 int colind[Brdsize][Brdsize] = {
31 {0,9,18,27,36,45,54,63,72},
32 {1,10,19,28,37,46,55,64,73},
33 {2,11,20,29,38,47,56,65,74},
34 {3,12,21,30,39,48,57,66,75},
35 {4,13,22,31,40,49,58,67,76},
36 {5,14,23,32,41,50,59,68,77},
37 {6,15,24,33,42,51,60,69,78},
38 {7,16,25,34,43,52,61,70,79},
39 {8,17,26,35,44,53,62,71,80},
40 };
41 int rowind[Brdsize][Brdsize] = {
42 {0,1,2,3,4,5,6,7,8},
43 {9,10,11,12,13,14,15,16,17},
44 {18,19,20,21,22,23,24,25,26},
45 {27,28,29,30,31,32,33,34,35},
46 {36,37,38,39,40,41,42,43,44},
47 {45,46,47,48,49,50,51,52,53},
48 {54,55,56,57,58,59,60,61,62},
49 {63,64,65,66,67,68,69,70,71},
50 {72,73,74,75,76,77,78,79,80},
51 };
52
53 static int maxlevel;
54 static int solved;
55
56 void
printbrd(int * board)57 printbrd(int *board)
58 {
59 int i;
60
61 for(i = 0; i < Psize; i++) {
62 if(i > 0 && i % Brdsize == 0)
63 print("\n");
64 print("%2.2d ", board[i] & Digit);
65 }
66 print("\n");
67 }
68
69 int
getrow(int cell)70 getrow(int cell)
71 {
72 return cell/9;
73 }
74
75 int
getcol(int cell)76 getcol(int cell)
77 {
78 return cell%9;
79 }
80
81 int
getbox(int cell)82 getbox(int cell)
83 {
84 int row = getrow(cell);
85 int col = getcol(cell);
86
87 return 3*(row/3)+ col/3;
88 }
89
90 void
setdigit(int cc,int num)91 setdigit(int cc, int num)
92 {
93 board[cc] = (board[cc] & ~Digit) | num;
94 }
95
96 int
boxcheck(int * board)97 boxcheck(int *board)
98 {
99 int i,j,d,sum,last,last2;
100
101 for (i = 0; i < 9; i++) {
102 for (d = 0;d < 9; d++) {
103 sum=0;
104 last=-1;
105 last2=-1;
106 for (j = 0; j < 9; j++) {
107 if (board[boxind[i][j]] & allowbits[d]) {
108 sum++;
109 last2=last;
110 last=boxind[i][j];
111 } else
112 sum += ((board[boxind[i][j]] & Solve)==(d << 4)) ? 1: 0;
113 }
114 if (sum==0)
115 return(0);
116 if ((sum==1)&&(last>=0))
117 if (!setallowed(board,last,d))
118 return(0);
119
120 if((sum == 2) && (last >= 0) && ( last2 >= 0) &&
121 (getrow(last) == getrow(last2))) {
122 for (j = 0; j < 9; j++) {
123 int c = rowind[getrow(last)][j];
124 if ((c != last)&&(c != last2)) {
125 if (board[c] & allowbits[d]) {
126 board[c] &= ~allowbits[d];
127 if ((board[c] & Allow)==0)
128 return(0);
129 }
130 }
131 }
132 }
133 if((sum == 2) && (last >= 0) && (last2 >= 0) &&
134 (getcol(last) == getcol(last2))) {
135 for (j = 0;j <9;j++) {
136 int c = colind[getcol(last)][j];
137 if ((c != last) && (c != last2)) {
138 if (board[c] & allowbits[d]) {
139 board[c] &= ~allowbits[d];
140 if ((board[c] & Allow) == 0)
141 return(0);
142 }
143 }
144 }
145 }
146 }
147 }
148 return(1);
149 }
150
151 int
rowcheck(int * board)152 rowcheck(int *board)
153 {
154 int i,j,d,sum,last;
155
156 for (i = 0; i < 9; i++) {
157 for (d = 0; d < 9; d++) {
158 sum = 0;
159 last = -1;
160 for (j = 0; j <9 ; j++) {
161 if (board[rowind[i][j]] & allowbits[d]) {
162 sum++;
163 last = j;
164 } else
165 sum += ((board[rowind[i][j]] & Solve) == (d << 4)) ? 1: 0;
166 }
167 if (sum == 0)
168 return(0);
169 if ((sum == 1) && (last >= 0)) {
170 if (!setallowed(board, rowind[i][last], d))
171 return(0);
172 }
173 }
174 }
175 return(1);
176 }
177
178 int
colcheck(int * board)179 colcheck(int *board)
180 {
181 int i,j,d,sum,last;
182
183 for (i = 0; i < 9; i++) {
184 for (d = 0; d < 9; d++) {
185 sum = 0;
186 last = -1;
187 for (j = 0;j < 9;j++) {
188 if (board[colind[i][j]] & allowbits[d]) {
189 sum++;
190 last = j;
191 } else
192 sum += ((board[colind[i][j]] & Solve) == (d << 4)) ? 1: 0;
193 }
194 if (sum == 0)
195 return(0);
196 if ((sum == 1) && (last >= 0)) {
197 if (!setallowed(board, colind[i][last], d))
198 return(0);
199 }
200 }
201 }
202 return(1);
203 }
204
205 int
setallowed(int * board,int cc,int num)206 setallowed(int *board, int cc, int num)
207 {
208 int j, d;
209 int row, col, box;
210
211 board[cc] &= ~Allow;
212 board[cc] = (board[cc] & ~Solve) | (num << 4);
213
214 row = getrow(cc);
215 for (j = 0; j < 9; j++) {
216 if (board[rowind[row][j]] & allowbits[num]) {
217 board[rowind[row][j]] &= ~allowbits[num];
218 if ((board[rowind[row][j]] & Allow) == 0)
219 return(0);
220 }
221 }
222
223 col = getcol(cc);
224 for (j = 0; j < 9; j++) {
225 if (board[colind[col][j]] & allowbits[num]) {
226 board[colind[col][j]] &= ~allowbits[num];
227 if ((board[colind[col][j]] & Allow) == 0)
228 return(0);
229 }
230 }
231
232 box = getbox(cc);
233 for (j = 0;j < 9;j++) {
234 if (board[boxind[box][j]] & allowbits[num]) {
235 board[boxind[box][j]] &= ~allowbits[num];
236 if ((board[boxind[box][j]] & Allow)==0)
237 return(0);
238 }
239 }
240
241 for (j = 0;j < 81; j++)
242 for (d = 0; d < 9; d++)
243 if ((board[j] & Allow) == allowbits[d])
244 if (!setallowed(board, j, d))
245 return(0);
246
247 if (!boxcheck(board)||!rowcheck(board)||!colcheck(board))
248 return(0);
249
250 for (j = 0; j < 81; j++)
251 for (d = 0; d < 9; d++)
252 if ((board[j] & Allow) == allowbits[d])
253 if (!setallowed(board, j, d))
254 return(0);
255
256 return(1);
257 }
258
259 int
chksolved(int * board)260 chksolved(int *board)
261 {
262 int i;
263
264 for (i = 0; i < Psize; i++)
265 if ((board[i] & Allow) != 0)
266 return 0;
267
268 solved = 1;
269 return solved;
270 }
271
272 int
findmove(int * board)273 findmove(int *board)
274 {
275 int i, d;
276 int s;
277
278 s = nrand(Psize);
279 for (i=(s+1)%81;i!=s;i=(i+1)%81) {
280 if (!(board[i] & Allow)) {
281 d=(board[i] & Solve) >> 4;
282 if ((board[i] & Digit)!=d)
283 return(i);
284 }
285 }
286 return(-1);
287 }
288
289 void
attempt(int * pboard,int level)290 attempt(int *pboard, int level)
291 {
292 int tb[Psize];
293 int i, j, k;
294 int s, e;
295
296 if (level > maxlevel)
297 maxlevel = level;
298
299 if (level > 25)
300 exits("level"); /* too much */
301
302 s = nrand(Psize);
303 for (i = (s + 1) % Psize; i != s; i = (i + 1) % Psize) {
304 if ((pboard[i] & Allow) != 0) {
305 e=nrand(9);
306 for (j = (e + 1) % 9; j != e; j = (j + 1) % 9) {
307 if (pboard[i] & allowbits[j]) {
308 for (k = 0; k < Psize; k++)
309 tb[k] = pboard[k];
310
311 if (setallowed(tb, i, j)) {
312 tb[i] = (tb[i] & ~Digit) | j;
313 if (chksolved(tb)) {
314 for (k = 0;k < Psize; k++)
315 pboard[k] = tb[k];
316 return; /* bad! */
317 }
318
319 attempt(tb, level + 1);
320 if (chksolved(tb)) {
321 for (k = 0; k < Psize; k++)
322 pboard[k] = tb[k];
323 return;
324 }
325 tb[i] |= Digit;
326 if (level > 25)
327 return;
328 }
329 }
330 }
331 }
332 }
333 }
334
335 void
solve(void)336 solve(void)
337 {
338 int pboard[Psize];
339 int i, c;
340
341 if (!solved) {
342 for (i = 0; i < Psize; i++)
343 pboard[i] = Allow | Solve | Digit;
344
345 for (i = 0; i < Psize; i++) {
346
347 c = board[i] & Digit;
348 if ((0 <= c) && (c < 9)) {
349 if (!setallowed(pboard,i,c)) {
350 print("starting position impossible... failed at cell %d char: %d\n", i, c + 1);
351 return;
352 }
353 }
354 }
355 attempt(pboard,0);
356
357 for (i = 0; i < Psize; i++)
358 board[i] = (board[i] & ~Solve) | (pboard[i] & Solve);
359 }
360 }
361
362 int
checklegal(int cc,int d)363 checklegal(int cc, int d)
364 {
365 int hold = board[cc];
366 int j, row, col, box;
367 board[cc] |= Digit;
368
369 row = getrow(cc);
370 for (j = 0; j < Brdsize; j++)
371 if ((board[rowind[row][j]] & Digit) == d) {
372 board[cc] = hold;
373 return(0);
374 }
375
376 col = getcol(cc);
377 for (j = 0; j < Brdsize; j++)
378 if ((board[colind[col][j]] & Digit) == d) {
379 board[cc] = hold;
380 return(0);
381 }
382
383 box = getbox(cc);
384 for (j = 0; j < Brdsize; j++)
385 if ((board[boxind[box][j]] & Digit) == d) {
386 board[cc] = hold;
387 return(0);
388 }
389
390 board[cc]=hold;
391 return(1);
392 }
393
394 void
clearp(void)395 clearp(void)
396 {
397 int i;
398 for(i = 0; i < Psize; i++) {
399 board[i] = (Allow | Solve | Digit);
400 }
401 solved = 0;
402 }
403
404 void
makep(void)405 makep(void)
406 {
407 int i,d;
408
409 do {
410 clearp();
411 maxlevel=0;
412
413 for (d = 0; d < Brdsize; d++) {
414 i = nrand(Psize);
415 if (board[i] & allowbits[d]) {
416 setallowed(board, i, d);
417 board[i] = (board[i] & ~Digit) | d;
418 }
419 }
420
421 attempt(board, 0);
422
423 for (i = 0; i < Psize; i++) {
424 if ((0 <= (board[i] & Digit)) && ((board[i] & Digit) < 9))
425 board[i] |= MLock;
426 setdigit(i, board[i] & Digit);
427 }
428
429 if (!solved) {
430 fprint(2, "failed to make puzzle\n");
431 exits("failed to make puzzle");
432 }
433
434 } while (!solved);
435
436 }
437