* 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"
static char sz[10];
ULONG u;
ULONG v;
-
+
memset(&sz, 0, sizeof(sz));
v = 0;
for (u = 1; u < 10; u++)
}
return(sz);
}
-
-void
+
+void
DumpBoard(POSITION *pos)
/*++
--*/
{
COOR c;
-
+
FOREACH_SQUARE(c)
{
if ((c % 9) == 0) printf("\n");
}
else
{
- printf("%-7s ",
+ printf("%-7s ",
ShowPossibilities(pos->rgSquare[c].bvPossibilities));
}
}
-void
+void
DumpBoardHtml(POSITION *pos)
/*++
{
if (pos->rgSquare[c].uValue)
{
- printf("%u:%u\n", (unsigned)c,
+ printf("%u:%u\n", (unsigned)c,
(unsigned)pos->rgSquare[c].uValue);
}
}
DumpBoardSimple(POSITION *pos) {
COOR c;
- FOREACH_SQUARE(c)
+ FOREACH_SQUARE(c)
{
if (pos->rgSquare[c].uValue) {
printf("%u", (unsigned)pos->rgSquare[c].uValue);
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;
-BOOL
+BOOL
PlaceValue(POSITION *pos, COOR sq, ULONG uValue, BOOL fReduce)
/*++
COOR cCol, cRow;
ULONG x;
- //
+ //
// Make sure it's empty
//
if (!IS_EMPTY(pos->rgSquare[sq].uValue))
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;
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)
/*++
}
-ULONG
+ULONG
BitCount(BITV x)
/*++
if ((x & 0x1FF) == 0) return(0);
do
{
- y = 1 << (rand() % 9);
+ y = 1 << (rand() % 9);
if (y & x)
{
return(BitNumber(y));
-BOOL
+BOOL
PositionIsLegal(POSITION *pos, BOOL fReduce)
/*++
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))
}
}
}
-
+
//
// 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))
(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);
//
// 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++)
#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)
{
#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);
#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);
}
}
}
-
+
for (c = 0; c < 9; c++)
{
bvMaskPoss = bvMaskFull = 0;
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)
{
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)
{
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);
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)
{
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);
}
-void
+void
InitializePosition(POSITION *pos)
/*++
pos->rgSquare[c].cRow = ROW(c);
pos->rgSquare[c].cCol = COL(c);
}
-
+
for (c = 0; c < 9; c++)
{
pos->bvRemainingByRow[c] = 0x1FF;
} 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
ULONG u, v;
ULONG uMinPos;
FEWEST temp;
-
+
for (u = 0; u < uLen; u++)
{
uMinPos = u;
uMinPos = v;
}
}
-
+
temp = p[u];
p[u] = p[uMinPos];
p[uMinPos] = temp;
}
-BOOL
+BOOL
Solve(POSITION *pos, ULONG uDepth)
/*++
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");
ASSERT(!sFewest[c].bvPossibilities);
#ifdef DBG
printf("%u: Found inconsistency at square %u.\n", uDepth, c);
- DumpBoard(pos);
+ DumpBoard(pos);
#endif
goto end;
}
//
// Make the guess
- //
+ //
FOREACH_SQUARE(v) {
if (IS_EMPTY(pos->rgSquare[sFewest[v].c].uValue)) {
ASSERT(sFewest[v].uBitCount > 0);
//
// 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) ||
// 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));
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;
uDepth, u, sFewest[v].c);
#endif
fRet = TRUE;
- if (g_uSolutions == 1)
+ if (g_uSolutions == 1)
{
memcpy(pos, &p, sizeof(p));
} else {
}
}
- 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));
}
u++;
}
-
+
//
// Solve the puzzle within these constraints...
//
// 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;
}
- }
+ }
}
}
}
}
-int
+int
main(int argc, char *argv[])
/*++
char buf[256];
char *p;
COOR c;
-
+
InitializePosition(&pos);
-
+
memset(buf, 0, sizeof(buf));
if (argc == 1)
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
projects / puzzle.git / commitdiff