src/classes/net/sourceforge/plantuml/sudoku/DLXEngine.java

   1 /****************************************************************************
   2  * DLXEngine.java
   3  *
   4  * Created on den 30 december 2005, 01:04
   5  *
   6  * DLXEngine
   7  * Sudoku puzzle generator and solver based on the suexg and suexk by
   8  * Gunter Stertenbrink. Suexg and suexk are C implementations of the
   9  * Dancing Links algorithm by Donald Knuth and optimized for performance
  10  * which means that certain cleanup work has been done. There is still
  11  * lots of these activities left to do, however, the code is nasty and
  12  * hard to read - but extremely efficient.
  13  *
  14  * The code is public domain so feel free to use it.
  15  *****************************************************************************/
  16
  17 package net.sourceforge.plantuml.sudoku;
  18
  19 import java.io.FileOutputStream;
  20 import java.io.IOException;
  21 import java.util.Date;
  22 import java.util.Random;
  23
  24 /*******************************************************************************
  25  * dlx_solver solve any Sudoku in a fraction of a second. Input is a string of
  26  * dots and digits representing the puzzle to solve and output is the solved
  27  * puzzle.
  28  *
  29  * @author Rolf Sandberg
  30  ******************************************************************************/
  31 class dlx_solver {
  32         static final int M = 8; // change this for larger grids. Use symbols as in
  33                                                         // L[] below
  34         static final int M2 = M * M;
  35         static final int M4 = M2 * M2;
  36
  37         /** Pseudo-random number generator */
  38         long MWC() {
  39                 return random.nextLong();
  40         }
  41
  42         int A0[][] = new int[M2 + 9][M2 + 9], A[][] = new int[M2 + 9][M2 + 9], Rows[] = new int[4 * M4 + 9],
  43                         Cols[] = new int[M2 * M4 + 9], Row[][] = new int[4 * M4 + 9][M2 + 9];
  44         int Col[][] = new int[M2 * M4 + 9][5], Ur[] = new int[M2 * M4 + 9], Uc[] = new int[4 * M4 + 9], V[] = new int[M2
  45                         * M4 + 9];
  46         int C[] = new int[M4 + 9], I[] = new int[M4 + 9], T[] = new int[M2 * M4 + 9], P[] = new int[M2 * M4 + 9];
  47         int Mr[] = { 0, 1, 63, 1023, 4095, 16383, 46655, 131071, 262143 };
  48         int Mc[] = { 0, 1, 63, 511, 1023, 4095, 8191, 16383, 16383 };
  49         int Mw[] = { 0, 1, 3, 15, 15, 31, 63, 63, 63 };
  50
  51         int nocheck = 0, max, _try_;
  52         final int rnd = 0;
  53         int min, clues, gu, tries;
  54         long Node[] = new long[M4 + 9];
  55         long nodes, tnodes, solutions, vmax, smax, time0, time1, t1, x1;
  56         double xx, yy;
  57         int q, a, p, i, i1, j, k, l, r, r1, c, c1, c2, n, N = 0, N2, N4, m, m0, m1, x, y, s;
  58         char L[] = { '.', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J',
  59                         'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z', 'a', 'b', 'c', 'd', 'e',
  60                         'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z',
  61                         '#', '*', '~' };
  62
  63         /** State machine states */
  64         static final int M6 = 10;
  65         static final int M7 = 11;
  66         static final int RESTART = 12;
  67         static final int M22 = 13;
  68         static final int M3 = 14;
  69         static final int M44 = 15;
  70         static final int NEXT_TRY = 16;
  71         static final int END = 30;
  72
  73         /**
  74          * Solver function. Input parameter: A puzzle to solve Output: The solved
  75          * puzzle
  76          */
  77         String solve(String puzzle) {
  78                 System.out.println("puzzle = "+puzzle);
  79                 String result = new String();
  80                 int STATE = M6;
  81
  82                 vmax = 4000000;
  83                 smax = 25;
  84                 p = 1;
  85                 q = 0;
  86
  87                 if (q > 0) {
  88                         vmax = 99999999;
  89                         smax = 99999999;
  90                 }
  91
  92                 N = 3;
  93                 N2 = N * N;
  94                 N4 = N2 * N2;
  95                 m = 4 * N4;
  96                 n = N2 * N4;
  97
  98                 if (puzzle.length() < N4) {
  99                         return "Error, puzzle incomplete";
 100                 }
 101
 102                 while (STATE != END) {
 103                         switch (STATE) {
 104                         case M6:
 105                                 clues = 0;
 106                                 i = 0;
 107                                 for (x = 0; x < N2; x++)
 108                                         for (y = 0; y < N2; y++) {
 109                                                 c = puzzle.charAt(x * N2 + y);
 110                                                 j = 0;
 111
 112                                                 if (c == '-' || c == '.' || c == '0' || c == '*') {
 113                                                         A0[x][y] = j;
 114                                                         i++;
 115                                                 } else {
 116                                                         while (L[j] != c && j <= N2)
 117                                                                 j++;
 118
 119                                                         if (j <= N2) {
 120                                                                 A0[x][y] = j;
 121                                                                 if (j > 0)
 122                                                                         clues++;
 123                                                                 i++;
 124                                                         }
 125                                                 }
 126                                         }
 127
 128                                 if (clues == N4) {
 129                                         clues--;
 130                                         A0[1][1] = 0;
 131                                 }
 132
 133                                 if (p < 8) {
 134                                         for (i = 0; i <= N4; i++)
 135                                                 Node[i] = 0;
 136                                 }
 137                                 tnodes = 0;
 138
 139                         case RESTART:
 140                                 r = 0;
 141                                 for (x = 1; x <= N2; x++)
 142                                         for (y = 1; y <= N2; y++)
 143                                                 for (s = 1; s <= N2; s++) {
 144                                                         r++;
 145                                                         Cols[r] = 4;
 146                                                         Col[r][1] = x * N2 - N2 + y;
 147                                                         Col[r][4] = (N * ((x - 1) / N) + (y - 1) / N) * N2 + s + N4;
 148
 149                                                         Col[r][3] = x * N2 - N2 + s + N4 * 2;
 150                                                         Col[r][2] = y * N2 - N2 + s + N4 * 3;
 151                                                 }
 152                                 for (c = 1; c <= m; c++)
 153                                         Rows[c] = 0;
 154
 155                                 for (r = 1; r <= n; r++)
 156                                         for (c = 1; c <= Cols[r]; c++) {
 157                                                 x = Col[r][c];
 158                                                 Rows[x]++;
 159                                                 Row[x][Rows[x]] = r;
 160                                         }
 161
 162                                 for (x = 0; x < N2; x++)
 163                                         for (y = 0; y < N2; y++)
 164                                                 A[x][y] = A0[x][y];
 165
 166                                 for (i = 0; i <= n; i++)
 167                                         Ur[i] = 0;
 168                                 for (i = 0; i <= m; i++)
 169                                         Uc[i] = 0;
 170
 171                                 solutions = 0;
 172
 173                                 for (x = 1; x <= N2; x++)
 174                                         for (y = 1; y <= N2; y++)
 175                                                 if (A[x - 1][y - 1] > 0) {
 176                                                         r = x * N4 - N4 + y * N2 - N2 + A[x - 1][y - 1];
 177
 178                                                         for (j = 1; j <= Cols[r]; j++) {
 179                                                                 c1 = Col[r][j];
 180                                                                 if (Uc[c1] > 0 && nocheck == 0) {
 181                                                                         STATE = NEXT_TRY;
 182                                                                         break;
 183                                                                 }
 184
 185                                                                 Uc[c1]++;
 186
 187                                                                 for (k = 1; k <= Rows[c1]; k++) {
 188                                                                         r1 = Row[c1][k];
 189                                                                         Ur[r1]++;
 190                                                                 }
 191                                                         }
 192                                                         if (STATE == NEXT_TRY)
 193                                                                 break;
 194                                                 }
 195                                 if (STATE == NEXT_TRY)
 196                                         break;
 197
 198                                 if (rnd > 0 && rnd != 17 && rnd != 18)
 199                                         shuffle();
 200
 201                                 for (c = 1; c <= m; c++) {
 202                                         V[c] = 0;
 203                                         for (r = 1; r <= Rows[c]; r++)
 204                                                 if (Ur[Row[c][r]] == 0)
 205                                                         V[c]++;
 206                                 }
 207
 208                                 i = clues;
 209                                 nodes = 0;
 210                                 m0 = 0;
 211                                 m1 = 0;
 212                                 gu = 0;
 213                                 solutions = 0;
 214
 215                         case M22:
 216                                 i++;
 217                                 I[i] = 0;
 218                                 min = n + 1;
 219                                 if (i > N4 || m0 > 0) {
 220                                         STATE = M44;
 221                                         break;
 222                                 }
 223                                 if (m1 > 0) {
 224                                         C[i] = m1;
 225                                         STATE = M3;
 226                                         break;
 227                                 }
 228                                 for (c = 1; c <= m; c++)
 229                                         if (Uc[c] == 0) {
 230                                                 if (V[c] <= min)
 231                                                         c1 = c;
 232                                                 if (V[c] < min) {
 233                                                         min = V[c];
 234                                                         C[i] = c;
 235                                                         if (min < 2) {
 236                                                                 STATE = M3;
 237                                                                 break;
 238                                                         }
 239                                                 }
 240                                         }
 241                                 if (STATE == M3)
 242                                         break;
 243
 244                                 gu++;
 245                                 if (min > 2) {
 246                                         STATE = M3;
 247                                         break;
 248                                 }
 249
 250                                 if ((rnd & 255) == 18)
 251                                         if ((nodes & 1) > 0) {
 252                                                 c = m + 1;
 253                                                 c--;
 254                                                 while (Uc[c] > 0 || V[c] != 2)
 255                                                         c--;
 256                                                 C[i] = c;
 257                                         }
 258
 259                                 if ((rnd & 255) == 17) {
 260                                         c1 = (int) (MWC() & Mc[N]);
 261                                         while (c1 >= m)
 262                                                 c1 = (int) (MWC() & Mc[N]);
 263                                         c1++;
 264
 265                                         for (c = c1; c <= m; c++)
 266                                                 if (Uc[c] == 0)
 267                                                         if (V[c] == 2) {
 268                                                                 C[i] = c;
 269                                                                 STATE = M3;
 270                                                                 break;
 271                                                         }
 272                                         for (c = 1; c < c1; c++)
 273                                                 if (Uc[c] == 0)
 274                                                         if (V[c] == 2) {
 275                                                                 C[i] = c;
 276                                                                 STATE = M3;
 277                                                                 break;
 278                                                         }
 279                                 }
 280
 281                         case M3:
 282                                 c = C[i];
 283                                 I[i]++;
 284                                 if (I[i] > Rows[c]) {
 285                                         STATE = M44;
 286                                         break;
 287                                 }
 288
 289                                 r = Row[c][I[i]];
 290                                 if (Ur[r] > 0) {
 291                                         STATE = M3;
 292                                         break;
 293                                 }
 294                                 m0 = 0;
 295                                 m1 = 0;
 296
 297                                 if (q > 0 && i > 32 && i < 65)
 298                                         if ((MWC() & 127) < q) {
 299                                                 STATE = M3;
 300                                                 break;
 301                                         }
 302
 303                                 k = N4;
 304                                 x = (r - 1) / k + 1;
 305                                 y = ((r - 1) % k) / j + 1;
 306                                 s = (r - 1) % j + 1;
 307
 308                                 if ((p & 1) > 0) {
 309                                         j = N2;
 310                                         k = N4;
 311                                         x = (r - 1) / k + 1;
 312                                         y = ((r - 1) % k) / j + 1;
 313                                         s = (r - 1) % j + 1;
 314                                         A[x - 1][y - 1] = s;
 315                                         if (i == k) {
 316                                                 for (x = 0; x < j; x++)
 317                                                         for (y = 0; y < j; y++)
 318                                                                 result = result.concat(String.valueOf(L[A[x][y]]));
 319                                                 result = result.concat(" #\n");
 320                                         }
 321                                 }
 322
 323                                 for (j = 1; j <= Cols[r]; j++) {
 324                                         c1 = Col[r][j];
 325                                         Uc[c1]++;
 326                                 }
 327
 328                                 for (j = 1; j <= Cols[r]; j++) {
 329                                         c1 = Col[r][j];
 330
 331                                         for (k = 1; k <= Rows[c1]; k++) {
 332                                                 r1 = Row[c1][k];
 333                                                 Ur[r1]++;
 334                                                 if (Ur[r1] == 1)
 335                                                         for (l = 1; l <= Cols[r1]; l++) {
 336                                                                 c2 = Col[r1][l];
 337                                                                 V[c2]--;
 338
 339                                                                 if (Uc[c2] + V[c2] < 1)
 340                                                                         m0 = c2;
 341                                                                 if (Uc[c2] == 0 && V[c2] < 2)
 342                                                                         m1 = c2;
 343                                                         }
 344                                         }
 345                                 }
 346                                 Node[i]++;
 347                                 tnodes++;
 348                                 nodes++;
 349                                 if (rnd > 99 && nodes > rnd) {
 350                                         STATE = RESTART;
 351                                         break;
 352                                 }
 353                                 if (i == N4)
 354                                         solutions++;
 355
 356                                 if (solutions >= smax) {
 357                                         System.out.println("smax xolutions found");
 358                                         if (_try_ == 1)
 359                                                 System.out.print("+");
 360                                         STATE = NEXT_TRY;
 361                                         break;
 362                                 }
 363                                 if (tnodes > vmax) {
 364                                         if (_try_ == 1)
 365                                                 System.out.print("-");
 366                                         STATE = NEXT_TRY;
 367                                         break;
 368                                 }
 369                                 STATE = M22;
 370                                 break;
 371
 372                         case M44:
 373                                 i--;
 374                                 c = C[i];
 375                                 r = Row[c][I[i]];
 376                                 if (i == clues) {
 377                                         STATE = NEXT_TRY;
 378                                         break;
 379                                 }
 380
 381                                 for (j = 1; j <= Cols[r]; j++) {
 382                                         c1 = Col[r][j];
 383                                         Uc[c1]--;
 384
 385                                         for (k = 1; k <= Rows[c1]; k++) {
 386                                                 r1 = Row[c1][k];
 387                                                 Ur[r1]--;
 388
 389                                                 if (Ur[r1] == 0)
 390                                                         for (l = 1; l <= Cols[r1]; l++) {
 391                                                                 c2 = Col[r1][l];
 392                                                                 V[c2]++;
 393                                                         }
 394                                         }
 395                                 }
 396                                 if (p > 0) {
 397                                         j = N2;
 398                                         k = N4;
 399                                         x = (r - 1) / k + 1;
 400                                         y = ((r - 1) % k) / j + 1;
 401                                         s = (r - 1) % j + 1;
 402                                         A[x - 1][y - 1] = 0;
 403                                 }
 404                                 if (i > clues) {
 405                                         STATE = M3;
 406                                         break;
 407                                 }
 408
 409                         case NEXT_TRY:
 410                                 time1 = System.currentTimeMillis();
 411                                 x1 = time1 - time0;
 412
 413                                 time0 = time1;
 414
 415                                 if (q > 0) {
 416                                         xx = 128;
 417                                         yy = 128 - q;
 418                                         xx = xx / yy;
 419                                         yy = solutions;
 420                                         for (i = 1; i < 33; i++)
 421                                                 yy = yy * xx;
 422                                         System.out.println("clues: " + clues + " estimated solutions:" + yy + " time " + x1 + "ms");
 423
 424                                         STATE = END;
 425                                         break;
 426                                 }
 427                                 if ((p == 0 || p == 1) && tnodes <= 999999) {
 428                                         if (solutions >= smax)
 429                                                 result = result.concat("More than " + solutions + " solutions ( bad sudoku!! ), rating "
 430                                                                 + (100 * tnodes / solutions) + ", time " + x1 + " ms");
 431                                         else if (solutions == 1)
 432                                                 result = result.concat(solutions + " solution, rating " + (100 * tnodes) + ", time " + x1
 433                                                                 + " ms");
 434                                         else if (solutions == 0)
 435                                                 result = result.concat("0 solutions, no rating possible, time " + x1 + " ms");
 436                                         else
 437                                                 result = result.concat(solutions + " solutions ( bad sudoku!! ), rating "
 438                                                                 + (100 * tnodes / solutions) + ", time " + x1 + " ms");
 439
 440                                         STATE = END;
 441                                         break;
 442                                 }
 443                                 if (p == 6) {
 444                                         System.out.println(solutions);
 445                                         STATE = END;
 446                                         break;
 447                                 }
 448                                 if (p == 0 || p == 1) {
 449                                         System.out.println(solutions + " solution(s), rating " + (100 * tnodes) + ", time " + x1 + "ms");
 450                                 }
 451                                 if (p > 5) {
 452                                         x = 0;
 453                                         for (i = 1; i <= N4; i++) {
 454                                                 x += Node[i];
 455                                                 System.out.print(Node[i]);
 456                                                 if (i % 9 == 0)
 457                                                         System.out.println();
 458                                         }
 459                                         System.out.println(x);
 460                                 }
 461                                 STATE = END;
 462                                 break;
 463                         } // end of switch statement
 464                 } // end of while loop
 465                 return result;
 466         }
 467
 468         /**
 469          * Helper function.
 470          */
 471         int shuffle() {
 472                 for (i = 1; i <= m; i++) {
 473                         a = (int) ((MWC() >> 8) & Mc[N]);
 474                         while (a >= i)
 475                                 a = (int) ((MWC() >> 8) & Mc[N]);
 476                         a++;
 477                         P[i] = P[a];
 478                         P[a] = i;
 479                 }
 480
 481                 for (c = 1; c <= m; c++) {
 482                         Rows[c] = 0;
 483                         T[c] = Uc[c];
 484                 }
 485
 486                 for (c = 1; c <= m; c++)
 487                         Uc[P[c]] = T[c];
 488
 489                 for (r = 1; r <= n; r++)
 490                         for (i = 1; i <= Cols[r]; i++) {
 491                                 c = P[Col[r][i]];
 492                                 Col[r][i] = c;
 493                                 Rows[c]++;
 494                                 Row[c][Rows[c]] = r;
 495                         }
 496
 497                 for (i = 1; i <= n; i++) {
 498                         a = (int) ((MWC() >> 8) & Mr[N]);
 499                         while (a >= i)
 500                                 a = (int) ((MWC() >> 8) & Mr[N]);
 501                         a++;
 502                         P[i] = P[a];
 503                         P[a] = i;
 504                 }
 505
 506                 for (r = 1; r <= n; r++) {
 507                         Cols[r] = 0;
 508                         T[r] = Ur[r];
 509                 }
 510
 511                 for (r = 1; r <= n; r++)
 512                         Ur[P[r]] = T[r];
 513
 514                 for (c = 1; c <= m; c++)
 515                         for (i = 1; i <= Rows[c]; i++) {
 516                                 r = P[Row[c][i]];
 517                                 Row[c][i] = r;
 518                                 Cols[r]++;
 519                                 Col[r][Cols[r]] = c;
 520                         }
 521
 522                 for (r = 1; r <= n; r++) {
 523                         for (i = 1; i <= Cols[r]; i++) {
 524                                 a = (int) ((MWC() >> 8) & 7);
 525                                 while (a >= i)
 526                                         a = (int) ((MWC() >> 8) & 7);
 527                                 a++;
 528                                 P[i] = P[a];
 529                                 P[a] = i;
 530                         }
 531
 532                         for (i = 1; i <= Cols[r]; i++)
 533                                 T[i] = Col[r][P[i]];
 534
 535                         for (i = 1; i <= Cols[r]; i++)
 536                                 Col[r][i] = T[i];
 537                 }
 538
 539                 for (c = 1; c <= m; c++) {
 540                         for (i = 1; i <= Rows[c]; i++) {
 541                                 a = (int) ((MWC() >> 8) & Mw[N]);
 542                                 while (a >= i)
 543                                         a = (int) ((MWC() >> 8) & Mw[N]);
 544                                 a++;
 545                                 P[i] = P[a];
 546                                 P[a] = i;
 547                         }
 548
 549                         for (i = 1; i <= Rows[c]; i++)
 550                                 T[i] = Row[c][P[i]];
 551
 552                         for (i = 1; i <= Rows[c]; i++)
 553                                 Row[c][i] = T[i];
 554                 }
 555                 return 0;
 556         }
 557
 558         private final Random random;
 559
 560         /** Creates a new instance of dlx_solver */
 561         public dlx_solver(Random random) {
 562                 this.random = random;
 563         }
 564 }
 565
 566 /*******************************************************************************
 567  * dlx_generator generate single solution locally minimized Sudoku puzzles.
 568  * Locally minimized means that all keys that can be removed without creating a
 569  * degenerate Sudoku (multiple solutions) are removed.
 570  ******************************************************************************/
 571 class dlx_generator {
 572         long MWC() {
 573                 return random.nextLong();
 574         }
 575
 576         int Rows[] = new int[325], Cols[] = new int[730], Row[][] = new int[325][10], Col[][] = new int[730][5],
 577                         Ur[] = new int[730], Uc[] = new int[325], V[] = new int[325], W[] = new int[325];
 578         int P[] = new int[88], A[] = new int[88], C[] = new int[88], I[] = new int[88], Two[] = new int[888];
 579         char B[] = { '0', '1', '1', '1', '2', '2', '2', '3', '3', '3', '1', '1', '1', '2', '2', '2', '3', '3', '3', '1',
 580                         '1', '1', '2', '2', '2', '3', '3', '3', '4', '4', '4', '5', '5', '5', '6', '6', '6', '4', '4', '4', '5',
 581                         '5', '5', '6', '6', '6', '4', '4', '4', '5', '5', '5', '6', '6', '6', '7', '7', '7', '8', '8', '8', '9',
 582                         '9', '9', '7', '7', '7', '8', '8', '8', '9', '9', '9', '7', '7', '7', '8', '8', '8', '9', '9', '9' };
 583         char H[][] = new char[326][7];
 584         long c2, w;
 585         int b, f, s1, m0, c1, r1, l, i1, m1, m2, a, p, i, j, k, r, c, d, n = 729, m = 324, x, y, s, z, fi;
 586         int mi1, mi2, q7, part, nt, rate, nodes, solutions, min, samples, sam1, clues;
 587         char L[] = { '.', '1', '2', '3', '4', '5', '6', '7', '8', '9' };
 588
 589         /** State machine states */
 590         static final int M0S = 10;
 591         static final int M0 = 11;
 592         static final int MR1 = 12;
 593         static final int MR3 = 13;
 594         static final int MR4 = 14;
 595         static final int M2 = 15;
 596         static final int M3 = 16;
 597         static final int M4 = 17;
 598         static final int M9 = 18;
 599         static final int MR = 19;
 600         static final int END = 20;
 601         static final int M6 = 21;
 602
 603         /** Set to true to generate debug output */
 604         boolean DBG = true;
 605
 606         /** Output trace messages */
 607         void dbg(String s) {
 608                 if (DBG)
 609                         System.out.println(s);
 610         }
 611
 612         private final Random random;
 613
 614         public dlx_generator(Random random) {
 615                 dbg("In constructor");
 616                 this.random = random;
 617         }
 618
 619         /**
 620          * Save the generated Sudoku to a file.
 621          */
 622         void saveSudokuToFile(String s) {
 623                 FileOutputStream FO = null;
 624                 byte[] buffer = new byte[s.length() + 1];
 625                 int i = 0;
 626
 627                 while (i < s.length()) {
 628                         buffer[i] = (byte) s.charAt(i);
 629                         i++;
 630                 }
 631
 632                 try {
 633                         FO = new FileOutputStream("generated_sudoku.sdk");
 634                         FO.write(buffer);
 635                         FO.close();
 636                 } catch (IOException IOE) {
 637                         // Well, well, well....
 638                         return;
 639                 }
 640         }
 641
 642         /**
 643          * Initialization code for both generate() and rate()
 644          */
 645         void initialize() {
 646                 for (i = 0; i < 888; i++) {
 647                         j = 1;
 648                         while (j <= i)
 649                                 j += j;
 650                         Two[i] = j - 1;
 651                 }
 652
 653                 r = 0;
 654                 for (x = 1; x <= 9; x++)
 655                         for (y = 1; y <= 9; y++)
 656                                 for (s = 1; s <= 9; s++) {
 657                                         r++;
 658                                         Cols[r] = 4;
 659                                         Col[r][1] = x * 9 - 9 + y;
 660                                         Col[r][2] = (B[x * 9 - 9 + y] - 48) * 9 - 9 + s + 81;
 661                                         Col[r][3] = x * 9 - 9 + s + 81 * 2;
 662                                         Col[r][4] = y * 9 - 9 + s + 81 * 3;
 663                                 }
 664
 665                 for (c = 1; c <= m; c++)
 666                         Rows[c] = 0;
 667
 668                 for (r = 1; r <= n; r++)
 669                         for (c = 1; c <= Cols[r]; c++) {
 670                                 a = Col[r][c];
 671                                 Rows[a]++;
 672                                 Row[a][Rows[a]] = r;
 673                         }
 674
 675                 c = 0;
 676                 for (x = 1; x <= 9; x++)
 677                         for (y = 1; y <= 9; y++) {
 678                                 c++;
 679                                 H[c][0] = 'r';
 680                                 H[c][1] = L[x];
 681                                 H[c][2] = 'c';
 682                                 H[c][3] = L[y];
 683                                 H[c][4] = 0;
 684                         }
 685
 686                 c = 81;
 687                 for (b = 1; b <= 9; b++)
 688                         for (s = 1; s <= 9; s++) {
 689                                 c++;
 690                                 H[c][0] = 'b';
 691                                 H[c][1] = L[b];
 692                                 H[c][2] = 's';
 693                                 H[c][3] = L[s];
 694                                 H[c][4] = 0;
 695                         }
 696
 697                 c = 81 * 2;
 698                 for (x = 1; x <= 9; x++)
 699                         for (s = 1; s <= 9; s++) {
 700                                 c++;
 701                                 H[c][0] = 'r';
 702                                 H[c][1] = L[x];
 703                                 H[c][2] = 's';
 704                                 H[c][3] = L[s];
 705                                 H[c][4] = 0;
 706                         }
 707
 708                 c = 81 * 3;
 709                 for (y = 1; y <= 9; y++)
 710                         for (s = 1; s <= 9; s++) {
 711                                 c++;
 712                                 H[c][0] = 'c';
 713                                 H[c][1] = L[y];
 714                                 H[c][2] = 's';
 715                                 H[c][3] = L[s];
 716                                 H[c][4] = 0;
 717                         }
 718         }
 719
 720         /*
 721          * Rating function
 722          */
 723         public long rate(String puzzle) {
 724                 int STATE = M6;
 725                 int Solutions;
 726
 727                 z = 100;
 728                 fi = 0;
 729                 rate = 1;
 730
 731                 for (i = 0; i < 88; i++)
 732                         A[i] = 0;
 733
 734                 initialize();
 735
 736                 while (STATE != END) {
 737                         switch (STATE) {
 738                         case M6:
 739                                 clues = 0;
 740                                 for (i = 1; i <= 81; i++) {
 741                                         c = puzzle.charAt(i - 1);
 742                                         j = 0;
 743
 744                                         if (c == '-' || c == '.' || c == '0' || c == '*') {
 745                                                 A[i] = j;
 746                                         } else {
 747                                                 while (L[j] != c && j <= 9)
 748                                                         j++;
 749
 750                                                 if (j <= 9) {
 751                                                         A[i] = j;
 752                                                 }
 753                                         }
 754                                 }
 755
 756                                 if (clues == 81) {
 757                                         clues--;
 758                                         A[1] = 0;
 759                                 }
 760
 761                                 nt = 0;
 762                                 mi1 = 9999;
 763                                 for (f = 0; f < z; f++) {
 764                                         Solutions = solve();
 765                                         if (Solutions != 1) {
 766                                                 if (Solutions > 1)
 767                                                         nt = -1 * Solutions;
 768                                                 STATE = END;
 769                                                 break;
 770                                         }
 771                                         nt += nodes;
 772                                         if (nodes < mi1) {
 773                                                 mi1 = nodes;
 774                                                 mi2 = C[clues];
 775                                         }
 776                                 }
 777                                 if (STATE == END)
 778                                         break;
 779
 780                                 if (fi > 0)
 781                                         if ((nt / z) > fi) {
 782                                                 for (i = 1; i <= 81; i++)
 783                                                         System.out.println(L[A[i]]);
 784                                                 System.out.println();
 785                                                 STATE = M6;
 786                                                 break;
 787                                         }
 788
 789                                 if (fi > 0) {
 790                                         STATE = M6;
 791                                         break;
 792                                 }
 793
 794                                 if ((z & 1) > 0) {
 795                                         System.out.println(nt / z);
 796                                         STATE = M6;
 797                                         break;
 798                                 }
 799
 800                                 if (rate > 1)
 801                                         System.out.println("hint: " + H[mi2]);
 802
 803                                 STATE = END;
 804                                 break;
 805                         } // End of switch statement
 806                 } // End of while loop
 807                 return (nt);
 808         }
 809
 810         public String[] generate(int Samples, int Rate) {
 811                 int STATE = M0S;
 812                 String result[] = new String[Samples];
 813
 814                 dbg("Entering generate");
 815
 816                 samples = 1000;
 817                 if (Samples > 0)
 818                         samples = Samples;
 819
 820                 for (i = 0; i < samples; i++)
 821                         result[i] = new String();
 822
 823                 // Set to 1 for rating, set to 2 for rating and hint
 824                 rate = 0;
 825                 if (Rate > 0)
 826                         rate = Rate;
 827                 if (rate > 2)
 828                         rate = 2;
 829
 830                 initialize();
 831
 832                 dbg("Entering state machine");
 833
 834                 sam1 = -1;
 835                 while (STATE != END) {
 836                         switch (STATE) {
 837                         case M0S:
 838                                 sam1++;
 839                                 if (sam1 >= samples) {
 840                                         STATE = END;
 841                                         break;
 842                                 }
 843
 844                         case M0:
 845                                 for (i = 1; i <= 81; i++)
 846                                         A[i] = 0;
 847                                 part = 0;
 848                                 q7 = 0;
 849
 850                         case MR1:
 851                                 i1 = (int) ((MWC() >> 8) & 127);
 852                                 if (i1 > 80) {
 853                                         STATE = MR1;
 854                                         break;
 855                                 }
 856
 857                                 i1++;
 858                                 if (A[i1] > 0) {
 859                                         STATE = MR1;
 860                                         break;
 861                                 }
 862
 863                         case MR3:
 864                                 s = (int) ((MWC() >> 9) & 15);
 865                                 if (s > 8) {
 866                                         STATE = MR3;
 867                                         break;
 868                                 }
 869
 870                                 s++;
 871                                 A[i1] = s;
 872                                 m2 = solve();
 873                                 q7++;
 874
 875                                 if (m2 < 1)
 876                                         A[i1] = 0;
 877
 878                                 if (m2 != 1) {
 879                                         STATE = MR1;
 880                                         break;
 881                                 }
 882
 883                                 part++;
 884                                 if (solve() != 1) {
 885                                         STATE = M0;
 886                                         break;
 887                                 }
 888
 889                         case MR4:
 890                                 for (i = 1; i <= 81; i++) {
 891                                         x = (int) ((MWC() >> 8) & 127);
 892                                         while (x >= i) {
 893                                                 x = (int) ((MWC() >> 8) & 127);
 894                                         }
 895                                         x++;
 896                                         P[i] = P[x];
 897                                         P[x] = i;
 898                                 }
 899
 900                                 for (i1 = 1; i1 <= 81; i1++) {
 901                                         s1 = A[P[i1]];
 902                                         A[P[i1]] = 0;
 903                                         if (solve() > 1)
 904                                                 A[P[i1]] = s1;
 905                                 }
 906
 907                                 if (rate > 0) {
 908                                         nt = 0;
 909                                         mi1 = 9999;
 910                                         for (f = 0; f < 100; f++) {
 911                                                 solve();
 912                                                 nt += nodes;
 913                                                 if (nodes < mi1) {
 914                                                         mi1 = nodes;
 915                                                         mi2 = C[clues];
 916                                                 }
 917                                         }
 918                                         result[sam1] = result[sam1].concat("Rating:" + nt + "# ");
 919                                         if (rate > 1) {
 920                                                 result[sam1] = result[sam1].concat("hint: " + String.valueOf(H[mi2]).substring(0, 4) + " #\n");
 921                                         } else
 922                                                 result[sam1] = result[sam1].concat("\n");
 923                                 }
 924
 925                                 for (i = 1; i <= 81; i++) {
 926                                         result[sam1] = result[sam1].concat(String.valueOf(L[A[i]]));
 927                                         if (i % 9 == 0) {
 928                                                 result[sam1] = result[sam1].concat("\n");
 929                                         }
 930                                 }
 931                                 result[sam1] = result[sam1].concat("\n");
 932
 933                         default:
 934                                 dbg("Default case. New state M0S");
 935                                 STATE = M0S;
 936                                 break;
 937                         } // end of switch statement
 938                 } // end of while loop
 939                 return result;
 940         }
 941
 942         int solve() {
 943                 // returns 0 (no solution), 1 (unique sol.), 2 (more than
 944                                         // one sol.)
 945                 int STATE = M2;
 946
 947                 for (i = 0; i <= n; i++)
 948                         Ur[i] = 0;
 949                 for (i = 0; i <= m; i++)
 950                         Uc[i] = 0;
 951                 clues = 0;
 952
 953                 for (i = 1; i <= 81; i++)
 954                         if (A[i] > 0) {
 955                                 clues++;
 956                                 r = i * 9 - 9 + A[i];
 957
 958                                 for (j = 1; j <= Cols[r]; j++) {
 959                                         d = Col[r][j];
 960                                         if (Uc[d] > 0)
 961                                                 return 0;
 962                                         Uc[d]++;
 963
 964                                         for (k = 1; k <= Rows[d]; k++) {
 965                                                 Ur[Row[d][k]]++;
 966                                         }
 967                                 }
 968                         }
 969
 970                 for (c = 1; c <= m; c++) {
 971                         V[c] = 0;
 972                         for (r = 1; r <= Rows[c]; r++)
 973                                 if (Ur[Row[c][r]] == 0)
 974                                         V[c]++;
 975                 }
 976
 977                 i = clues;
 978                 m0 = 0;
 979                 m1 = 0;
 980                 solutions = 0;
 981                 nodes = 0;
 982
 983                 dbg("Solve: Entering state machine");
 984
 985                 while (STATE != END) {
 986                         switch (STATE) {
 987                         case M2:
 988                                 i++;
 989                                 I[i] = 0;
 990                                 min = n + 1;
 991                                 if ((i > 81) || (m0 > 0)) {
 992                                         STATE = M4;
 993                                         break;
 994                                 }
 995
 996                                 if (m1 > 0) {
 997                                         C[i] = m1;
 998                                         STATE = M3;
 999                                         break;
1000                                 }
1001
1002                                 w = 0;
1003                                 for (c = 1; c <= m; c++)
1004                                         if (Uc[c] == 0) {
1005                                                 if (V[c] < 2) {
1006                                                         C[i] = c;
1007                                                         STATE = M3;
1008                                                         break;
1009                                                 }
1010
1011                                                 if (V[c] <= min) {
1012                                                         w++;
1013                                                         W[(int) w] = c;
1014                                                 }
1015                                                 ;
1016
1017                                                 if (V[c] < min) {
1018                                                         w = 1;
1019                                                         W[(int) w] = c;
1020                                                         min = V[c];
1021                                                 }
1022                                         }
1023
1024                                 if (STATE == M3) {
1025                                         // break in for loop detected, continue breaking
1026                                         break;
1027                                 }
1028
1029                         case MR:
1030                                 c2 = (MWC() & Two[(int) w]);
1031                                 while (c2 >= w) {
1032                                         c2 = (MWC() & Two[(int) w]);
1033                                 }
1034                                 C[i] = W[(int) c2 + 1];
1035
1036                         case M3:
1037                                 c = C[i];
1038                                 I[i]++;
1039                                 if (I[i] > Rows[c]) {
1040                                         STATE = M4;
1041                                         break;
1042                                 }
1043
1044                                 r = Row[c][I[i]];
1045                                 if (Ur[r] > 0) {
1046                                         STATE = M3;
1047                                         break;
1048                                 }
1049                                 m0 = 0;
1050                                 m1 = 0;
1051                                 nodes++;
1052                                 for (j = 1; j <= Cols[r]; j++) {
1053                                         c1 = Col[r][j];
1054                                         Uc[c1]++;
1055                                 }
1056
1057                                 for (j = 1; j <= Cols[r]; j++) {
1058                                         c1 = Col[r][j];
1059                                         for (k = 1; k <= Rows[c1]; k++) {
1060                                                 r1 = Row[c1][k];
1061                                                 Ur[r1]++;
1062                                                 if (Ur[r1] == 1)
1063                                                         for (l = 1; l <= Cols[r1]; l++) {
1064                                                                 c2 = Col[r1][l];
1065                                                                 V[(int) c2]--;
1066                                                                 if (Uc[(int) c2] + V[(int) c2] < 1)
1067                                                                         m0 = (int) c2;
1068                                                                 if (Uc[(int) c2] == 0 && V[(int) c2] < 2)
1069                                                                         m1 = (int) c2;
1070                                                         }
1071                                         }
1072                                 }
1073
1074                                 if (i == 81)
1075                                         solutions++;
1076
1077                                 if (solutions > 1) {
1078                                         STATE = M9;
1079                                         break;
1080                                 }
1081                                 STATE = M2;
1082                                 break;
1083
1084                         case M4:
1085                                 i--;
1086                                 if (i == clues) {
1087                                         STATE = M9;
1088                                         break;
1089                                 }
1090                                 c = C[i];
1091                                 r = Row[c][I[i]];
1092
1093                                 for (j = 1; j <= Cols[r]; j++) {
1094                                         c1 = Col[r][j];
1095                                         Uc[c1]--;
1096                                         for (k = 1; k <= Rows[c1]; k++) {
1097                                                 r1 = Row[c1][k];
1098                                                 Ur[r1]--;
1099                                                 if (Ur[r1] == 0)
1100                                                         for (l = 1; l <= Cols[r1]; l++) {
1101                                                                 c2 = Col[r1][l];
1102                                                                 V[(int) c2]++;
1103                                                         }
1104                                         }
1105                                 }
1106
1107                                 if (i > clues) {
1108                                         STATE = M3;
1109                                         break;
1110                                 }
1111
1112                         case M9:
1113                                 STATE = END;
1114                                 break;
1115                         default:
1116                                 STATE = END;
1117                                 break;
1118                         } // end of switch statement
1119                 } // end of while statement
1120                 return solutions;
1121         }
1122 }
1123
1124 /**
1125  *
1126  * @author Rolf Sandberg
1127  */
1128
1129 class xxxDLXEngine {
1130         dlx_generator generator;
1131         dlx_solver solver;
1132
1133         public xxxDLXEngine(Random random) {
1134                 generator = new dlx_generator(random);
1135                 solver = new dlx_solver(random);
1136         }
1137
1138         String generate(int minrating, int maxrating) {
1139                 // Date t = new Date();
1140                 // long start = t.getTime();
1141                 // int tries = 0, i, samples = 5;
1142                 // long rating = 0;
1143                 String ss[] = generator.generate(1, 0);
1144                 return ss[0];
1145
1146                 // Generator:
1147                 // First arg: rand seed
1148                 // Second arg: #samples, ignored if <= 0
1149                 // Third arg: rating and hints, ignored if <= 0
1150
1151                 // Task: Find a Sudoku with a rating in a specified interval.
1152                 // Do it by generating samples and examine them
1153                 // Continue until an appropriate puzzle is found.
1154                 // while(tries < 9999999) {
1155                 // tries++;
1156                 // t = new Date();
1157                 // ss = generator.generate(samples, 0);
1158                 // for(i = 0; i < samples; i++) {
1159                 // rating = generator.rate(ss[i].replace("\n","").trim());
1160                 // if(rating > minrating && rating < maxrating) {
1161                 // return ss[i];
1162                 // }
1163                 // }
1164                 // System.out.println(minrating + ", " + maxrating + ", " + rating + ",
1165                 // looping");
1166                 // }
1167                 // return ss[0];
1168         }
1169
1170         long rate(String s) {
1171                 return generator.rate(s);
1172         }
1173
1174         String solve(String s) {
1175                 String result = solver.solve(s);
1176                 return result;
1177         }
1178 }
1179
1180 public class DLXEngine {
1181         dlx_generator generator;
1182         dlx_solver solver;
1183
1184         public DLXEngine(Random random) {
1185                 generator = new dlx_generator(random);
1186                 solver = new dlx_solver(random);
1187         }
1188
1189         public String generate(int minrating, int maxrating){
1190                 int tries = 0, i, samples = 5;
1191                 long rating = 0;
1192                 String ss[] = new String[samples];
1193
1194                 for(tries = 0; tries < samples; tries++)
1195                         ss[tries] = new String();
1196                 tries = 1;
1197
1198                 // Generator:
1199                         // First arg: rand seed
1200                         // Second arg: #samples, ignored if <= 0
1201                 // Third arg: rating and hints, ignored if <= 0
1202
1203                 // Task: Find a Sudoku with a rating in a specified interval.
1204                 // Do it by generating samples and examine them
1205                 // Continue until an appropriate puzzle is found.
1206                 while(tries < 9999999) {
1207                         tries++;
1208                         ss = generator.generate(samples, 0);
1209                         for(i = 0; i < samples; i++) {
1210                                 rating = generator.rate(ss[i].replace("\n","").trim());
1211                                 if(rating > minrating && rating < maxrating) {
1212                                         System.out.println(minrating + ", " + maxrating + ", " + rating);
1213                                         return ss[i];
1214                                 }
1215                         }
1216                 }
1217                 return ss[0];
1218         }
1219
1220         public long rate(String s) {
1221                 return generator.rate(s);
1222         }
1223
1224         public String solve(String s){
1225                 String result = solver.solve(s);
1226                 return result;
1227         }
1228 }