Initial commit of sudoku puzzle solver.

1 files changed, 1069 insertions, 0 deletions

diff --git a/puzzle.c b/puzzle.c
new file mode 100644
index 0000000..e8e50c6
--- /dev/null
+++ b/puzzle.c
@@ -0,0 +1,1069 @@
+/* Copyright (c) 2006 Scott Gasch
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+ 
+#include <stdlib.h>
+#include <stdio.h>
+#include <string.h>
+#include <ctype.h>
+#include <time.h>
+//#include <unistd.h>
+
+#include "puzzle.h"
+
+ULONG g_uNodes = 0;
+ULONG g_uGuesses = 0;
+ULONG g_uSolutions = 0;
+POSITION g_Solution;
+
+BOOL
+PositionIsLegal(POSITION *, BOOL);
+
+
+char *
+ShowPossibilities(BITV bv)
+/*++
+
+Routine description:
+
+    Return a text representation of the possible moves at a square.
+
+Parameters:
+
+    BITV bv
+
+Return value:
+
+    char
+
+--*/
+{
+    static char bits[] = "*123456789";
+    static char sz[10];
+    ULONG u;
+    ULONG v;
+    
+    memset(&sz, 0, sizeof(sz));
+    v = 0;
+    for (u = 1; u < 10; u++)
+    {
+        if (bv & (1 << (u - 1)))
+        {
+            sz[v++] = bits[u];
+        }
+    }
+    return(sz);
+}
+    
+
+
+
+void 
+DumpBoard(POSITION *pos)
+/*++
+
+Routine description:
+
+    Draw a text representation of the playing board.
+
+Parameters:
+
+    POSITION *pos : position
+
+Return value:
+
+    void
+
+--*/
+{
+    COOR c;
+    
+    FOREACH_SQUARE(c)
+    {
+        if ((c % 9) == 0) printf("\n");
+        if ((c == 27) || (c == 54)) printf("-----------------------------------------------------------------------------\n");
+        if (((c % 3) == 0) && ((c % 9) != 0)) printf(" | ");
+        if (pos->rgSquare[c].uValue)
+        {
+            printf("[%u]     ", (unsigned)pos->rgSquare[c].uValue);
+        }
+        else
+        {
+            printf("%-7s ", 
+                   ShowPossibilities(pos->rgSquare[c].bvPossibilities));
+        }
+    }
+    printf("\n");
+#ifdef DBG
+    printf("%u empty squares...\n", (unsigned)pos->uEmpty);
+#endif
+}
+
+
+
+
+void 
+DumpBoardHtml(POSITION *pos)
+/*++
+
+Routine description:
+
+    Draw a text representation of the playing board.
+
+Parameters:
+
+    POSITION *pos : position
+
+Return value:
+
+    void
+
+--*/
+{
+    COOR c;
+
+    FOREACH_SQUARE(c)
+    {
+        if (pos->rgSquare[c].uValue)
+        {
+            printf("%u:%u\n", (unsigned)c, 
+                   (unsigned)pos->rgSquare[c].uValue);
+        }
+    }
+    printf("\n");
+    printf("%u empty squares...\n", (unsigned)pos->uEmpty);
+}
+
+void
+DumpBoardSimple(POSITION *pos) {
+    COOR c;
+
+    FOREACH_SQUARE(c) 
+    {
+        if (pos->rgSquare[c].uValue) {
+            printf("%u", (unsigned)pos->rgSquare[c].uValue);
+        } else {
+            printf("-");
+        }
+    }
+    printf("\n");
+}
+
+
+BOOL
+LiftValue(POSITION *pos, COOR sq)
+{
+    ULONG uValue = pos->rgSquare[sq].uValue;
+    BITV bvMask = (1UL << (uValue - 1));
+    COOR c;
+    COOR cCol, cRow;
+    ULONG x;
+    
+    // 
+    // Make sure it's full
+    //
+    if (IS_EMPTY(uValue))
+    {
+        return(FALSE);
+    }
+    
+    //
+    // uValue is a possibility on the file/rank/group again.
+    // 
+    cCol = COL(sq);
+    ASSERT(cCol == pos->rgSquare[sq].cCol);
+    FOREACH_COL(c, cCol)
+    {
+        pos->rgSquare[c].bvPossibilities |= bvMask;
+    }
+    
+    cRow = ROW(sq);
+    ASSERT(cRow == pos->rgSquare[sq].cRow);
+    FOREACH_ROW(c, cRow)
+    {
+        pos->rgSquare[c].bvPossibilities |= bvMask;
+    }
+    
+    FOREACH_GROUP(c, pos->rgSquare[sq].cGroup, x)
+    {
+        pos->rgSquare[c].bvPossibilities |= bvMask;
+    }
+
+    pos->uEmpty += 1;
+    pos->rgSquare[sq].uValue = 0;
+    pos->rgSquare[sq].bvPossibilities |= bvMask;
+    pos->bvRemainingByGroup[pos->rgSquare[sq].cGroup] |= bvMask;
+    pos->bvRemainingByCol[pos->rgSquare[sq].cCol] |= bvMask;
+    pos->bvRemainingByRow[pos->rgSquare[sq].cRow] |= bvMask;
+
+    return(TRUE);
+}
+
+
+
+BOOL 
+PlaceValue(POSITION *pos, COOR sq, ULONG uValue, BOOL fReduce)
+/*++
+
+Routine description:
+
+    Put a number in a square.
+
+Parameters:
+
+    POSITION *pos : board
+    COOR sq : square
+    ULONG uValue : number
+
+Return value:
+
+    BOOL : TRUE if move is legal, FALSE if it leads to an invalid position
+
+--*/
+{
+    BITV bvMask = ~(1UL << (uValue - 1));
+    COOR c;
+    COOR cCol, cRow;
+    ULONG x;
+
+    // 
+    // Make sure it's empty
+    //
+    if (!IS_EMPTY(pos->rgSquare[sq].uValue))
+    {
+        if (pos->rgSquare[sq].uValue == uValue)
+        {
+            return(TRUE);
+        }
+        else
+        {
+            return(FALSE);
+        }
+    }
+    
+    //
+    // There can only be one uValue per file/rank/group
+    // 
+    cCol = COL(sq);
+    ASSERT(cCol == pos->rgSquare[sq].cCol);
+    FOREACH_COL(c, cCol)
+    {
+        pos->rgSquare[c].bvPossibilities &= bvMask;
+    }
+    
+    cRow = ROW(sq);
+    ASSERT(cRow == pos->rgSquare[sq].cRow);
+    FOREACH_ROW(c, cRow)
+    {
+        pos->rgSquare[c].bvPossibilities &= bvMask;
+    }
+    
+    FOREACH_GROUP(c, pos->rgSquare[sq].cGroup, x)
+    {
+        pos->rgSquare[c].bvPossibilities &= bvMask;
+    }
+
+    ASSERT(pos->uEmpty > 0);
+    pos->uEmpty -= 1;
+    ASSERT(pos->uEmpty < 81);
+    pos->rgSquare[sq].uValue = uValue;
+    pos->rgSquare[sq].bvPossibilities = (1 << (uValue - 1));
+    pos->bvRemainingByGroup[pos->rgSquare[sq].cGroup] &= bvMask;
+    pos->bvRemainingByCol[pos->rgSquare[sq].cCol] &= bvMask;
+    pos->bvRemainingByRow[pos->rgSquare[sq].cRow] &= bvMask;
+    
+    return(PositionIsLegal(pos, fReduce));
+}
+
+
+
+
+ULONG 
+BitNumber(BITV x)
+/*++
+
+Routine description:
+
+    Given a bit, return its number.
+
+Parameters:
+
+    BITV x
+
+Return value:
+
+    ULONG
+
+--*/
+{
+    ULONG u = 0;
+    do
+    {
+        x >>= 1;
+        u++;
+    }
+    while(x > 0);
+    return(u);
+}
+
+
+ULONG 
+BitCount(BITV x)
+/*++
+
+Routine description:
+
+    Count the number of bits in a bitvector.
+
+Parameters:
+
+    BITV x : bitv
+
+Return value:
+
+    ULONG : population count
+
+--*/
+{
+    ULONG uCount = 0;
+
+    ASSERT(!(x & 0xFFFFFE00));
+    while(x)
+    {
+        uCount += (x & 1);
+        x >>= 1;
+    }
+    return(uCount);
+}
+
+
+ULONG
+LegalValue(POSITION *pos, COOR c)
+{
+    ULONG x, y;
+    if (!IS_EMPTY(pos->rgSquare[c].uValue))
+    {
+        return(pos->rgSquare[c].uValue);
+    }
+
+    x = pos->rgSquare[c].bvPossibilities;
+    if ((x & 0x1FF) == 0) return(0);
+    do
+    {
+        y = 1 << (rand() % 9); 
+        if (y & x)
+        {
+            return(BitNumber(y));
+        }
+    }
+    while(1);
+}
+
+
+
+
+BOOL 
+PositionIsLegal(POSITION *pos, BOOL fReduce)
+/*++
+
+Routine description:
+
+    Determine if a position is legal
+
+Parameters:
+
+    POSITION *pos : board
+
+Return value:
+
+    BOOL : TRUE on success, FALSE on failure
+
+--*/
+{
+    COOR c, sq, cOnly;
+    ULONG x, y, uCount;
+    BITV bvMaskFull, bvMaskPoss;
+
+    g_uNodes += 1;
+#ifdef DBG    
+    printf("Is this legal?\n");
+    DumpBoardSimple(pos);
+    printf("----------------------------------------------------------\n");
+#endif
+    
+    FOREACH_SQUARE(c)
+    {
+        if (IS_EMPTY(pos->rgSquare[c].uValue))
+        {
+            x = pos->rgSquare[c].bvPossibilities;
+            if (x == 0)
+            {
+#ifdef DBG
+                printf("Nothing possible at sq %u\n", c);
+#endif
+                return(FALSE);
+            }
+        }
+    }
+    
+    //
+    // Note: I don't combine the two loops here because this way we
+    // detect invalid positions (empty squares w/ no legal moves in
+    // them) earlier instead of recursing on obviously bad positions.
+    // 
+    FOREACH_SQUARE(c)
+    {
+        if (IS_EMPTY(pos->rgSquare[c].uValue))
+        {
+            x = pos->rgSquare[c].bvPossibilities;
+            if (ONE_BIT(x))
+            {
+#ifdef DBG
+                printf("%u at %u is forced...\n", BitNumber(x), c);
+#endif
+                if ((TRUE == fReduce) &&
+                    (FALSE == PlaceValue(pos, c, BitNumber(x), fReduce)))
+                {
+#ifdef DBG
+                    printf("Couldn't place forced %u at sq %u\n", 
+                           BitNumber(x), c);
+#endif
+                    return(FALSE);
+                }
+            }
+        }
+    }
+
+    //
+    // If there's only one square in a row|col|group that can be
+    // a given number, make the move.
+    // 
+    for (x = 1; x <= 256; x <<= 1)
+    {
+        for (c = 0; c < 9; c++)
+        {
+            uCount = 0;
+            FOREACH_COL(sq, c)
+            {
+                if (IS_EMPTY(pos->rgSquare[sq].uValue) &&
+                    (pos->rgSquare[sq].bvPossibilities & x))
+                {
+                    uCount++;
+                    cOnly = sq;
+                    if (uCount > 1) break;
+                }
+            }
+            if (uCount == 1)
+            {
+#ifdef DBG
+                printf("%u at square %u is forced...\n", BitNumber(x), cOnly);
+#endif
+                if ((TRUE == fReduce) && 
+                    (FALSE == PlaceValue(pos, cOnly, BitNumber(x), fReduce)))
+                {
+                    return(FALSE);
+                }
+            }
+                
+            uCount = 0;
+            FOREACH_ROW(sq, c)
+            {
+                if (IS_EMPTY(pos->rgSquare[sq].uValue) &&
+                    (pos->rgSquare[sq].bvPossibilities & x))
+                {
+                    uCount++;
+                    cOnly = sq;
+                    if (uCount > 1) break;
+                }
+            }
+            if (uCount == 1)
+            {
+#ifdef DBG
+                printf("%u at square %u is forced...\n", BitNumber(x), cOnly);
+#endif
+                if ((TRUE == fReduce) && 
+                    (FALSE == PlaceValue(pos, cOnly, BitNumber(x), fReduce)))
+                {
+                    return(FALSE);
+                }
+            }
+
+            uCount = 0;
+            FOREACH_GROUP(sq, c, y)
+            {
+                if (IS_EMPTY(pos->rgSquare[sq].uValue) &&
+                    (pos->rgSquare[sq].bvPossibilities & x))
+                {
+                    uCount++;
+                    cOnly = sq;
+                    if (uCount > 1) break;
+                }
+            }
+            if (uCount == 1)
+            {
+#ifdef DBG
+                printf("%u at square %u is forced...\n", BitNumber(x), cOnly);
+#endif
+                if ((TRUE == fReduce) && 
+                    (FALSE == PlaceValue(pos, cOnly, BitNumber(x), fReduce)))
+                {
+                    return(FALSE);
+                }
+            }
+        }
+    }
+    
+    for (c = 0; c < 9; c++)
+    {
+        bvMaskPoss = bvMaskFull = 0;
+        FOREACH_ROW(sq, c)
+        {
+            bvMaskPoss |= pos->rgSquare[sq].bvPossibilities;
+            if (!IS_EMPTY(pos->rgSquare[sq].uValue))
+            {
+                ASSERT(pos->rgSquare[sq].bvPossibilities == 
+                       (1 << pos->rgSquare[sq].uValue));
+                if (bvMaskFull & pos->rgSquare[sq].bvPossibilities)
+                {
+#ifdef DBG
+                    printf("Two %u's in row %u.\n", pos->rgSquare[sq].uValue,
+                           c);
+#endif
+                    return(FALSE);
+                }
+                bvMaskFull |= pos->rgSquare[sq].bvPossibilities;
+            }
+        }
+        if (bvMaskPoss != 0x1FF)
+        {
+#ifdef DBG
+            printf("Not everything is possible in row %u (%x).\n", 
+                   c, bvMaskPoss);
+#endif
+            return(FALSE);
+        }
+        
+        bvMaskPoss = bvMaskFull = 0;
+        FOREACH_COL(sq, c)
+        {
+            bvMaskPoss |= pos->rgSquare[sq].bvPossibilities;
+            if (!IS_EMPTY(pos->rgSquare[sq].uValue))
+            {
+                ASSERT(pos->rgSquare[sq].bvPossibilities == 
+                       (1 << pos->rgSquare[sq].uValue));
+                if (bvMaskFull & pos->rgSquare[sq].bvPossibilities)
+                {
+#ifdef DBG
+                    printf("Two %u's in col %u.\n", pos->rgSquare[sq].uValue,
+                           c);
+#endif
+                    return(FALSE);
+                }
+                bvMaskFull |= pos->rgSquare[sq].bvPossibilities;
+            }
+        }
+        if (bvMaskPoss != 0x1FF)
+        {
+#ifdef DBG
+            printf("Not everything is possible in col %u (%x).\n", 
+                   c, bvMaskPoss);
+#endif
+            return(FALSE);
+        }
+
+        bvMaskPoss = bvMaskFull = 0;
+        FOREACH_GROUP(sq, c, y)
+        {
+            bvMaskPoss |= pos->rgSquare[sq].bvPossibilities;
+            if (!IS_EMPTY(pos->rgSquare[sq].uValue))
+            {
+                ASSERT(pos->rgSquare[sq].bvPossibilities == 
+                       (1 << pos->rgSquare[sq].uValue));
+                if (bvMaskFull & pos->rgSquare[sq].bvPossibilities)
+                {
+#ifdef DBG
+                    printf("Two %u's in group %u.\n", pos->rgSquare[sq].uValue,
+                           c);
+#endif
+                    return(FALSE);
+                }
+                bvMaskFull |= pos->rgSquare[sq].bvPossibilities;
+            }
+        }
+        if (bvMaskPoss != 0x1FF)
+        {
+#ifdef DBG
+            printf("Not everything is possible in group %u (%x).\n", 
+                   c, bvMaskPoss);
+#endif
+            return(FALSE);
+        }
+    }
+    return(TRUE);
+}
+
+
+void 
+InitializePosition(POSITION *pos)
+/*++
+
+Routine description:
+
+    Initialize a position to empty.
+
+Parameters:
+
+    POSITION *pos : position
+
+Return value:
+
+    void
+
+--*/
+{
+    COOR c;
+    memset(pos, 0, sizeof(POSITION));
+    pos->uEmpty = 81;
+    FOREACH_SQUARE(c)
+    {
+        pos->rgSquare[c].bvPossibilities = 0x1FF;
+        pos->rgSquare[c].cGroup = g_cGroup[c];
+        pos->rgSquare[c].cRow = ROW(c);
+        pos->rgSquare[c].cCol = COL(c);
+    }
+    
+    for (c = 0; c < 9; c++)
+    {
+        pos->bvRemainingByRow[c] = 0x1FF;
+        pos->bvRemainingByCol[c] = 0x1FF;
+        pos->bvRemainingByGroup[c] = 0x1FF;
+    }
+}
+
+
+typedef struct _FEWEST
+{
+    COOR c;
+    ULONG uBitCount;
+    BITV bvPossibilities;
+} FEWEST;
+
+
+void 
+Sort(FEWEST *p, ULONG uLen)
+/*++
+
+Routine description:
+
+    Selection sort to put the FEWEST array in order... this is so that 
+    that when we make a guess we are guessing at the square with the 
+    fewest possible choices.
+    
+Parameters:
+
+    FEWEST *p : start of array
+    ULONG uLen : number of elements in it
+
+Return value:
+
+    void
+
+--*/
+{
+    ULONG u, v;
+    ULONG uMinPos;
+    FEWEST temp;
+    
+    for (u = 0; u < uLen; u++)
+    {
+        uMinPos = u;
+        for (v = u + 1; v < uLen; v++)
+        {
+            if (p[v].uBitCount < p[uMinPos].uBitCount)
+            {
+                uMinPos = v;
+            }
+        }
+        
+        temp = p[u];
+        p[u] = p[uMinPos];
+        p[uMinPos] = temp;
+    }
+}
+
+
+BOOL 
+Solve(POSITION *pos, ULONG uDepth)
+/*++
+
+Routine description:
+
+    Recursively solve a suduko position.
+
+Parameters:
+
+    POSITION *pos : position
+    ULONG uDepth : number of ply from root
+
+Return value:
+
+    BOOL : TRUE if solved, FALSE if no solution exists
+
+--*/
+{
+    COOR c;
+    ULONG u, v;
+    POSITION p;
+    FEWEST sFewest[81];
+    BOOL fRet = FALSE;
+
+    g_uNodes++;
+    
+#ifdef DBG
+    printf("Depth %u (%u node%s):\n", uDepth, 
+           g_uNodes, 
+           (g_uNodes != 1) ? "" : "s");
+    DumpBoardSimple(pos);
+    printf("---------------------------------------------------\n");
+#endif
+
+    //
+    // Find the square with the fewest possibilities
+    //
+    FOREACH_SQUARE(c)
+    {
+        sFewest[c].c = c;
+        sFewest[c].bvPossibilities = pos->rgSquare[c].bvPossibilities;
+        sFewest[c].uBitCount = BitCount(pos->rgSquare[c].bvPossibilities);
+        if ((pos->rgSquare[c].uValue == 0) && (sFewest[c].uBitCount == 0))
+        {
+            ASSERT(!sFewest[c].bvPossibilities);
+#ifdef DBG
+            printf("%u: Found inconsistency at square %u.\n", uDepth, c);
+			DumpBoard(pos);
+#endif
+            goto end;
+        }
+    }
+    Sort(sFewest, 81);
+
+    //
+    // Make the guess
+    // 
+    FOREACH_SQUARE(v) {
+        if (IS_EMPTY(pos->rgSquare[sFewest[v].c].uValue)) {
+            ASSERT(sFewest[v].uBitCount > 0);
+            for (u = 1; u <= 9; u++) {
+
+                //
+                // Only make guesses that are legal.  Don't "guess"
+                // the same thing as a prior solution. 
+                //
+                if ((sFewest[v].bvPossibilities & (1 << (u - 1))) &&
+                    ((g_uSolutions == 0) ||
+                     (g_Solution.rgSquare[sFewest[v].c].uValue != u))) {
+                    memcpy(&p, pos, sizeof(p));
+                    g_uGuesses += 1;
+#ifdef DBG
+                    printf("%u: Guessing %u at square %u\n",
+                           uDepth, u, sFewest[v].c);
+#endif
+                    if ((FALSE == PlaceValue(pos, sFewest[v].c, u, TRUE)) ||
+                        (FALSE == Solve(pos, uDepth + 1)))
+                    {
+                        //
+                        // Unmake the guess move.
+                        //
+#ifdef DBG
+                        printf("%u: Bad guess (%u at %u), taking it back.\n", 
+                               uDepth, u, sFewest[v].c);
+#endif
+                        memcpy(pos, &p, sizeof(p));
+
+                        //
+                        // We've learned that the guess is wrong, mask it
+                        // off the possibilities bitv.
+                        //
+                        pos->rgSquare[sFewest[v].c].bvPossibilities &=
+                            ~(1 << (u - 1));
+
+                        //
+                        // Are we in a screwed up state now after masking
+                        // off that bit?  If so something above us in the
+                        // callstack is screwed up.
+                        //
+                        if (pos->rgSquare[sFewest[v].c].bvPossibilities == 0)
+                        {
+#ifdef DBG
+                            printf("%u: Nothing possible at square %u.\n", 
+                                   uDepth, sFewest[v].c);
+#endif
+                            goto end;
+                        }
+                    }
+                    else
+                    {
+                        //
+                        // This move leads to a win.  Count it as a
+                        // solution and carry on.
+                        //
+#ifdef DBG
+                        printf("%u: Guess of %u at square %u leads to a "
+                               "solution\n",
+                               uDepth, u, sFewest[v].c);
+#endif
+                        fRet = TRUE;
+                        if (g_uSolutions == 1) 
+                        {
+                            memcpy(pos, &p, sizeof(p));
+                        } else {
+                            goto end;
+                        }
+                    }
+                }
+            }
+        }
+    }
+
+    if (0 == pos->uEmpty) 
+    {
+        fRet = TRUE;
+        g_uSolutions += 1;
+#ifdef DBG
+        printf("%u: Puzzle is solved, solution number %u\n", 
+               uDepth, g_uSolutions);
+        DumpBoardSimple(pos);
+#endif
+        if (g_uSolutions == 1) 
+        {
+            memcpy(&g_Solution, pos, sizeof(POSITION));
+        }
+        goto end;
+    }
+    
+ end:
+    return fRet;
+}
+
+
+void 
+GeneratePuzzle(BOOL fHard, POSITION *pos)
+{
+    COOR c, x;
+    ULONG v;
+    POSITION p;
+    ULONG u;
+	ULONG uTries;
+    COOR cSeed[] = { 
+        1, 7, 12, 14, 17, 27, 31, 35, 37,40, 43, 
+        45, 49, 53, 63, 66, 68, 71, 73, 79, 0 };
+
+    srand(time(0));
+    u = 0;
+    do
+    {
+        //
+        // Clear the board
+        //
+        InitializePosition(pos);
+
+        if (!fHard)
+        {
+            //
+            // Place a number, try to solve it, repeat...
+            //
+            while(pos->uEmpty > 45)
+            {
+                c = RANDOM_COOR;
+                if (IS_EMPTY(pos->rgSquare[c].uValue))
+                {
+                    v = LegalValue(pos, c);
+                    if (0 == v) break;
+
+                    //
+                    // See if the rest can be solved by deduction...
+                    //
+                    memcpy(&p, pos, sizeof(p));
+                    if ((TRUE == PlaceValue(pos, c, v, TRUE)) &&
+                        (pos->uEmpty == 0))
+                    {
+                        memcpy(pos, &p, sizeof(p));
+                        pos->rgSquare[c].uValue = v;
+                        return;
+                    }
+                }
+            }
+        }
+        else
+        {
+            //
+            // Throw some random numbers out there on the board...
+            //
+            u = 0;
+            while(cSeed[u] != 0) {
+                if (IS_EMPTY(pos->rgSquare[cSeed[u]].uValue))
+                {
+                    v = LegalValue(pos, cSeed[u]);
+                    if (0 == v) break;
+
+                    (void)PlaceValue(pos, cSeed[u], v, TRUE);
+                }
+                u++;
+            }
+            
+            //
+            // Solve the puzzle within these constraints...
+            //
+            g_uSolutions = g_uGuesses = g_uNodes = 0;
+            if (TRUE == Solve(pos, 0))
+            {
+                //
+                // Now start taking away values until you get a puzzle
+                // that is still uniquely solvable but requires
+                // guessing
+                //
+				uTries = 0;
+                while(1) {
+                    c = RANDOM_COOR;				
+                    if (!IS_EMPTY(pos->rgSquare[c].uValue)) {
+				        InitializePosition(&p);
+						FOREACH_SQUARE(x) {
+							if ((x != c) && 
+                                (!IS_EMPTY(pos->rgSquare[x].uValue))) {
+								PlaceValue(&p, x, 
+                                           pos->rgSquare[x].uValue, FALSE);
+							}
+						}
+						ASSERT(p.uEmpty - 1 == pos->uEmpty);
+                        g_uSolutions = g_uGuesses = g_uNodes = 0;
+                        if ((TRUE == Solve(&p, 0)) && (g_uSolutions == 1))
+                        {
+							uTries = 0;
+                            memcpy(pos, &p, sizeof(p));
+							if ((g_uGuesses > 5) && 
+                                (g_uNodes > 200) &&
+                                (pos->uEmpty > 55)) {
+                                printf("%u guesses, %u nodes.\n", 
+                                       g_uGuesses, g_uNodes);
+                                return;
+                            }
+                        }
+						else
+						{
+							uTries++;
+							if (uTries > 50) {
+                                usleep(20);
+                                break;
+                            }
+						}
+                    }
+                }
+            }
+        }
+    }
+    while(1);
+}
+
+
+int 
+main(int argc, char *argv[])
+/*++
+
+Routine description:
+
+    Program entry point
+
+Parameters:
+
+    void
+
+Return value:
+
+    int
+
+--*/
+{
+    POSITION pos;
+    char buf[256];
+    char *p;
+    COOR c;
+    
+    InitializePosition(&pos);
+    
+    memset(buf, 0, sizeof(buf));
+
+    if (argc == 1)
+    {
+        printf("Enter board: ");
+        scanf("%255s", buf);
+    }
+    else
+    {
+        if (!strcmp(argv[1], "--create-easy"))
+        {
+            GeneratePuzzle(FALSE, &pos);
+            DumpBoardHtml(&pos);
+            DumpBoardSimple(&pos);
+            exit(0);
+        }
+        else if (!strcmp(argv[1], "--create-hard"))
+        {
+            GeneratePuzzle(TRUE, &pos);
+            DumpBoardHtml(&pos);
+            DumpBoardSimple(&pos);
+            exit(0);
+        }
+        else
+        {
+            strncpy(buf, argv[1], 255);
+        }
+    }
+
+    //
+    // Solve...
+    //
+    p = buf;
+    c = 0;
+    while(*p)
+    {
+        if (!isspace(*p))
+        {
+            if (isdigit(*p) && (*p != '0'))
+            {
+                if (FALSE == PlaceValue(&pos, c, *p - '0', TRUE))
+                {
+                    printf("%u!%u\n",
+                           (unsigned)c, (unsigned)(*p - '0'));
+                    exit(0);
+                }
+            }
+            c++;
+        }
+        p++;
+    }
+
+    g_uSolutions = g_uGuesses = g_uNodes = 0;
+    if (TRUE == Solve(&pos, 0)) {
+        memcpy(&pos, &g_Solution, sizeof(pos));
+        DumpBoardHtml(&pos);
+        printf("%u solutions, %u nodes, %u guesses.\n", 
+               g_uSolutions, g_uNodes, g_uGuesses);
+    }
+    else
+    {
+        DumpBoardHtml(&pos);
+        printf("No solution found...\n");
+    }
+    exit(0);
+}