puzzle.c

   1 /* Copyright (c) 2006 Scott Gasch
   2  *
   3  * Licensed under the Apache License, Version 2.0 (the "License");
   4  * you may not use this file except in compliance with the License.
   5  * You may obtain a copy of the License at
   6  *
   7  *     http://www.apache.org/licenses/LICENSE-2.0
   8  *
   9  * Unless required by applicable law or agreed to in writing, software
  10  * distributed under the License is distributed on an "AS IS" BASIS,
  11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12  * See the License for the specific language governing permissions and
  13  * limitations under the License.
  14  */
  15
  16 #include <stdlib.h>
  17 #include <stdio.h>
  18 #include <string.h>
  19 #include <ctype.h>
  20 #include <time.h>
  21
  22 #include "puzzle.h"
  23
  24 ULONG g_uNodes = 0;
  25 ULONG g_uGuesses = 0;
  26 ULONG g_uSolutions = 0;
  27 POSITION g_Solution;
  28
  29 BOOL
  30 PositionIsLegal(POSITION *, BOOL);
  31
  32
  33 char *
  34 ShowPossibilities(BITV bv)
  35 /*++
  36
  37 Routine description:
  38
  39     Return a text representation of the possible moves at a square.
  40
  41 Parameters:
  42
  43     BITV bv
  44
  45 Return value:
  46
  47     char
  48
  49 --*/
  50 {
  51     static char bits[] = "*123456789";
  52     static char sz[10];
  53     ULONG u;
  54     ULONG v;
  55
  56     memset(&sz, 0, sizeof(sz));
  57     v = 0;
  58     for (u = 1; u < 10; u++)
  59     {
  60         if (bv & (1 << (u - 1)))
  61         {
  62             sz[v++] = bits[u];
  63         }
  64     }
  65     return(sz);
  66 }
  67
  68
  69
  70
  71 void
  72 DumpBoard(POSITION *pos)
  73 /*++
  74
  75 Routine description:
  76
  77     Draw a text representation of the playing board.
  78
  79 Parameters:
  80
  81     POSITION *pos : position
  82
  83 Return value:
  84
  85     void
  86
  87 --*/
  88 {
  89     COOR c;
  90
  91     FOREACH_SQUARE(c)
  92     {
  93         if ((c % 9) == 0) printf("\n");
  94         if ((c == 27) || (c == 54)) printf("-----------------------------------------------------------------------------\n");
  95         if (((c % 3) == 0) && ((c % 9) != 0)) printf(" | ");
  96         if (pos->rgSquare[c].uValue)
  97         {
  98             printf("[%u]     ", (unsigned)pos->rgSquare[c].uValue);
  99         }
 100         else
 101         {
 102             printf("%-7s ",
 103                    ShowPossibilities(pos->rgSquare[c].bvPossibilities));
 104         }
 105     }
 106     printf("\n");
 107 #ifdef DBG
 108     printf("%u empty squares...\n", (unsigned)pos->uEmpty);
 109 #endif
 110 }
 111
 112
 113
 114
 115 void
 116 DumpBoardHtml(POSITION *pos)
 117 /*++
 118
 119 Routine description:
 120
 121     Draw a text representation of the playing board.
 122
 123 Parameters:
 124
 125     POSITION *pos : position
 126
 127 Return value:
 128
 129     void
 130
 131 --*/
 132 {
 133     COOR c;
 134
 135     FOREACH_SQUARE(c)
 136     {
 137         if (pos->rgSquare[c].uValue)
 138         {
 139             printf("%u:%u\n", (unsigned)c,
 140                    (unsigned)pos->rgSquare[c].uValue);
 141         }
 142     }
 143     printf("\n");
 144     printf("%u empty squares...\n", (unsigned)pos->uEmpty);
 145 }
 146
 147 void
 148 DumpBoardSimple(POSITION *pos) {
 149     COOR c;
 150
 151     FOREACH_SQUARE(c)
 152     {
 153         if (pos->rgSquare[c].uValue) {
 154             printf("%u", (unsigned)pos->rgSquare[c].uValue);
 155         } else {
 156             printf("-");
 157         }
 158     }
 159     printf("\n");
 160 }
 161
 162
 163 BOOL
 164 LiftValue(POSITION *pos, COOR sq)
 165 {
 166     ULONG uValue = pos->rgSquare[sq].uValue;
 167     BITV bvMask = (1UL << (uValue - 1));
 168     COOR c;
 169     COOR cCol, cRow;
 170     ULONG x;
 171
 172     //
 173     // Make sure it's full
 174     //
 175     if (IS_EMPTY(uValue))
 176     {
 177         return(FALSE);
 178     }
 179
 180     //
 181     // uValue is a possibility on the file/rank/group again.
 182     //
 183     cCol = COL(sq);
 184     ASSERT(cCol == pos->rgSquare[sq].cCol);
 185     FOREACH_COL(c, cCol)
 186     {
 187         pos->rgSquare[c].bvPossibilities |= bvMask;
 188     }
 189
 190     cRow = ROW(sq);
 191     ASSERT(cRow == pos->rgSquare[sq].cRow);
 192     FOREACH_ROW(c, cRow)
 193     {
 194         pos->rgSquare[c].bvPossibilities |= bvMask;
 195     }
 196
 197     FOREACH_GROUP(c, pos->rgSquare[sq].cGroup, x)
 198     {
 199         pos->rgSquare[c].bvPossibilities |= bvMask;
 200     }
 201
 202     pos->uEmpty += 1;
 203     pos->rgSquare[sq].uValue = 0;
 204     pos->rgSquare[sq].bvPossibilities |= bvMask;
 205     pos->bvRemainingByGroup[pos->rgSquare[sq].cGroup] |= bvMask;
 206     pos->bvRemainingByCol[pos->rgSquare[sq].cCol] |= bvMask;
 207     pos->bvRemainingByRow[pos->rgSquare[sq].cRow] |= bvMask;
 208
 209     return(TRUE);
 210 }
 211
 212
 213
 214 BOOL
 215 PlaceValue(POSITION *pos, COOR sq, ULONG uValue, BOOL fReduce)
 216 /*++
 217
 218 Routine description:
 219
 220     Put a number in a square.
 221
 222 Parameters:
 223
 224     POSITION *pos : board
 225     COOR sq : square
 226     ULONG uValue : number
 227
 228 Return value:
 229
 230     BOOL : TRUE if move is legal, FALSE if it leads to an invalid position
 231
 232 --*/
 233 {
 234     BITV bvMask = ~(1UL << (uValue - 1));
 235     COOR c;
 236     COOR cCol, cRow;
 237     ULONG x;
 238
 239     //
 240     // Make sure it's empty
 241     //
 242     if (!IS_EMPTY(pos->rgSquare[sq].uValue))
 243     {
 244         if (pos->rgSquare[sq].uValue == uValue)
 245         {
 246             return(TRUE);
 247         }
 248         else
 249         {
 250             return(FALSE);
 251         }
 252     }
 253
 254     //
 255     // There can only be one uValue per file/rank/group
 256     //
 257     cCol = COL(sq);
 258     ASSERT(cCol == pos->rgSquare[sq].cCol);
 259     FOREACH_COL(c, cCol)
 260     {
 261         pos->rgSquare[c].bvPossibilities &= bvMask;
 262     }
 263
 264     cRow = ROW(sq);
 265     ASSERT(cRow == pos->rgSquare[sq].cRow);
 266     FOREACH_ROW(c, cRow)
 267     {
 268         pos->rgSquare[c].bvPossibilities &= bvMask;
 269     }
 270
 271     FOREACH_GROUP(c, pos->rgSquare[sq].cGroup, x)
 272     {
 273         pos->rgSquare[c].bvPossibilities &= bvMask;
 274     }
 275
 276     ASSERT(pos->uEmpty > 0);
 277     pos->uEmpty -= 1;
 278     ASSERT(pos->uEmpty < 81);
 279     pos->rgSquare[sq].uValue = uValue;
 280     pos->rgSquare[sq].bvPossibilities = (1 << (uValue - 1));
 281     pos->bvRemainingByGroup[pos->rgSquare[sq].cGroup] &= bvMask;
 282     pos->bvRemainingByCol[pos->rgSquare[sq].cCol] &= bvMask;
 283     pos->bvRemainingByRow[pos->rgSquare[sq].cRow] &= bvMask;
 284
 285     return(PositionIsLegal(pos, fReduce));
 286 }
 287
 288
 289
 290
 291 ULONG
 292 BitNumber(BITV x)
 293 /*++
 294
 295 Routine description:
 296
 297     Given a bit, return its number.
 298
 299 Parameters:
 300
 301     BITV x
 302
 303 Return value:
 304
 305     ULONG
 306
 307 --*/
 308 {
 309     ULONG u = 0;
 310     do
 311     {
 312         x >>= 1;
 313         u++;
 314     }
 315     while(x > 0);
 316     return(u);
 317 }
 318
 319
 320 ULONG
 321 BitCount(BITV x)
 322 /*++
 323
 324 Routine description:
 325
 326     Count the number of bits in a bitvector.
 327
 328 Parameters:
 329
 330     BITV x : bitv
 331
 332 Return value:
 333
 334     ULONG : population count
 335
 336 --*/
 337 {
 338     ULONG uCount = 0;
 339
 340     ASSERT(!(x & 0xFFFFFE00));
 341     while(x)
 342     {
 343         uCount += (x & 1);
 344         x >>= 1;
 345     }
 346     return(uCount);
 347 }
 348
 349
 350 ULONG
 351 LegalValue(POSITION *pos, COOR c)
 352 {
 353     ULONG x, y;
 354     if (!IS_EMPTY(pos->rgSquare[c].uValue))
 355     {
 356         return(pos->rgSquare[c].uValue);
 357     }
 358
 359     x = pos->rgSquare[c].bvPossibilities;
 360     if ((x & 0x1FF) == 0) return(0);
 361     do
 362     {
 363         y = 1 << (rand() % 9);
 364         if (y & x)
 365         {
 366             return(BitNumber(y));
 367         }
 368     }
 369     while(1);
 370 }
 371
 372
 373
 374
 375 BOOL
 376 PositionIsLegal(POSITION *pos, BOOL fReduce)
 377 /*++
 378
 379 Routine description:
 380
 381     Determine if a position is legal
 382
 383 Parameters:
 384
 385     POSITION *pos : board
 386
 387 Return value:
 388
 389     BOOL : TRUE on success, FALSE on failure
 390
 391 --*/
 392 {
 393     COOR c, sq, cOnly;
 394     ULONG x, y, uCount;
 395     BITV bvMaskFull, bvMaskPoss;
 396
 397     g_uNodes += 1;
 398 #ifdef DBG
 399     printf("Is this legal?\n");
 400     DumpBoardSimple(pos);
 401     printf("----------------------------------------------------------\n");
 402 #endif
 403
 404     FOREACH_SQUARE(c)
 405     {
 406         if (IS_EMPTY(pos->rgSquare[c].uValue))
 407         {
 408             x = pos->rgSquare[c].bvPossibilities;
 409             if (x == 0)
 410             {
 411 #ifdef DBG
 412                 printf("Nothing possible at sq %u\n", c);
 413 #endif
 414                 return(FALSE);
 415             }
 416         }
 417     }
 418
 419     //
 420     // Note: I don't combine the two loops here because this way we
 421     // detect invalid positions (empty squares w/ no legal moves in
 422     // them) earlier instead of recursing on obviously bad positions.
 423     //
 424     FOREACH_SQUARE(c)
 425     {
 426         if (IS_EMPTY(pos->rgSquare[c].uValue))
 427         {
 428             x = pos->rgSquare[c].bvPossibilities;
 429             if (ONE_BIT(x))
 430             {
 431 #ifdef DBG
 432                 printf("%u at %u is forced...\n", BitNumber(x), c);
 433 #endif
 434                 if ((TRUE == fReduce) &&
 435                     (FALSE == PlaceValue(pos, c, BitNumber(x), fReduce)))
 436                 {
 437 #ifdef DBG
 438                     printf("Couldn't place forced %u at sq %u\n",
 439                            BitNumber(x), c);
 440 #endif
 441                     return(FALSE);
 442                 }
 443             }
 444         }
 445     }
 446
 447     //
 448     // If there's only one square in a row|col|group that can be
 449     // a given number, make the move.
 450     //
 451     for (x = 1; x <= 256; x <<= 1)
 452     {
 453         for (c = 0; c < 9; c++)
 454         {
 455             uCount = 0;
 456             FOREACH_COL(sq, c)
 457             {
 458                 if (IS_EMPTY(pos->rgSquare[sq].uValue) &&
 459                     (pos->rgSquare[sq].bvPossibilities & x))
 460                 {
 461                     uCount++;
 462                     cOnly = sq;
 463                     if (uCount > 1) break;
 464                 }
 465             }
 466             if (uCount == 1)
 467             {
 468 #ifdef DBG
 469                 printf("%u at square %u is forced...\n", BitNumber(x), cOnly);
 470 #endif
 471                 if ((TRUE == fReduce) &&
 472                     (FALSE == PlaceValue(pos, cOnly, BitNumber(x), fReduce)))
 473                 {
 474                     return(FALSE);
 475                 }
 476             }
 477
 478             uCount = 0;
 479             FOREACH_ROW(sq, c)
 480             {
 481                 if (IS_EMPTY(pos->rgSquare[sq].uValue) &&
 482                     (pos->rgSquare[sq].bvPossibilities & x))
 483                 {
 484                     uCount++;
 485                     cOnly = sq;
 486                     if (uCount > 1) break;
 487                 }
 488             }
 489             if (uCount == 1)
 490             {
 491 #ifdef DBG
 492                 printf("%u at square %u is forced...\n", BitNumber(x), cOnly);
 493 #endif
 494                 if ((TRUE == fReduce) &&
 495                     (FALSE == PlaceValue(pos, cOnly, BitNumber(x), fReduce)))
 496                 {
 497                     return(FALSE);
 498                 }
 499             }
 500
 501             uCount = 0;
 502             FOREACH_GROUP(sq, c, y)
 503             {
 504                 if (IS_EMPTY(pos->rgSquare[sq].uValue) &&
 505                     (pos->rgSquare[sq].bvPossibilities & x))
 506                 {
 507                     uCount++;
 508                     cOnly = sq;
 509                     if (uCount > 1) break;
 510                 }
 511             }
 512             if (uCount == 1)
 513             {
 514 #ifdef DBG
 515                 printf("%u at square %u is forced...\n", BitNumber(x), cOnly);
 516 #endif
 517                 if ((TRUE == fReduce) &&
 518                     (FALSE == PlaceValue(pos, cOnly, BitNumber(x), fReduce)))
 519                 {
 520                     return(FALSE);
 521                 }
 522             }
 523         }
 524     }
 525
 526     for (c = 0; c < 9; c++)
 527     {
 528         bvMaskPoss = bvMaskFull = 0;
 529         FOREACH_ROW(sq, c)
 530         {
 531             bvMaskPoss |= pos->rgSquare[sq].bvPossibilities;
 532             if (!IS_EMPTY(pos->rgSquare[sq].uValue))
 533             {
 534                 ASSERT(pos->rgSquare[sq].bvPossibilities ==
 535                        (1 << pos->rgSquare[sq].uValue));
 536                 if (bvMaskFull & pos->rgSquare[sq].bvPossibilities)
 537                 {
 538 #ifdef DBG
 539                     printf("Two %u's in row %u.\n", pos->rgSquare[sq].uValue,
 540                            c);
 541 #endif
 542                     return(FALSE);
 543                 }
 544                 bvMaskFull |= pos->rgSquare[sq].bvPossibilities;
 545             }
 546         }
 547         if (bvMaskPoss != 0x1FF)
 548         {
 549 #ifdef DBG
 550             printf("Not everything is possible in row %u (%x).\n",
 551                    c, bvMaskPoss);
 552 #endif
 553             return(FALSE);
 554         }
 555
 556         bvMaskPoss = bvMaskFull = 0;
 557         FOREACH_COL(sq, c)
 558         {
 559             bvMaskPoss |= pos->rgSquare[sq].bvPossibilities;
 560             if (!IS_EMPTY(pos->rgSquare[sq].uValue))
 561             {
 562                 ASSERT(pos->rgSquare[sq].bvPossibilities ==
 563                        (1 << pos->rgSquare[sq].uValue));
 564                 if (bvMaskFull & pos->rgSquare[sq].bvPossibilities)
 565                 {
 566 #ifdef DBG
 567                     printf("Two %u's in col %u.\n", pos->rgSquare[sq].uValue,
 568                            c);
 569 #endif
 570                     return(FALSE);
 571                 }
 572                 bvMaskFull |= pos->rgSquare[sq].bvPossibilities;
 573             }
 574         }
 575         if (bvMaskPoss != 0x1FF)
 576         {
 577 #ifdef DBG
 578             printf("Not everything is possible in col %u (%x).\n",
 579                    c, bvMaskPoss);
 580 #endif
 581             return(FALSE);
 582         }
 583
 584         bvMaskPoss = bvMaskFull = 0;
 585         FOREACH_GROUP(sq, c, y)
 586         {
 587             bvMaskPoss |= pos->rgSquare[sq].bvPossibilities;
 588             if (!IS_EMPTY(pos->rgSquare[sq].uValue))
 589             {
 590                 ASSERT(pos->rgSquare[sq].bvPossibilities ==
 591                        (1 << pos->rgSquare[sq].uValue));
 592                 if (bvMaskFull & pos->rgSquare[sq].bvPossibilities)
 593                 {
 594 #ifdef DBG
 595                     printf("Two %u's in group %u.\n", pos->rgSquare[sq].uValue,
 596                            c);
 597 #endif
 598                     return(FALSE);
 599                 }
 600                 bvMaskFull |= pos->rgSquare[sq].bvPossibilities;
 601             }
 602         }
 603         if (bvMaskPoss != 0x1FF)
 604         {
 605 #ifdef DBG
 606             printf("Not everything is possible in group %u (%x).\n",
 607                    c, bvMaskPoss);
 608 #endif
 609             return(FALSE);
 610         }
 611     }
 612     return(TRUE);
 613 }
 614
 615
 616 void
 617 InitializePosition(POSITION *pos)
 618 /*++
 619
 620 Routine description:
 621
 622     Initialize a position to empty.
 623
 624 Parameters:
 625
 626     POSITION *pos : position
 627
 628 Return value:
 629
 630     void
 631
 632 --*/
 633 {
 634     COOR c;
 635     memset(pos, 0, sizeof(POSITION));
 636     pos->uEmpty = 81;
 637     FOREACH_SQUARE(c)
 638     {
 639         pos->rgSquare[c].bvPossibilities = 0x1FF;
 640         pos->rgSquare[c].cGroup = g_cGroup[c];
 641         pos->rgSquare[c].cRow = ROW(c);
 642         pos->rgSquare[c].cCol = COL(c);
 643     }
 644
 645     for (c = 0; c < 9; c++)
 646     {
 647         pos->bvRemainingByRow[c] = 0x1FF;
 648         pos->bvRemainingByCol[c] = 0x1FF;
 649         pos->bvRemainingByGroup[c] = 0x1FF;
 650     }
 651 }
 652
 653
 654 typedef struct _FEWEST
 655 {
 656     COOR c;
 657     ULONG uBitCount;
 658     BITV bvPossibilities;
 659 } FEWEST;
 660
 661
 662 void
 663 Sort(FEWEST *p, ULONG uLen)
 664 /*++
 665
 666 Routine description:
 667
 668     Selection sort to put the FEWEST array in order... this is so that
 669     that when we make a guess we are guessing at the square with the
 670     fewest possible choices.
 671
 672 Parameters:
 673
 674     FEWEST *p : start of array
 675     ULONG uLen : number of elements in it
 676
 677 Return value:
 678
 679     void
 680
 681 --*/
 682 {
 683     ULONG u, v;
 684     ULONG uMinPos;
 685     FEWEST temp;
 686
 687     for (u = 0; u < uLen; u++)
 688     {
 689         uMinPos = u;
 690         for (v = u + 1; v < uLen; v++)
 691         {
 692             if (p[v].uBitCount < p[uMinPos].uBitCount)
 693             {
 694                 uMinPos = v;
 695             }
 696         }
 697
 698         temp = p[u];
 699         p[u] = p[uMinPos];
 700         p[uMinPos] = temp;
 701     }
 702 }
 703
 704
 705 BOOL
 706 Solve(POSITION *pos, ULONG uDepth)
 707 /*++
 708
 709 Routine description:
 710
 711     Recursively solve a suduko position.
 712
 713 Parameters:
 714
 715     POSITION *pos : position
 716     ULONG uDepth : number of ply from root
 717
 718 Return value:
 719
 720     BOOL : TRUE if solved, FALSE if no solution exists
 721
 722 --*/
 723 {
 724     COOR c;
 725     ULONG u, v;
 726     POSITION p;
 727     FEWEST sFewest[81];
 728     BOOL fRet = FALSE;
 729
 730     g_uNodes++;
 731
 732 #ifdef DBG
 733     printf("Depth %u (%u node%s):\n", uDepth,
 734            g_uNodes,
 735            (g_uNodes != 1) ? "" : "s");
 736     DumpBoardSimple(pos);
 737     printf("---------------------------------------------------\n");
 738 #endif
 739
 740     //
 741     // Find the square with the fewest possibilities
 742     //
 743     FOREACH_SQUARE(c)
 744     {
 745         sFewest[c].c = c;
 746         sFewest[c].bvPossibilities = pos->rgSquare[c].bvPossibilities;
 747         sFewest[c].uBitCount = BitCount(pos->rgSquare[c].bvPossibilities);
 748         if ((pos->rgSquare[c].uValue == 0) && (sFewest[c].uBitCount == 0))
 749         {
 750             ASSERT(!sFewest[c].bvPossibilities);
 751 #ifdef DBG
 752             printf("%u: Found inconsistency at square %u.\n", uDepth, c);
 753             DumpBoard(pos);
 754 #endif
 755             goto end;
 756         }
 757     }
 758     Sort(sFewest, 81);
 759
 760     //
 761     // Make the guess
 762     //
 763     FOREACH_SQUARE(v) {
 764         if (IS_EMPTY(pos->rgSquare[sFewest[v].c].uValue)) {
 765             ASSERT(sFewest[v].uBitCount > 0);
 766             for (u = 1; u <= 9; u++) {
 767
 768                 //
 769                 // Only make guesses that are legal.  Don't "guess"
 770                 // the same thing as a prior solution.
 771                 //
 772                 if ((sFewest[v].bvPossibilities & (1 << (u - 1))) &&
 773                     ((g_uSolutions == 0) ||
 774                      (g_Solution.rgSquare[sFewest[v].c].uValue != u))) {
 775                     memcpy(&p, pos, sizeof(p));
 776                     g_uGuesses += 1;
 777 #ifdef DBG
 778                     printf("%u: Guessing %u at square %u\n",
 779                            uDepth, u, sFewest[v].c);
 780 #endif
 781                     if ((FALSE == PlaceValue(pos, sFewest[v].c, u, TRUE)) ||
 782                         (FALSE == Solve(pos, uDepth + 1)))
 783                     {
 784                         //
 785                         // Unmake the guess move.
 786                         //
 787 #ifdef DBG
 788                         printf("%u: Bad guess (%u at %u), taking it back.\n",
 789                                uDepth, u, sFewest[v].c);
 790 #endif
 791                         memcpy(pos, &p, sizeof(p));
 792
 793                         //
 794                         // We've learned that the guess is wrong, mask it
 795                         // off the possibilities bitv.
 796                         //
 797                         pos->rgSquare[sFewest[v].c].bvPossibilities &=
 798                             ~(1 << (u - 1));
 799
 800                         //
 801                         // Are we in a screwed up state now after masking
 802                         // off that bit?  If so something above us in the
 803                         // callstack is screwed up.
 804                         //
 805                         if (pos->rgSquare[sFewest[v].c].bvPossibilities == 0)
 806                         {
 807 #ifdef DBG
 808                             printf("%u: Nothing possible at square %u.\n",
 809                                    uDepth, sFewest[v].c);
 810 #endif
 811                             goto end;
 812                         }
 813                     }
 814                     else
 815                     {
 816                         //
 817                         // This move leads to a win.  Count it as a
 818                         // solution and carry on.
 819                         //
 820 #ifdef DBG
 821                         printf("%u: Guess of %u at square %u leads to a "
 822                                "solution\n",
 823                                uDepth, u, sFewest[v].c);
 824 #endif
 825                         fRet = TRUE;
 826                         if (g_uSolutions == 1)
 827                         {
 828                             memcpy(pos, &p, sizeof(p));
 829                         } else {
 830                             goto end;
 831                         }
 832                     }
 833                 }
 834             }
 835         }
 836     }
 837
 838     if (0 == pos->uEmpty)
 839     {
 840         fRet = TRUE;
 841         g_uSolutions += 1;
 842 #ifdef DBG
 843         printf("%u: Puzzle is solved, solution number %u\n",
 844                uDepth, g_uSolutions);
 845         DumpBoardSimple(pos);
 846 #endif
 847         if (g_uSolutions == 1)
 848         {
 849             memcpy(&g_Solution, pos, sizeof(POSITION));
 850         }
 851         goto end;
 852     }
 853
 854  end:
 855     return fRet;
 856 }
 857
 858
 859 void
 860 GeneratePuzzle(BOOL fHard, POSITION *pos)
 861 {
 862     COOR c, x;
 863     ULONG v;
 864     POSITION p;
 865     ULONG u;
 866     ULONG uTries;
 867     COOR cSeed[] = {
 868         1, 7, 12, 14, 17, 27, 31, 35, 37,40, 43,
 869         45, 49, 53, 63, 66, 68, 71, 73, 79, 0 };
 870
 871     srand(time(0));
 872     u = 0;
 873     do
 874     {
 875         //
 876         // Clear the board
 877         //
 878         InitializePosition(pos);
 879
 880         if (!fHard)
 881         {
 882             //
 883             // Place a number, try to solve it, repeat...
 884             //
 885             while(pos->uEmpty > 45)
 886             {
 887                 c = RANDOM_COOR;
 888                 if (IS_EMPTY(pos->rgSquare[c].uValue))
 889                 {
 890                     v = LegalValue(pos, c);
 891                     if (0 == v) break;
 892
 893                     //
 894                     // See if the rest can be solved by deduction...
 895                     //
 896                     memcpy(&p, pos, sizeof(p));
 897                     if ((TRUE == PlaceValue(pos, c, v, TRUE)) &&
 898                         (pos->uEmpty == 0))
 899                     {
 900                         memcpy(pos, &p, sizeof(p));
 901                         pos->rgSquare[c].uValue = v;
 902                         return;
 903                     }
 904                 }
 905             }
 906         }
 907         else
 908         {
 909             //
 910             // Throw some random numbers out there on the board...
 911             //
 912             u = 0;
 913             while(cSeed[u] != 0) {
 914                 if (IS_EMPTY(pos->rgSquare[cSeed[u]].uValue))
 915                 {
 916                     v = LegalValue(pos, cSeed[u]);
 917                     if (0 == v) break;
 918
 919                     (void)PlaceValue(pos, cSeed[u], v, TRUE);
 920                 }
 921                 u++;
 922             }
 923
 924             //
 925             // Solve the puzzle within these constraints...
 926             //
 927             g_uSolutions = g_uGuesses = g_uNodes = 0;
 928             if (TRUE == Solve(pos, 0))
 929             {
 930                 //
 931                 // Now start taking away values until you get a puzzle
 932                 // that is still uniquely solvable but requires
 933                 // guessing
 934                 //
 935                 uTries = 0;
 936                 while(1) {
 937                     c = RANDOM_COOR;
 938                     if (!IS_EMPTY(pos->rgSquare[c].uValue)) {
 939                         InitializePosition(&p);
 940                         FOREACH_SQUARE(x) {
 941                             if ((x != c) &&
 942                                 (!IS_EMPTY(pos->rgSquare[x].uValue))) {
 943                                 PlaceValue(&p, x,
 944                                            pos->rgSquare[x].uValue, FALSE);
 945                             }
 946                         }
 947                         ASSERT(p.uEmpty - 1 == pos->uEmpty);
 948                         g_uSolutions = g_uGuesses = g_uNodes = 0;
 949                         if ((TRUE == Solve(&p, 0)) && (g_uSolutions == 1))
 950                         {
 951                             uTries = 0;
 952                             memcpy(pos, &p, sizeof(p));
 953                             if ((g_uGuesses > 5) &&
 954                                 (g_uNodes > 200) &&
 955                                 (pos->uEmpty > 55)) {
 956                                 printf("%u guesses, %u nodes.\n",
 957                                        g_uGuesses, g_uNodes);
 958                                 return;
 959                             }
 960                         }
 961                         else
 962                         {
 963                             uTries++;
 964                             if (uTries > 50) {
 965                                 usleep(20);
 966                                 break;
 967                             }
 968                         }
 969                     }
 970                 }
 971             }
 972         }
 973     }
 974     while(1);
 975 }
 976
 977
 978 int
 979 main(int argc, char *argv[])
 980 /*++
 981
 982 Routine description:
 983
 984     Program entry point
 985
 986 Parameters:
 987
 988     void
 989
 990 Return value:
 991
 992     int
 993
 994 --*/
 995 {
 996     POSITION pos;
 997     char buf[256];
 998     char *p;
 999     COOR c;
1000
1001     InitializePosition(&pos);
1002
1003     memset(buf, 0, sizeof(buf));
1004
1005     if (argc == 1)
1006     {
1007         printf("Enter board: ");
1008         scanf("%255s", buf);
1009     }
1010     else
1011     {
1012         if (!strcmp(argv[1], "--create-easy"))
1013         {
1014             GeneratePuzzle(FALSE, &pos);
1015             DumpBoardHtml(&pos);
1016             DumpBoardSimple(&pos);
1017             exit(0);
1018         }
1019         else if (!strcmp(argv[1], "--create-hard"))
1020         {
1021             GeneratePuzzle(TRUE, &pos);
1022             DumpBoardHtml(&pos);
1023             DumpBoardSimple(&pos);
1024             exit(0);
1025         }
1026         else
1027         {
1028             strncpy(buf, argv[1], 255);
1029         }
1030     }
1031
1032     //
1033     // Solve...
1034     //
1035     p = buf;
1036     c = 0;
1037     while(*p)
1038     {
1039         if (!isspace(*p))
1040         {
1041             if (isdigit(*p) && (*p != '0'))
1042             {
1043                 if (FALSE == PlaceValue(&pos, c, *p - '0', TRUE))
1044                 {
1045                     printf("%u!%u\n",
1046                            (unsigned)c, (unsigned)(*p - '0'));
1047                     exit(0);
1048                 }
1049             }
1050             c++;
1051         }
1052         p++;
1053     }
1054
1055     g_uSolutions = g_uGuesses = g_uNodes = 0;
1056     if (TRUE == Solve(&pos, 0)) {
1057         memcpy(&pos, &g_Solution, sizeof(pos));
1058         DumpBoardHtml(&pos);
1059         printf("%u solutions, %u nodes, %u guesses.\n",
1060                g_uSolutions, g_uNodes, g_uGuesses);
1061     }
1062     else
1063     {
1064         DumpBoardHtml(&pos);
1065         printf("No solution found...\n");
1066     }
1067     exit(0);
1068 }