From: Scott Gasch Date: Thu, 2 Jun 2016 15:39:09 +0000 (-0700) Subject: Space work in code, remove tabs etc... X-Git-Url: https://wannabe.guru.org/gitweb/?p=puzzle.git;a=commitdiff_plain;h=HEAD Space work in code, remove tabs etc... --- diff --git a/puzzle.c b/puzzle.c index e8e50c6..e74be62 100644 --- a/puzzle.c +++ b/puzzle.c @@ -12,13 +12,12 @@ * See the License for the specific language governing permissions and * limitations under the License. */ - + #include #include #include #include #include -//#include #include "puzzle.h" @@ -53,7 +52,7 @@ Return value: static char sz[10]; ULONG u; ULONG v; - + memset(&sz, 0, sizeof(sz)); v = 0; for (u = 1; u < 10; u++) @@ -65,11 +64,11 @@ Return value: } return(sz); } - -void + +void DumpBoard(POSITION *pos) /*++ @@ -88,7 +87,7 @@ Return value: --*/ { COOR c; - + FOREACH_SQUARE(c) { if ((c % 9) == 0) printf("\n"); @@ -100,7 +99,7 @@ Return value: } else { - printf("%-7s ", + printf("%-7s ", ShowPossibilities(pos->rgSquare[c].bvPossibilities)); } } @@ -113,7 +112,7 @@ Return value: -void +void DumpBoardHtml(POSITION *pos) /*++ @@ -137,7 +136,7 @@ Return value: { if (pos->rgSquare[c].uValue) { - printf("%u:%u\n", (unsigned)c, + printf("%u:%u\n", (unsigned)c, (unsigned)pos->rgSquare[c].uValue); } } @@ -149,7 +148,7 @@ void DumpBoardSimple(POSITION *pos) { COOR c; - FOREACH_SQUARE(c) + FOREACH_SQUARE(c) { if (pos->rgSquare[c].uValue) { printf("%u", (unsigned)pos->rgSquare[c].uValue); @@ -169,32 +168,32 @@ LiftValue(POSITION *pos, COOR sq) 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; @@ -212,7 +211,7 @@ LiftValue(POSITION *pos, COOR sq) -BOOL +BOOL PlaceValue(POSITION *pos, COOR sq, ULONG uValue, BOOL fReduce) /*++ @@ -237,7 +236,7 @@ Return value: COOR cCol, cRow; ULONG x; - // + // // Make sure it's empty // if (!IS_EMPTY(pos->rgSquare[sq].uValue)) @@ -251,24 +250,24 @@ Return value: 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; @@ -282,14 +281,14 @@ Return value: 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 +ULONG BitNumber(BITV x) /*++ @@ -318,7 +317,7 @@ Return value: } -ULONG +ULONG BitCount(BITV x) /*++ @@ -361,7 +360,7 @@ LegalValue(POSITION *pos, COOR c) if ((x & 0x1FF) == 0) return(0); do { - y = 1 << (rand() % 9); + y = 1 << (rand() % 9); if (y & x) { return(BitNumber(y)); @@ -373,7 +372,7 @@ LegalValue(POSITION *pos, COOR c) -BOOL +BOOL PositionIsLegal(POSITION *pos, BOOL fReduce) /*++ @@ -396,12 +395,12 @@ Return value: BITV bvMaskFull, bvMaskPoss; g_uNodes += 1; -#ifdef DBG +#ifdef DBG printf("Is this legal?\n"); DumpBoardSimple(pos); printf("----------------------------------------------------------\n"); #endif - + FOREACH_SQUARE(c) { if (IS_EMPTY(pos->rgSquare[c].uValue)) @@ -416,12 +415,12 @@ Return value: } } } - + // // 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)) @@ -436,7 +435,7 @@ Return value: (FALSE == PlaceValue(pos, c, BitNumber(x), fReduce))) { #ifdef DBG - printf("Couldn't place forced %u at sq %u\n", + printf("Couldn't place forced %u at sq %u\n", BitNumber(x), c); #endif return(FALSE); @@ -448,7 +447,7 @@ Return value: // // 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++) @@ -469,13 +468,13 @@ Return value: #ifdef DBG printf("%u at square %u is forced...\n", BitNumber(x), cOnly); #endif - if ((TRUE == fReduce) && + if ((TRUE == fReduce) && (FALSE == PlaceValue(pos, cOnly, BitNumber(x), fReduce))) { return(FALSE); } } - + uCount = 0; FOREACH_ROW(sq, c) { @@ -492,7 +491,7 @@ Return value: #ifdef DBG printf("%u at square %u is forced...\n", BitNumber(x), cOnly); #endif - if ((TRUE == fReduce) && + if ((TRUE == fReduce) && (FALSE == PlaceValue(pos, cOnly, BitNumber(x), fReduce))) { return(FALSE); @@ -515,7 +514,7 @@ Return value: #ifdef DBG printf("%u at square %u is forced...\n", BitNumber(x), cOnly); #endif - if ((TRUE == fReduce) && + if ((TRUE == fReduce) && (FALSE == PlaceValue(pos, cOnly, BitNumber(x), fReduce))) { return(FALSE); @@ -523,7 +522,7 @@ Return value: } } } - + for (c = 0; c < 9; c++) { bvMaskPoss = bvMaskFull = 0; @@ -532,7 +531,7 @@ Return value: bvMaskPoss |= pos->rgSquare[sq].bvPossibilities; if (!IS_EMPTY(pos->rgSquare[sq].uValue)) { - ASSERT(pos->rgSquare[sq].bvPossibilities == + ASSERT(pos->rgSquare[sq].bvPossibilities == (1 << pos->rgSquare[sq].uValue)); if (bvMaskFull & pos->rgSquare[sq].bvPossibilities) { @@ -548,19 +547,19 @@ Return value: if (bvMaskPoss != 0x1FF) { #ifdef DBG - printf("Not everything is possible in row %u (%x).\n", + 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 == + ASSERT(pos->rgSquare[sq].bvPossibilities == (1 << pos->rgSquare[sq].uValue)); if (bvMaskFull & pos->rgSquare[sq].bvPossibilities) { @@ -576,7 +575,7 @@ Return value: if (bvMaskPoss != 0x1FF) { #ifdef DBG - printf("Not everything is possible in col %u (%x).\n", + printf("Not everything is possible in col %u (%x).\n", c, bvMaskPoss); #endif return(FALSE); @@ -588,7 +587,7 @@ Return value: bvMaskPoss |= pos->rgSquare[sq].bvPossibilities; if (!IS_EMPTY(pos->rgSquare[sq].uValue)) { - ASSERT(pos->rgSquare[sq].bvPossibilities == + ASSERT(pos->rgSquare[sq].bvPossibilities == (1 << pos->rgSquare[sq].uValue)); if (bvMaskFull & pos->rgSquare[sq].bvPossibilities) { @@ -604,7 +603,7 @@ Return value: if (bvMaskPoss != 0x1FF) { #ifdef DBG - printf("Not everything is possible in group %u (%x).\n", + printf("Not everything is possible in group %u (%x).\n", c, bvMaskPoss); #endif return(FALSE); @@ -614,7 +613,7 @@ Return value: } -void +void InitializePosition(POSITION *pos) /*++ @@ -642,7 +641,7 @@ Return value: pos->rgSquare[c].cRow = ROW(c); pos->rgSquare[c].cCol = COL(c); } - + for (c = 0; c < 9; c++) { pos->bvRemainingByRow[c] = 0x1FF; @@ -660,16 +659,16 @@ typedef struct _FEWEST } FEWEST; -void +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 + 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 @@ -684,7 +683,7 @@ Return value: ULONG u, v; ULONG uMinPos; FEWEST temp; - + for (u = 0; u < uLen; u++) { uMinPos = u; @@ -695,7 +694,7 @@ Return value: uMinPos = v; } } - + temp = p[u]; p[u] = p[uMinPos]; p[uMinPos] = temp; @@ -703,7 +702,7 @@ Return value: } -BOOL +BOOL Solve(POSITION *pos, ULONG uDepth) /*++ @@ -729,10 +728,10 @@ Return value: BOOL fRet = FALSE; g_uNodes++; - + #ifdef DBG - printf("Depth %u (%u node%s):\n", uDepth, - g_uNodes, + printf("Depth %u (%u node%s):\n", uDepth, + g_uNodes, (g_uNodes != 1) ? "" : "s"); DumpBoardSimple(pos); printf("---------------------------------------------------\n"); @@ -751,7 +750,7 @@ Return value: ASSERT(!sFewest[c].bvPossibilities); #ifdef DBG printf("%u: Found inconsistency at square %u.\n", uDepth, c); - DumpBoard(pos); + DumpBoard(pos); #endif goto end; } @@ -760,7 +759,7 @@ Return value: // // Make the guess - // + // FOREACH_SQUARE(v) { if (IS_EMPTY(pos->rgSquare[sFewest[v].c].uValue)) { ASSERT(sFewest[v].uBitCount > 0); @@ -768,7 +767,7 @@ Return value: // // Only make guesses that are legal. Don't "guess" - // the same thing as a prior solution. + // the same thing as a prior solution. // if ((sFewest[v].bvPossibilities & (1 << (u - 1))) && ((g_uSolutions == 0) || @@ -786,7 +785,7 @@ Return value: // Unmake the guess move. // #ifdef DBG - printf("%u: Bad guess (%u at %u), taking it back.\n", + printf("%u: Bad guess (%u at %u), taking it back.\n", uDepth, u, sFewest[v].c); #endif memcpy(pos, &p, sizeof(p)); @@ -806,7 +805,7 @@ Return value: if (pos->rgSquare[sFewest[v].c].bvPossibilities == 0) { #ifdef DBG - printf("%u: Nothing possible at square %u.\n", + printf("%u: Nothing possible at square %u.\n", uDepth, sFewest[v].c); #endif goto end; @@ -824,7 +823,7 @@ Return value: uDepth, u, sFewest[v].c); #endif fRet = TRUE; - if (g_uSolutions == 1) + if (g_uSolutions == 1) { memcpy(pos, &p, sizeof(p)); } else { @@ -836,37 +835,37 @@ Return value: } } - if (0 == pos->uEmpty) + if (0 == pos->uEmpty) { fRet = TRUE; g_uSolutions += 1; #ifdef DBG - printf("%u: Puzzle is solved, solution number %u\n", + printf("%u: Puzzle is solved, solution number %u\n", uDepth, g_uSolutions); DumpBoardSimple(pos); #endif - if (g_uSolutions == 1) + if (g_uSolutions == 1) { memcpy(&g_Solution, pos, sizeof(POSITION)); } goto end; } - + end: return fRet; } -void +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, + 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)); @@ -921,7 +920,7 @@ GeneratePuzzle(BOOL fHard, POSITION *pos) } u++; } - + // // Solve the puzzle within these constraints... // @@ -933,40 +932,40 @@ GeneratePuzzle(BOOL fHard, POSITION *pos) // that is still uniquely solvable but requires // guessing // - uTries = 0; + uTries = 0; while(1) { - c = RANDOM_COOR; + c = RANDOM_COOR; if (!IS_EMPTY(pos->rgSquare[c].uValue)) { - InitializePosition(&p); - FOREACH_SQUARE(x) { - if ((x != c) && + InitializePosition(&p); + FOREACH_SQUARE(x) { + if ((x != c) && (!IS_EMPTY(pos->rgSquare[x].uValue))) { - PlaceValue(&p, x, + PlaceValue(&p, x, pos->rgSquare[x].uValue, FALSE); - } - } - ASSERT(p.uEmpty - 1 == pos->uEmpty); + } + } + ASSERT(p.uEmpty - 1 == pos->uEmpty); g_uSolutions = g_uGuesses = g_uNodes = 0; if ((TRUE == Solve(&p, 0)) && (g_uSolutions == 1)) { - uTries = 0; + uTries = 0; memcpy(pos, &p, sizeof(p)); - if ((g_uGuesses > 5) && + if ((g_uGuesses > 5) && (g_uNodes > 200) && (pos->uEmpty > 55)) { - printf("%u guesses, %u nodes.\n", + printf("%u guesses, %u nodes.\n", g_uGuesses, g_uNodes); return; } } - else - { - uTries++; - if (uTries > 50) { + else + { + uTries++; + if (uTries > 50) { usleep(20); break; } - } + } } } } @@ -976,7 +975,7 @@ GeneratePuzzle(BOOL fHard, POSITION *pos) } -int +int main(int argc, char *argv[]) /*++ @@ -998,9 +997,9 @@ Return value: char buf[256]; char *p; COOR c; - + InitializePosition(&pos); - + memset(buf, 0, sizeof(buf)); if (argc == 1) @@ -1057,7 +1056,7 @@ Return value: if (TRUE == Solve(&pos, 0)) { memcpy(&pos, &g_Solution, sizeof(pos)); DumpBoardHtml(&pos); - printf("%u solutions, %u nodes, %u guesses.\n", + printf("%u solutions, %u nodes, %u guesses.\n", g_uSolutions, g_uNodes, g_uGuesses); } else