sys/src/games/sudoku/game.c

   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
  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
  70 getrow(int cell)
  71 {
  72         return cell/9;
  73 }
  74
  75 int
  76 getcol(int cell)
  77 {
  78         return cell%9;
  79 }
  80
  81 int
  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
  91 setdigit(int cc, int num)
  92 {
  93         board[cc] = (board[cc] & ~Digit) | num;
  94 }
  95
  96 int
  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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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 }