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