From 54539998209c0eeaf09ac850cf99cab1432c3509 Mon Sep 17 00:00:00 2001 From: Scott Gasch Date: Wed, 1 Jun 2016 19:39:59 -0700 Subject: [PATCH 1/1] Initial commit of sudoku puzzle solver. --- GNUmakefile | 30 ++ README | 21 + puzzle.c | 1069 +++++++++++++++++++++++++++++++++++++++++++++++++++ puzzle.h | 173 +++++++++ puzzle.sln | 11 + puzzle.suo | Bin 0 -> 5632 bytes 6 files changed, 1304 insertions(+) create mode 100644 GNUmakefile create mode 100644 README create mode 100644 puzzle.c create mode 100644 puzzle.h create mode 100644 puzzle.sln create mode 100644 puzzle.suo diff --git a/GNUmakefile b/GNUmakefile new file mode 100644 index 0000000..90ab63f --- /dev/null +++ b/GNUmakefile @@ -0,0 +1,30 @@ +CC = gcc +RM = /bin/rm +CFLAGS = -pipe -Wall +HEADERS = puzzle.h +BINARY = puzzle + +ifdef DBG +PROFILE += -g -O -DDEBUG -DDBG +else +PROFILE += -O3 +endif + +# +# ---> .o, not .c! <--- +# +OBJS = puzzle.o + +.SUFFIXES: .c .o + +all: $(BINARY) + +$(BINARY): $(OBJS) + $(CC) $(PROFILE) -o $(BINARY) -Wall $(OBJS) + +%.o: %.c $(HEADERS) + $(CC) $(CFLAGS) $(PROFILE) -c $< -o $@ + +clean: + $(RM) -f *.core *~ *.gmon \#*\# $(OBJS) $(BINARY) + diff --git a/README b/README new file mode 100644 index 0000000..6c8ce5c --- /dev/null +++ b/README @@ -0,0 +1,21 @@ + + This is a simple text-mode sudoku puzzle solver. Sudoku is a + number game that has been published in the Sunday newspapers in + some cities. For more information see http://www.sudoku.com or + http://en.wikipedia.org/wiki/Sudoku. You can use this program to + enter a puzzle and have it search for the solution. + +/* 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. + */ 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 +#include +#include +#include +#include +//#include + +#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); +} diff --git a/puzzle.h b/puzzle.h new file mode 100644 index 0000000..161d005 --- /dev/null +++ b/puzzle.h @@ -0,0 +1,173 @@ +/* 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. + */ + +#ifndef _PUZZLE_H_ +#define _PUZZLE_H_ + +#include +#include + +typedef unsigned long ULONG; +typedef unsigned long BITV; +typedef unsigned long COOR; +#define RANDOM_COOR (rand() % 81) +typedef unsigned long BOOL; + +#if 0 +#define ASSERT(x) if (x) \ + { ; } \ + else \ + { _assert(__FILE__, __LINE__); } +#define VERIFY(x) ASSERT(x) +#else +#define ASSERT(x) ; +#define VERIFY(x) x; +#endif // DEBUG + +#ifdef PERF_COUNTERS +#define INC(x) ((x) += 1) +#else +#define INC(x) +#endif + +typedef struct _SQUARE +{ + BITV bvPossibilities; + ULONG uValue; + ULONG cCol; + ULONG cRow; + ULONG cGroup; +} SQUARE; + +// +// 0 1 2 3 4 5 6 7 8 +// 9 10 11 12 13 14 15 16 17 +// 18 19 20 21 22 23 24 25 26 +// +// 27 28 29 30 31 32 33 34 35 +// 36 37 38 39 40 41 42 43 44 +// 45 46 47 48 49 50 51 52 53 +// +// 54 55 56 57 58 59 60 61 62 +// 63 64 65 66 67 68 69 70 71 +// 72 73 74 75 76 77 78 79 80 +// +COOR g_cGroup[81] = { + 0, 0, 0, 1, 1, 1, 2, 2, 2, + 0, 0, 0, 1, 1, 1, 2, 2, 2, + 0, 0, 0, 1, 1, 1, 2, 2, 2, + 3, 3, 3, 4, 4, 4, 5, 5, 5, + 3, 3, 3, 4, 4, 4, 5, 5, 5, + 3, 3, 3, 4, 4, 4, 5, 5, 5, + 6, 6, 6, 7, 7, 7, 8, 8, 8, + 6, 6, 6, 7, 7, 7, 8, 8, 8, + 6, 6, 6, 7, 7, 7, 8, 8, 8 +}; + +COOR g_cSquareByGroup[9][9] = +{ + { 0, 1, 2, 9, 10, 11, 18, 19, 20 }, + { 3, 4, 5, 12, 13, 14, 21, 22, 23 }, + { 6, 7, 8, 15, 16, 17, 24, 25, 26 }, + { 27, 28, 29, 36, 37, 38, 45, 46, 47 }, + { 30, 31, 32, 39, 40, 41, 48, 49, 50 }, + { 33, 34, 35, 42, 43, 44, 51, 52, 53 }, + { 54, 55, 56, 63, 64, 65, 72, 73, 74 }, + { 57, 58, 59, 66, 67, 68, 75, 76, 77 }, + { 60, 61, 62, 69, 70, 71, 78, 79, 80 } +}; + +#define IS_EMPTY(x) ((x) == 0) +#define COL(c) ((c) % 9) +#define FIRST_OF_COL(c) (c) +#define ROW(c) ((c) / 9) +#define FIRST_OF_ROW(c) ((c) * 9) +#define FOREACH_ROW(c, r) \ + for((c) = FIRST_OF_ROW(r); (c) < FIRST_OF_ROW((r) + 1); (c)++) +#define FOREACH_COL(c, f) \ + for((c) = FIRST_OF_COL(f); (c) < 81; (c) += 9) +#define FOREACH_GROUP(c, g, x) \ + for((x) = 0, (c) = g_cSquareByGroup[(g)][(x)]; \ + (x) < 9; \ + (x)++, (c) = g_cSquareByGroup[(g)][(x)]) +#define FOREACH_SQUARE(x) \ + for((x) = 0; (x) < 81; (x)++) +COOR g_cGroupsByRow[9][3] = +{ + { 0, 1, 2 }, + { 0, 1, 2 }, + { 0, 1, 2 }, + { 3, 4, 5 }, + { 3, 4, 5 }, + { 3, 4, 5 }, + { 6, 7, 8 }, + { 6, 7, 8 }, + { 6, 7, 8 } +}; + +COOR g_cRowsByGroup[9][3] = +{ + { 0, 1, 2 }, + { 0, 1, 2 }, + { 0, 1, 2 }, + { 3, 4, 5 }, + { 3, 4, 5 }, + { 3, 4, 5 }, + { 6, 7, 8 }, + { 6, 7, 8 }, + { 6, 7, 8 } +}; + +COOR g_cGroupsByCol[9][3] = +{ + { 0, 3, 6 }, + { 0, 3, 6 }, + { 0, 3, 6 }, + { 1, 4, 7 }, + { 1, 4, 7 }, + { 1, 4, 7 }, + { 2, 5, 8 }, + { 2, 5, 8 }, + { 2, 5, 8 } +}; + +COOR g_cColsByGroup[9][3] = +{ + { 0, 1, 2 }, + { 3, 4, 5 }, + { 6, 7, 8 }, + { 0, 1, 2 }, + { 3, 4, 5 }, + { 6, 7, 8 }, + { 0, 1, 2 }, + { 3, 4, 5 }, + { 6, 7, 8 } +}; + +typedef struct _POSITION +{ + SQUARE rgSquare[81]; + BITV bvRemainingByGroup[9]; + BITV bvRemainingByCol[9]; + BITV bvRemainingByRow[9]; + ULONG uEmpty; +} POSITION; + +#define ONE_BIT(x) (((x) & (x - 1)) == 0) + +#define TRUE (1) +#define FALSE (0) + +#endif /* _PUZZLE_H_ */ diff --git a/puzzle.sln b/puzzle.sln new file mode 100644 index 0000000..ff0f832 --- /dev/null +++ b/puzzle.sln @@ -0,0 +1,11 @@ +Microsoft Visual Studio Solution File, Format Version 8.00 +Global + GlobalSection(SolutionConfiguration) = preSolution + EndGlobalSection + GlobalSection(ProjectConfiguration) = postSolution + EndGlobalSection + GlobalSection(ExtensibilityGlobals) = postSolution + EndGlobalSection + GlobalSection(ExtensibilityAddIns) = postSolution + EndGlobalSection +EndGlobal diff --git a/puzzle.suo b/puzzle.suo new file mode 100644 index 0000000000000000000000000000000000000000..a46875d8dd4f06b4a89bec7f887533be6f7380db GIT binary patch literal 5632 zcmeHLO-vI}5S|uMP((o?>VXjB-$6(bP(&q>789aHwEP&u1xi7sP(n)-|KiDmF?uo4 zn=u}ZiQWmui;)H0lSe#yk@|ga->Y>k+bxZWBuumW-oBstW@cyR&Gy4w*_S6T zcYGBawMc<1CW~cl+PDXOUWzu0c+uhWVltVu21U?ar4?j>pOAHpeusr<`M%fTD$--c zx?Mpkt%{n11Kt!(G5H!y3j5 z<;b#JO*3b5Jt+XR0hyFx{D|8Nc@h$q3wX+g&HdF{f9m5FpLu&LH-nhF?N@pZ;5%K9 zYeU-F(zL#PuX&~{tMva{;9ybJ{nrE2frtKA5AOQk-NviUiN5=@MZGgS#zH>C{gt@R zOSAOJI3npPeo;hEpDVWc;u{c^)9~O|a#&ey81dXMqlnQH$S#yA4yl6ZhgH^#Bi{|F z+}oqF&m>kyu{wmYNg2dg3{SPvfvnht-U0F9R}UUN;BW{n`6STB(T35A+{;l0d;Vz! zrwHU2fh}W@fMX0kg42wI=Wejw%Vyz+3}hG!;oMcxYU2l5nW^t@QKZw#WpKA z7O>t~D*y6LjluRIU{5NmMjTlJU!6a!ncU*jUeg|ntzG}$_*3wl0Z0+ehM%&%Tl^Am zH2FV&ALMxzg{(u$1C1w|=iEK=UrA)i=`Jfcn*6Uxo~L%oXUxv)Uq0LYFNoM1h1anT z?A5Ullgmp+;ePl(PGg33~ zS(^}>q}e()n=nh6NdfQ;Bhp7T=X9MrF&BpooHCJ5=N}8*9X@L{<_nS&zNtk6uuKA1 zCaQ)0tjAcRxz(Tbs?lGU;e(3zHu+Rg?ggu4a<4b_ssG~StoQAySuZnIvEDZ?*C2YG z1i0U$bD83yZ||QqlrPLY|7_;yALX_=K2nw->>pKD=E>I&U*P#Sp87TrIfj2DNJpdr zcMT1n2q+;-J3{j_3njrjyC1#sKCbwYK^(O^)9p-krcw7}=jLenJcvrPN|Q874HRm` zQQw4K9c_yPzXo$BFn%089{zq@4H!9$pAYl(*l|Oy%TaY;MG+kBFdjoVE-e_(R2HQd zNwqxZqOi8{aVyS-;Pt~8W&L7iGV6%=PsN^F|DzxHG`rI{<1WDiSSu|R;P)T%8FPwTe10Qo_>_+`4~|0?W?p7PD-!rB zor(Cw<$2>4pJzYoB~mwBhN%6hc_O&}%(_mMpS6GIGTwi>{^mQ|e1C`V