/* cc -g -O hexagons.c -lm -o hex 2>&1 | more nohup nice ./hex -x 2 -y 2 > hex.out 2>&1 # # Copyright (c) 2021 - 2022 David Albert Bagley, bagleyd AT verizon.net # # All Rights Reserved # # Permission to use, copy, modify, and distribute this software and # its documentation for any purpose and without fee is hereby granted, # provided that the above copyright notice appear in all copies and # that both that copyright notice and this permission notice appear in # supporting documentation, and that the name of the author not be # used in advertising or publicity pertaining to distribution of the # software without specific, written prior permission. # # This program is distributed in the hope that it will be "usable", # but WITHOUT ANY WARRANTY; without even the implied warranty of # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. # # NOTE: you may THRASH your hard drive if you run out of RAM... # IF YOU HAVE LOTS OF DISK ACTIVITY AFTER EXECUTING THIS, TERMINATE IT! https://kconrad.math.uconn.edu/blurbs/grouptheory/15puzzle.pdf DO NOT try for order 19 i.e. 3x3 (aka. 17 puzzle) -x 3 -y 3 . DO NOT even try for simpler orders like 14 i.e. -x 2 -y 3, by the 20th move it will eat all memory and freeze 16 Gig system (or order 16 -x 1 -y 4 (with corners this is on cusp) or also order 16 -x 5 -y 2). Highest I recommend (if you have this much memory (less if you do not)) is to solve an order 10 puzzle that is: -x 3 -y 2 . On the cusp is order 13 -x 4 -y 2 . I get solutions for some starting positions but cannot reach furthest solution without it thrashing around the 22nd move. For corners, it just makes it with 84 moves and furthest is 85. -x 1 -y 3 -> offset 12, mirror 12, reverse 28, reverse offset 27, furthest 31 -x 2 -y 2 -> offset 7, mirror 12, reverse 12, reverse offset 15, furthest 15 -x 3 -y 2 -> offset 17, mirror 32, reverse 24, reverse offset 31, furthest 32 -c -x 1 -y 3 -> 18 moves -c -x 1 -y 4 -> offset 48, >52 for others -c -x 2 -y 2 -> 16 moves -c -x 2 -y 3 -> offset 46, >51 for others -c -x 3 -y 2 -> offset 50, mirror 47, reverse 25, reverse offset 36, furthest 78 -c -x 4 -y 2 -> offset 84, mirror 87, reverse 53, reverse offset 66, furthest 102 Option piecemeal -p may be able to extend this to find a good but probably not best solution. -p -x 2 -y 3 -i 0 -> (offset) 27 moves -p -x 3 -y 3 -i 0 -> (offset) 44 moves -p -c -x 3 -y 3 -i 0 -> (offset) 126 moves (251 Puzzle Party solution) -p -c -x 3 -y 3 -i 1 -> (mirror) 149 moves head /proc/meminfo MemTotal: 16058756 kB head /proc/cpuinfo cpu MHz */ /* Converted from cubes.c */ /* This program calculates the hexagons puzzle problem. */ /* lxm (usually l and m = 3) tiles to be exchanged . */ /* Input: */ /* # of tiles */ /* # of nodes you expect it to take to search for a solution. */ /* Start and Final positions hard coded */ /* Output: */ /* The optimum route to exchange the tiles, but must obey rule */ /* no tile can go through another tile. */ /* As it stands now a full solution will not be printed if number of */ /* greater than X. */ #include #include #include #include #define FILE_NAME_LENGTH 1024 #define FALSE 0 #define TRUE 1 #define TR 0 #define RIGHT 1 #define BR 2 #define BL 3 #define LEFT 4 #define TL 5 #define COORD 6 #define TRBL 0 #define TLBR 1 #define ROW 2 #define ROW_TYPES 3 #define LOW 0 #define HIGH 1 #define POSSIBILITIES COORD /* maximum number of possible moves */ #define AREA (sizeY * sizeY + (sizeX - 1) * (sizeY * 2 - 1)) #define CENTER ((AREA - 1) >> 1) #define BLANK 0 #define BLANK2 (AREA - 1) #define CHAINS 3 /* for deleting nodes from hash table */ #define ARRAYTWEAKS 20 /* if <= tiles it will consult array for tweaks */ #define FREQBITS 22 /* sets frequency of what node & move its at now, for feedback */ #define NOFULLSOLUTION 10 /* lower this if you do not have the memory */ #define MINIMUM_MOVES 0 #define FURTHER 1 #define MODES 2 #define OFFSET 0 #define MIRROR 1 #define REVERSE 2 #define OFFSET_REVERSE 3 #define STARTS 4 int corners = FALSE; int debug = 0; int mode = MINIMUM_MOVES; int initial = OFFSET; int arch = 8; #define OPP_DIR(dir) ((dir + 3) % 6) #define OPP_BLANK(blank) ((blank == BLANK) ? BLANK2 : BLANK) #define MAX(i, j) (((i) > (j)) ? (i) : (j)) #define MIN(i, j) (((i) < (j)) ? (i) : (j)) #define CEIL(i) ((int) (i + 0.999999)) /* rough ceiling */ /* min bits needed to store a move */ #define MINBITS() CEIL(log2(AREA)) /* max tiles to store in a unit of memory */ #define MAXNUMINUNIT() ((int) (arch / MINBITS())) /* min units to store all tiles */ #define MINUNITS() CEIL((double) AREA / MAXNUMINUNIT()) #ifdef ARCH128 #include using namespace std; const int len = 128; /* does not work past ? due to to_ulong() conversion, also slow */ #define TO_LONG(x) (x).to_ulong() #define LONG bitset #else #define TO_LONG(x) (x) #define LONG unsigned long long #endif #define LOOKUP(x) ((units>1)?(TO_LONG(*x+((*(x+1))*253))%hashSize):\ (TO_LONG(*x)%hashSize)) static int tiles; static int size, hashSize; static int bits, units, numInUnit, freqmask, loop; static LONG bitmask, inputSize; #define numTile(l) ((l >> 1) + ((l & 1) ? tiles : 0)) #define tileChar(l) ((l == BLANK) ? '-' : ((corners && l == BLANK2) ? '+' : ((l < 10) ? l + '0' : l - 10 + 'a'))) #define tileDigit(l) (((!corners && l == BLANK) || (corners && l == BLANK2)) ? 0 : ((l == BLANK) ? -1 : l)) #define SETBIT(t, p) (((LONG) (p)) << (bits * (t % numInUnit))) #define setStart(t, p) startTiles[t / numInUnit] |= SETBIT(t, p) #define setFinish(t, p) finishTiles[t / numInUnit] |= SETBIT(t, p) #define setTile(t, p) shrunkPositionOfTile[t / numInUnit] |= SETBIT(t, p) #define BITMASK ((1 << bits) - 1) #define getStart(t) (((startTiles[t / numInUnit]) >> (bits * (t % numInUnit))) & BITMASK) #define getFinish(t) (((finishTiles[t / numInUnit]) >> (bits * (t % numInUnit))) & BITMASK) #define getTile(t) (((shrunkPositionOfTile[t / numInUnit]) >> (bits * (t % numInUnit))) & BITMASK) /* move counts are for OFFSET */ /* ones marked 128 are currently beyond reach for 16G */ static int moves1d[MODES][ARRAYTWEAKS] = { /* 1x1 -15x1 */ {0, 0, 1, 2, 3, 4, 5, 6, 7, 12, 9, 11, 12, 13, 14, 15, 16, 17, 18, 19}, {0, 1, 2, 3, 7, 5, 6, 7, 8, 18, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19}}; static int moves2dx2[MODES][ARRAYTWEAKS / 2 - 1] = { /* 2x2 - 8x2 */ {6, 16, 20, 26, 42, 128, 128, 128, 128}, {6, 21, 36, 55, 80, 128, 128, 128, 128}}; static int moves2dx3[MODES][ARRAYTWEAKS / 3 - 2] = { /* 3x3 */ {128, 128}, {128, 128}}; static int moves[MODES][ARRAYTWEAKS] = { {0, 1, 2, 3, 4, 5, 6, /*12 18*/ 20, 28, 26, 10, /*20 32*/ 42, 12, 128, 128, 128, 128, 128, 128, 128}, {0, 1, 2, 6, 4, 21, 6, /*15 19*/ 36, 31, 55, 10, /*36 40*/ 80, 12, 128, 128, 128, 128, 128, 128, 128}}; static int hashSizes[ARRAYTWEAKS] = {31, 253, 1021, 65533, 131071, 262141, 1048573, 8388607, 259000001, 259000001, 259000001, 259000001, 259000001, 259000001, 259000001, 259000001, 259000001, 259000001, 259000001, 259000001}; /* These values are maximum for FURTHER, as may be more than one way to get there */ static int moveSizes[ARRAYTWEAKS] = { 5, 5, 5, 5, 902, 902, 902, 902, 38495, 443553, 83000000, 83000000, 83000000, 83000000, 83000000, 83000000, 83000000, 83000000, 83000000, 83000000}; static long long minSizes[ARRAYTWEAKS] = { /* nodes */ 24, 24, 24, 24, 5040, 5040, 5040, 5040, 362880, 3628800, 2675020213LL, 2675020213LL, 2675020213LL, 2675020213LL, 2675020213LL, 2675020213LL, 2675020213LL, 2675020213LL, 2675020213LL, 2675020213LL}; /* corners move size 35117437, nodes 513021125 */ static LONG *nodeLog = NULL; static char *backPoss = NULL; static int *move = NULL, *backPath = NULL; static int newNode = 0, currNode = 0; /* hashless, debug level 2 check */ /* slow but good to check the hashes are working */ static int newBottom = 0; static int unitMem; typedef struct _hashtype { int node; struct _hashtype *next; } hashtype; static hashtype **hash; static hashtype *chain[CHAINS]; static int hashNewIndex; static long long c; static int sizeX = 0, sizeY = 0; static char *tileOfPosition = NULL; /* easier to see */ static char *startPosition = NULL, *finishPosition = NULL; static char *positionOfTile = NULL; static int startSpacePosition, finishSpacePosition; static int startSpacePosition2, finishSpacePosition2; static LONG *startTiles = NULL, *finishTiles = NULL; static LONG *shrunkPositionOfTile = NULL; static int blanks = 1; static int frozenRows = 0, frozenTrBl = 0, frozenTlBr = 0; static char startFile[FILE_NAME_LENGTH] = ""; static char finishFile[FILE_NAME_LENGTH] = ""; static int piecemeal = 0; static int redirect = 0; static LONG intMask = 0; static LONG *rowMask = NULL; static LONG *trblMask = NULL; static LONG *tlbrMask = NULL; /* may not be a good idea */ static int spaceRow[ROW_TYPES]; static int space2Row[ROW_TYPES]; static int spacePosition[2] = {BLANK, 1}; static int SQRT(const int i) { int j = 0; while (j * j <= i) j++; return (j - 1); } static void swapChar(char *a, char *b) { char c; c = *b; *b = *a; *a = c; } static void swapInt(int *a, int *b) { int c; c = *b; *b = *a; *a = c; } #ifdef DEBUG static int positionInRow(int position, int posRow) { /* Untested */ return (posRow <= sizeY - 1) ? (position - sizeX * posRow - ((posRow * (posRow - 1)) >> 1)) : (position - sizeY * (posRow - sizeY) - ((4 * sizeX * (sizeX - 1)) >> 1) + (((2 * sizeX - posRow - 2) * (2 * sizeX - posRow - 1)) >> 1) - 1); } #endif static int positionFromRow(int rowPosition, int posRow) { return (posRow <= sizeY - 1) ? (sizeX * posRow + ((posRow * (posRow - 1)) >> 1) + rowPosition) : (sizeY * (2 * posRow - sizeY + 1) - sizeX * (posRow + 1) + 4 * ((sizeX * (sizeX - 1)) >> 1) - (((2 * sizeX - posRow - 2) * (2 * sizeX - posRow - 1)) >> 1) + 1 + rowPosition); } static int toPosition(int row, int trbl) { return ((row < sizeY) ? positionFromRow(trbl, row) : positionFromRow(trbl, row) - row + sizeY - 1); } int toRow(const int pos) { return (pos <= CENTER) ? ((1 + SQRT(1 + 8 * (pos + ((sizeX * (sizeX - 1)) >> 1)))) >> 1) - sizeX : sizeX + 2 * sizeY - 2 - (1 + SQRT(1 + 8 * (AREA - 1 + ((sizeX * (sizeX - 1)) >> 1) - pos))) / 2; } /* Passing row so there is no sqrt calculation again */ int toTrBl(const int pos, const int posRow) { return (pos <= CENTER) ? (pos + ((sizeX * (sizeX - 1)) >> 1)) - (((posRow + sizeX) * (posRow + sizeX - 1)) >> 1) : sizeY + sizeX - 2 - (AREA - 1 + ((sizeX * (sizeX - 1)) >> 1) - pos - (2 * sizeY + sizeX - posRow - 2) * (2 * sizeY + sizeX - posRow - 3) / 2); } int toTlBr(const int pos, const int posRow) { return (pos <= CENTER) ? -(1 + pos + ((sizeX * (sizeX - 1)) >> 1)) + (((posRow + sizeX + 1) * (posRow + sizeX)) >> 1) : sizeY + sizeX - 1 + (AREA - 1 + ((sizeX * (sizeX - 1)) >> 1) - pos - (((2 * sizeY + sizeX - posRow - 1) * (2 * sizeY + sizeX - posRow - 2)) >> 1)); } static char * dirToString(int i) { switch (i) { case TR: return "TR"; case RIGHT: return "RIGHT"; case BR: return "BR"; case BL: return "BL"; case LEFT: return "LEFT"; case TL: return "TL"; default: return "?"; } } static int tileNFrom(int pos, int n, int rowType, int direction) { int offset = (direction == HIGH) ? -n : n; if (rowType == ROW) return (pos + offset); else { int row = toRow(pos); int trbl = toTrBl(pos, row); if (rowType == TRBL) return toPosition(row + offset, trbl); else /*if (rowType == TLBR)*/ return toPosition(row + offset, trbl + offset); } } static void freeHash(int index) { hashtype **oldChain = &(chain[index]); hashtype *ctemp = *oldChain; hashtype **oldHashPt; hashtype *htemp, *temp; while (ctemp) { oldHashPt = &(hash[LOOKUP(&nodeLog[ctemp->node * units])]); htemp = *oldHashPt; if ((*oldHashPt)->node == ctemp->node) { *oldHashPt = htemp->next; (void) free((void *) htemp); /* fnc++; */ } else { while (htemp->next->node != ctemp->node) htemp = htemp->next; temp = htemp->next; htemp->next = temp->next; (void) free((void *) temp); /* fc++; */ } *oldChain = (*oldChain)->next; (void) free((void *) ctemp); ctemp = *oldChain; } } #ifdef DEBUG static void printHash() { int i; for (i = 0; i < hashSize; i++) { hashtype *temp = hash[i]; while (temp != NULL) { (void) printf("%d: %d %lld\n", i, temp->node, nodeLog[temp->node * units]); temp = temp->next; } } } #endif static int inHash() { LONG *psPOT = shrunkPositionOfTile; LONG *tempsPOT, *pnodeLog; hashtype *temp; int i; temp = hash[LOOKUP(psPOT)]; /*printf("temp %lld\n", temp);*/ while (temp != NULL) { tempsPOT = psPOT; pnodeLog = &(nodeLog[temp->node * units]); for (i = 0; i < units; i++) { /*printf("in here %lld %lld", *pnodeLog, *tempsPOT);*/ if (*pnodeLog != *tempsPOT) goto HASHCONTINUE; /*printf("in hash %lld %lld", *pnodeLog, *tempsPOT);*/ pnodeLog++; tempsPOT++; } return TRUE; HASHCONTINUE: temp = temp->next; } return FALSE; } static void memoryError(const char * string) { (void) fprintf(stderr, "Not enough memory for %s.\n", string); (void) fprintf(stderr, "Try a smaller number of nodes with -n.\n"); (void) fprintf(stderr, "Exiting\n"); exit(1); } static void printTilesDigit(char * inTileOfPosition) { int position; char *ptOP = inTileOfPosition; int rowPos = 0, r = 0, rp, p, length = 0; for (position = 0; position < AREA; position++) { if (rowPos == 0) { if (position < CENTER) { length = sizeX + r; for (rp = 0; rp < sizeY - r - 1; rp++) (void) fprintf(stderr, " "); } else { length = 2 * sizeY + sizeX - r - 2; for (rp = 0; rp < r - sizeY + 1; rp++) (void) fprintf(stderr, " "); } } (void) fprintf(stderr, "%2d", tileDigit(*ptOP)); if (rowPos == length - 1) { r++; rowPos = 0; (void) fprintf(stderr, "\n"); } else { (void) fprintf(stderr, " "); rowPos++; } ptOP++; } } static void printTiles(char * inTileOfPosition) { int position; char *ptOP = inTileOfPosition; int rowPos = 0, r = 0, rp, p, length = 0; for (position = 0; position < AREA; position++) { if (rowPos == 0) { if (position < CENTER) { length = sizeX + r; for (rp = 0; rp < sizeY - r - 1; rp++) (void) printf(" "); } else { length = 2 * sizeY + sizeX - r - 2; for (rp = 0; rp < r - sizeY + 1; rp++) (void) printf(" "); } } (void) printf("%c", tileChar(*ptOP)); if (rowPos == length - 1) { r++; rowPos = 0; (void) printf("\n"); } else { (void) printf(" "); rowPos++; } ptOP++; } } static void printPositions(char * inPositionOfTile) { int tile; char *ppOT = inPositionOfTile; char *inTileOfPosition; /*printf("print Positions\n");*/ if (!(inTileOfPosition = (char *) calloc(AREA, sizeof (char)))) { memoryError("printPositions"); } for (tile = 0; tile < AREA; tile++) inTileOfPosition[inPositionOfTile[tile]] = tile; printTiles(inTileOfPosition); if (inTileOfPosition) (void) free((void *) inTileOfPosition); } static void putInHash(int index, int node) { hashtype **oldHashPt = &(hash[LOOKUP(&nodeLog[node * units])]); hashtype **oldChain = &(chain[index]); hashtype *htemp = *oldHashPt; hashtype *ctemp = *oldChain; if (!(htemp = (hashtype *) malloc(sizeof (hashtype)))) { memoryError("adding to hash table"); } htemp->node = node; if (*oldHashPt == NULL) { *oldHashPt = htemp; htemp->next = NULL; /* nc++; */ } else { htemp->next = *oldHashPt; *oldHashPt = htemp; c++; } if (!(ctemp = (hashtype *) malloc(sizeof (hashtype)))) { memoryError("adding to chain"); } ctemp->node = node; ctemp->next = *oldChain; *oldChain = ctemp; } static void putCurrent(int node) { LONG *pnodeLog = &(nodeLog[node * units]); LONG *psPOT = shrunkPositionOfTile; int j; /*char *ppOT = positionOfTile; int i, j, shift, n = 0; for (j = 0; j < units; j++) shrunkPositionOfTile[j] = 0; for (i = 0; i < AREA; i++) setTile(i, positionOfTile[i]); for (;;) { shift = 0; *psPOT = 0; for (j = 0; j < numInUnit; j++) { *psPOT |= (((LONG) *ppOT) << shift); shift += bits; ppOT++; n++; if (n >= AREA) { *pnodeLog = *psPOT; return; } }*/ for (j = 0; j < units; j++) { *pnodeLog = *psPOT; psPOT++; pnodeLog++; } } static void calculateRows(int fromPosition) { int posRow = toRow(fromPosition); spaceRow[ROW] = posRow; spaceRow[TRBL] = toTrBl(fromPosition, posRow); spaceRow[TLBR] = toTlBr(fromPosition, posRow); } static void calculateRows2(int fromPosition) { int posRow = toRow(fromPosition); space2Row[ROW] = posRow; space2Row[TRBL] = toTrBl(fromPosition, posRow); space2Row[TLBR] = toTlBr(fromPosition, posRow); } static void getCurrent(int node) { int i, j, shift, n = 0; LONG *pnodeLog = &(nodeLog[node * units]); LONG *psPOT = shrunkPositionOfTile; char *ptOP = tileOfPosition; char value; for (;;) { shift = 0; *psPOT = *pnodeLog; for (j = 0; j < numInUnit; j++) { value = (char) TO_LONG((((LONG) *psPOT) >> shift) & bitmask); *ptOP = value; /*tileOfPosition[n] = value;*/ positionOfTile[value] = n; shift += bits; ptOP++; n++; if (n >= AREA) { return; } } pnodeLog++; psPOT++; } } static char decideSwap() { if (!corners) { return FALSE; } else if (initial == MIRROR) { return TRUE; } else if (initial == OFFSET) { return FALSE; } else if (initial == REVERSE || initial == OFFSET_REVERSE) { return ((sizeX & 1) == 0 && (sizeY & 1) == 0); } } static void setStartPosition() { int i, j, switch1, switch2; if (!corners && sizeY == 1) { startSpacePosition = 0; startPosition[startSpacePosition] = 0; for (i = 1; i < sizeX; i++) startPosition[i] = i; return; } if (corners && sizeX == 1 && sizeY == 3) { startSpacePosition = 0; startPosition[startSpacePosition] = 0; startSpacePosition2 = 1; startPosition[startSpacePosition2] = AREA - 1; startPosition[2] = 1; startPosition[3] = 6; startPosition[4] = 5; startPosition[5] = 4; startPosition[6] = 3; startPosition[7] = 2; startPosition[8] = 7; return; } if (corners && sizeX == 2 && sizeY == 2) { startSpacePosition = 0; startPosition[startSpacePosition] = 0; startSpacePosition2 = 1; startPosition[startSpacePosition2] = AREA - 1; startPosition[2] = 5; startPosition[3] = 4; startPosition[4] = 3; startPosition[5] = 2; startPosition[6] = 1; return; } if (initial == MIRROR) { if (corners && sizeX == 1) { for (i = 0; i < AREA; i++) { calculateRows(i); j = toPosition(spaceRow[ROW], spaceRow[TLBR]) + 1; startPosition[i] = j; if (j == AREA - 4) switch1 = i; else if (j == AREA - 3) switch2 = i; } /* FIXME */ startSpacePosition = AREA - 1; startPosition[startSpacePosition] = AREA - 1; startSpacePosition2 = AREA - 3; startPosition[startSpacePosition2] = 0; } else { for (i = 0; i < AREA; i++) { calculateRows(i); j = toPosition(spaceRow[ROW], spaceRow[TLBR]) + 1; startPosition[i] = j; if (j == AREA) { startSpacePosition = i; startPosition[startSpacePosition] = 0; } if (corners && j == AREA - 1) { startSpacePosition2 = i; startPosition[startSpacePosition2] = AREA - 1; } if (j == AREA - 3) switch1 = i; else if (j == AREA - 2) switch2 = i; } } if (decideSwap()) { printf("need swap\n"); i = startPosition[switch1]; startPosition[switch1] = startPosition[switch2]; startPosition[switch2] = i; } } else if (initial == OFFSET) { for (i = 0; i < AREA; i++) { j = i - ((corners) ? 1 : 0); startPosition[i] = j; if (j == AREA - 3 - ((sizeX == 1) ? 1 : 0)) switch1 = i; else if (j == AREA - 2 - ((sizeX == 1) ? 1 : 0)) switch2 = i; } startSpacePosition = 0; startPosition[startSpacePosition] = 0; if (corners) { startSpacePosition2 = 1; startPosition[startSpacePosition2] = AREA - 1; } if (decideSwap()) { printf("need swap\n"); i = startPosition[switch1]; startPosition[switch1] = startPosition[switch2]; startPosition[switch2] = i; } } else if (initial == REVERSE) { if (corners && sizeX == 1) { for (i = 0; i < AREA - 2; i++) { j = AREA - i - 2; if (i == 0) startPosition[0] = 1; else if (i == AREA - 3) startPosition[AREA - 3] = AREA - 2; else startPosition[i] = j; if (j == AREA - 4) switch1 = i; else if (j == AREA - 3) switch2 = i; } } else for (i = 0; i < AREA; i++) { j = AREA - i - 1 - ((corners) ? 1 : 0); startPosition[i] = j; if (j == AREA - 3) switch1 = i; else if (j == AREA - 2) switch2 = i; } if (corners) { startSpacePosition = AREA - 2; startPosition[startSpacePosition] = 0; startSpacePosition2 = AREA - 1; startPosition[startSpacePosition2] = AREA - 1; } else { startSpacePosition = AREA - 1; startPosition[startSpacePosition] = 0; } if (decideSwap()) { printf("need swap\n"); i = startPosition[switch1]; startPosition[switch1] = startPosition[switch2]; startPosition[switch2] = i; } } else if (initial == OFFSET_REVERSE) { if (corners && sizeX == 1) { for (i = 0; i < AREA; i++) { j = AREA - i - 1; if (i == 2) startPosition[2] = 1; else if (i == AREA - 1) startPosition[AREA - 1] = AREA - 2; else startPosition[i] = j + 1; if (j == AREA - 4) switch1 = i; else if (j == AREA - 3) switch2 = i; } } else for (i = 0; i < AREA; i++) { j = AREA - i; startPosition[i] = j; if (j == AREA - 3) switch1 = i; else if (j == AREA - 2) switch2 = i; } startSpacePosition = 0; startPosition[startSpacePosition] = 0; if (corners) { startSpacePosition2 = 1; startPosition[startSpacePosition2] = AREA - 1; } if (decideSwap()) { printf("need swap\n"); i = startPosition[switch1]; i = startPosition[switch1]; startPosition[switch1] = startPosition[switch2]; startPosition[switch2] = i; } } } static void setFinishPosition() { int i; for (i = 0; i < AREA - 1; i++) finishPosition[i] = i + 1; if (corners) { finishSpacePosition = AREA - 2; finishPosition[finishSpacePosition] = 0; finishSpacePosition2 = AREA - 1; finishPosition[finishSpacePosition2] = AREA - 1; } else { finishSpacePosition = AREA - 1; finishPosition[finishSpacePosition] = 0; } } static char checkSolved() { int i; for (i = 1; i < AREA - ((corners) ? 1 : 0); i++) { if (tileOfPosition[i - 1] != i) return FALSE; } return TRUE; } static void setRowMask(int row) { int i, j, start, shift = 0; int modUnit, divUnit; for (i = 0; i < MINUNITS(); i++) rowMask[i] = 0; for (j = 0; j <= row; j++) { start = j * bits * (sizeX + j); shift = 0; for (i = 0; i < (sizeX + j) ; i++) { modUnit = (start + shift) % arch; divUnit = (start + shift) / arch; rowMask[divUnit] |= intMask << modUnit; shift += bits; } } } static void setTrBlMask(int trbl) { int i, j, start, shift = 0; int modUnit, divUnit; for (i = 0; i < MINUNITS(); i++) trblMask[i] = 0; for (j = 0; j <= trbl; j++) { start = j * bits; shift = 0; for (i = 0; i < sizeY; i++) { modUnit = (start + shift) % arch; divUnit = (start + shift) / arch; trblMask[divUnit] |= intMask << modUnit; shift += (sizeX + i) * bits; } } } static void setTlBrMask(int tlbr) { int i, j, start, shift = 0; int modUnit, divUnit; for (i = 0; i < MINUNITS(); i++) tlbrMask[i] = 0; for (j = 0; j <= tlbr; j++) { start = (sizeX - 1 - j) * bits; shift = 0; for (i = 0; i < sizeY; i++) { modUnit = (start + shift) % arch; divUnit = (start + shift) / arch; tlbrMask[divUnit] |= intMask << modUnit; shift += (sizeX + i + 1) * bits; } } } static char checkSolvedByUnitRow(int row) { int i; setRowMask(row); for (i = 0; i < MINUNITS(); i++) if ((shrunkPositionOfTile[i] & rowMask[i]) != (finishTiles[i] & rowMask[i])) return FALSE; /*printf("rowMask %lld\n", rowMask[0]); printf("%lld %lld\n", shrunkPositionOfTile[0], finishTiles[0]); printf("%lld %lld\n", shrunkPositionOfTile[0] & rowMask[0], finishTiles[0] & rowMask[0]);*/ return TRUE; } static char checkSolvedByUnitTrBl(int trbl) { int i; setTrBlMask(trbl); for (i = 0; i < MINUNITS(); i++) if ((shrunkPositionOfTile[i] & trblMask[i]) != (finishTiles[i] & trblMask[i])) return FALSE; /*printf("trblMask %lld\n", trblMask[0]); printf("%lld %lld\n", shrunkPositionOfTile[0], finishTiles[0]); printf("%lld %lld\n", shrunkPositionOfTile[0] & trblMask[0], finishTiles[0] & trblMask[0]);*/ return TRUE; } static char checkSolvedByUnitTlBr(int tlbr) { int i; setTlBrMask(tlbr); for (i = 0; i < MINUNITS(); i++) if ((shrunkPositionOfTile[i] & tlbrMask[i]) != (finishTiles[i] & tlbrMask[i])) return FALSE; /*printf("tlbrMask %lld\n", tlbrMask[0]); printf("%lld %lld\n", shrunkPositionOfTile[0], finishTiles[0]); printf("%lld %lld\n", shrunkPositionOfTile[0] & tlbrMask[0], finishTiles[0] & tlbrMask[0]);*/ return TRUE; } static char checkSolvedByUnit() { int i; for (i = 0; i < units; i++) if (shrunkPositionOfTile[i] != finishTiles[i]) return FALSE; return TRUE; } static char partiallySolveRow(int row) { if (((sizeX == 1 && sizeY - row >= 4) || (sizeX == 2 && sizeY - row >= 3) || (sizeX == 3 && sizeY - row >= 3) || (sizeX > 4)) && piecemeal) return TRUE; return FALSE; } static char partiallySolveTrBl(int trbl) { if (((sizeX == 1 && sizeY - trbl >= 4) || (sizeX == 2 && sizeY - trbl >= 3) || (sizeX == 3 && sizeY - trbl >= 3) || (sizeX > 4)) && piecemeal) return TRUE; return FALSE; } static char partiallySolveTlBr(int tlbr) { if (((sizeX == 1 && sizeY - tlbr >= 4) || (sizeX == 2 && sizeY - tlbr >= 4) || (sizeX == 3 && sizeY - tlbr >= 3) || (sizeX > 4)) && piecemeal) return TRUE; return FALSE; } static int scanStartPosition(FILE *fp) { int i, num, c; for (i = 0; i < AREA; i++) { if (fscanf(fp, "%d ", &num) != 1) { (void) fprintf(stderr, "corrupt start record, expecting an integer for %d\n", i); return FALSE; } startPosition[i] = num; if ((!num && !corners) || ((num < 0) && corners)) { startPosition[i] = BLANK; startSpacePosition = i; } else if (!num) { startPosition[i] = BLANK2; startSpacePosition2 = i; } } return TRUE; } static int scanFinishPosition(FILE *fp) { int i, num, c; for (i = 0; i < AREA; i++) { if (fscanf(fp, "%d ", &num) != 1) { (void) fprintf(stderr, "corrupt start record, expecting an integer for %d\n", i); return FALSE; } finishPosition[i] = num; if ((!num && !corners) || ((num < 0) && corners)) { finishPosition[i] = BLANK; finishSpacePosition = i; } else if (!num) { finishPosition[i] = BLANK2; finishSpacePosition2 = i; } } return TRUE; } static void setTilesToStart() { int i, j; /* Need one more for start position */ if (strcmp(startFile, "") != 0) { FILE *fp; if ((fp = fopen(startFile, "r")) != NULL) { scanStartPosition(fp); } else { fprintf(stderr, "cannot open %s\n", startFile); exit(1); } } else { setStartPosition(); } for (i = 0; i < AREA; i++) { j = startPosition[i]; tileOfPosition[j] = i; positionOfTile[i] = j; } if (!corners || sizeX != 1) { /* FIXME */ if (tileOfPosition[BLANK] != startSpacePosition) { printf("fix start!!! tileOfPosition0=%d, startSpacePosition=%d\n", tileOfPosition[BLANK], startSpacePosition); } if (corners && tileOfPosition[BLANK2] != startSpacePosition2) { printf("fix start!!! tileOfPosition1=%d, startSpacePosition2=%d\n", tileOfPosition[BLANK2], startSpacePosition2); } } printf("start:\n"); printTiles(positionOfTile); for (i = 0; i < AREA; i++) setStart(i, startPosition[i]); if (debug) { printf("check start\n"); /*for (i = 0; i < AREA; i++) startPosition[i] = getStart(i);*/ for (i = 0; i < AREA; i++) { j = startPosition[i]; tileOfPosition[j] = i; positionOfTile[i] = j; } /*printTiles(positionOfTile);*/ } for (j = 0; j < units; j++) shrunkPositionOfTile[j] = 0; for (i = 0; i < AREA; i++) setTile(i, positionOfTile[i]); if ((!corners || sizeX > 2 || sizeY > 1) && checkSolvedByUnit()) printf("solution FAILED!!! (start)\n"); } static void setTilesToFinish() { int i, j; if (strcmp(finishFile, "") != 0) { FILE *fp; if ((fp = fopen(finishFile, "r")) != NULL) { scanFinishPosition(fp); } else { fprintf(stderr, "cannot open %s\n", finishFile); exit(1); } } else { setFinishPosition(); } for (i = 0; i < AREA; i++) { j = finishPosition[i]; tileOfPosition[j] = i; positionOfTile[i] = j; } if (tileOfPosition[BLANK] != finishSpacePosition) { printf("fix finish!!! tileOfPosition0=%d, finishSpacePosition=%d\n", tileOfPosition[BLANK], finishSpacePosition); } if (corners && tileOfPosition[BLANK2] != finishSpacePosition2) { printf("fix finish!!! tileOfPosition1=%d, finishSpacePosition2=%d\n", tileOfPosition[BLANK2], finishSpacePosition2); } printf("finish:\n"); printTiles(positionOfTile); for (i = 0; i < AREA; i++) setFinish(i, finishPosition[i]); if (debug) { /*for (i = 0; i < AREA; i++) finishPosition[i] = getFinish(i);*/ for (i = 0; i < AREA; i++) { j = finishPosition[i]; tileOfPosition[j] = i; positionOfTile[i] = j; } /*printPositions(tileOfPosition);*/ } for (j = 0; j < units; j++) shrunkPositionOfTile[j] = 0; for (i = 0; i < AREA; i++) setTile(i, positionOfTile[i]); if (!checkSolvedByUnit()) printf("solution FAILED!!! (finish)\n"); } static void resetTiles() { int i; if (nodeLog) (void) free((void *) nodeLog); if (!(nodeLog = (LONG *) calloc(size * units, sizeof (LONG)))) { memoryError("nodeLog"); } if (!(hash = (hashtype **) calloc(hashSize, sizeof (hashtype *)))) { memoryError("hash table"); } if (tileOfPosition) (void) free((void *) tileOfPosition); if (!(tileOfPosition = (char *) calloc(AREA, sizeof (char)))) { memoryError("tileOfPosition"); } if (startPosition) (void) free((void *) startPosition); if (!(startPosition = (char *) calloc(AREA, sizeof (char)))) { memoryError("startPosition"); } if (finishPosition) (void) free((void *) finishPosition); if (!(finishPosition = (char *) calloc(AREA, sizeof (char)))) { memoryError("finishPosition"); } if (positionOfTile) (void) free((void *) positionOfTile); if (!(positionOfTile = (char *) calloc(AREA, sizeof (char)))) { memoryError("positionOfTile"); } if (shrunkPositionOfTile) (void) free((void *) shrunkPositionOfTile); if (!(shrunkPositionOfTile = (LONG *) calloc(units, sizeof (LONG)))) { memoryError("shrunkPositionOfTile"); } if (rowMask) (void) free((void *) rowMask); if (!(rowMask = (LONG *) calloc(units, sizeof (LONG)))) { memoryError("rowMask"); } if (trblMask) (void) free((void *) trblMask); if (!(trblMask = (LONG *) calloc(units, sizeof (LONG)))) { memoryError("trblMask"); } if (tlbrMask) (void) free((void *) tlbrMask); if (!(tlbrMask = (LONG *) calloc(units, sizeof (LONG)))) { memoryError("tlbrMask"); } if (startTiles) (void) free((void *) startTiles); if (!(startTiles = (LONG *) calloc(units, sizeof (LONG)))) { memoryError("startTiles"); } if (finishTiles) (void) free((void *) finishTiles); if (!(finishTiles = (LONG *) calloc(units, sizeof (LONG)))) { memoryError("finishTiles"); } if (move) (void) free((void *) move); if (!(move = (int *) calloc(size, sizeof (int)))) { memoryError("move"); } if (backPoss) (void) free((void *) backPoss); if (!(backPoss = (char *) calloc(size, sizeof (char)))) { memoryError("backPoss"); } if (backPath) (void) free((void *) backPath); if (!(backPath = (int *) calloc(size, sizeof (int)))) { memoryError("backPath"); } setTilesToFinish(); setTilesToStart(); putCurrent(currNode); getCurrent(currNode); if (debug) { printf("printTiles\n"); printTiles(tileOfPosition); printf("printPositions\n"); printPositions(positionOfTile); } move[0] = 0; backPoss[0] = -1; /* needed for first pass */ loop = 0; hashNewIndex = 0; c = 0; for (i = 0; i < bits; i++) { intMask |= 1 << i; } spacePosition[1] = BLANK2; } static void moveCornerTiles(int fromPosition, int posRow, int space) { #if 0 int fromTile, nextPos, row; int dx, dy, s0x, s0y, s1x, s1y, cx, cy; fromTile = tileOfPosition[fromPosition]; #if 0 nextPos = spacePosition[space]; row = toRow(from); /* positionOfTile[BLANK] */ row = toRow(spacePosition[space]); row = toRow(spacePosition[OPP_BLANK(space)]); #endif tileOfPosition[fromPosition] = tileOfPosition[spacePosition[space]]; spacePosition[space] = fromPosition; spaceRow[space] = posRow; /* FIXME */ tileOfPosition[nextPos] = fromTile; #endif int fromTile = tileOfPosition[fromPosition]; int spacePosition = positionOfTile[space]; int i, j; positionOfTile[fromTile] = spacePosition; positionOfTile[space] = fromPosition; tileOfPosition[fromPosition] = tileOfPosition[spacePosition]; tileOfPosition[spacePosition] = fromTile; if (positionOfTile[BLANK2] < positionOfTile[BLANK]) { swapChar(&(positionOfTile[BLANK]), &(positionOfTile[BLANK2])); tileOfPosition[positionOfTile[BLANK]] = BLANK; tileOfPosition[positionOfTile[BLANK2]] = BLANK2; } for (j = 0; j < units; j++) shrunkPositionOfTile[j] = 0; for (i = 0; i < AREA; i++) setTile(i, tileOfPosition[i]); } static int moveNoCornTiles(int fromPosition, int posRow) { int fromTile = tileOfPosition[fromPosition]; int spacePosition = positionOfTile[BLANK]; int i, j; positionOfTile[fromTile] = spacePosition; positionOfTile[BLANK] = fromPosition; tileOfPosition[fromPosition] = tileOfPosition[spacePosition]; tileOfPosition[spacePosition] = fromTile; for (j = 0; j < units; j++) shrunkPositionOfTile[j] = 0; for (i = 0; i < AREA; i++) setTile(i, tileOfPosition[i]); } static int findTileTriangle(int pI, int pJ, int pK, int rI, int rJ, int rK) { int temp = 0, k = 0, row1 = 0, row2 = 0, pos; int found = TRUE; if (rI == rJ) { if (pI == pJ - 1) temp = pJ; else if (pI == pJ + 1) temp = pI; else found = FALSE; k = pK; row1 = rI; row2 = rK; } else if (rJ == rK) { if (pJ == pK - 1) temp = pK; else if (pJ == pK + 1) temp = pJ; else found = FALSE; k = pI; row1 = rJ; row2 = rI; } else if (rK == rI) { if (pK == pI - 1) temp = pI; else if (pK == pI + 1) temp = pK; else found = FALSE; k = pJ; row1 = rK; row2 = rJ; } if (!found) return (0); pos = -1; if (row1 == row2 + 1) { if (row1 <= sizeY - 1) pos = temp - sizeX - row1; else /* row1 > sizeY - 1 */ pos = temp - 2 * sizeY - sizeX + row1 + 1; } else if (row1 == row2 - 1) { if (row1 < sizeY - 1) pos = temp + sizeX + row1; else /* row1 >= sizeY - 1 */ pos = temp + 2 * (sizeY - 1) + (sizeX - 1) - row1; } if (k == pos) return TRUE; return FALSE; } static int findSpaceType(int p1, int p2, int r1, int r2) { int pos1 = p1, pos2 = p2, row1 = r1, row2 = r2; if (row1 == row2 && (pos1 == pos2 + 1 || pos1 == pos2 - 1)) return (ROW); else if (row1 == row2 - 1) { swapInt(&row1, &row2); swapInt(&pos1, &pos2); } if (row1 == row2 + 1) { if (row1 <= sizeY - 1) { if (pos2 == pos1 - sizeX - row1) return (TLBR); else if (pos2 == pos1 - sizeX - row1 + 1) return (TRBL); } else { /* row1 > sizeY - 1 */ if (pos2 == pos1 - 2 * sizeY - sizeX + row1 + 1) return (TLBR); else if (pos2 == pos1 - 2 * sizeY - sizeX + row1 + 2) return (TRBL); } } return (-1); } static void findMovableTile(int pos, int posRow, int spaceType, int side, int *tilePos, int *tileRow) { switch (spaceType) { case TRBL: if (side == HIGH) { *tileRow = posRow; *tilePos = pos + 1; } else { /* side == LOW */ *tileRow = posRow - 1; *tilePos = (posRow <= sizeY - 1) ? pos - sizeX - posRow : pos - 2 * sizeY - sizeX + posRow + 1; } break; case TLBR: if (side == HIGH) { *tileRow = posRow; *tilePos = pos - 1; } else { /* side == LOW */ *tileRow = posRow - 1; *tilePos = (posRow <= sizeY - 1) ? pos - sizeX - posRow + 1 : pos - 2 * sizeY - sizeX + posRow + 2; } break; case ROW: if (side == HIGH) { *tileRow = posRow + 1; *tilePos = (posRow < sizeY - 1) ? pos + sizeX + posRow : pos + 2 * sizeY + sizeX - posRow - 3; } else { /* side == LOW */ *tileRow = posRow - 1; *tilePos = (posRow <= sizeY - 1) ? pos - sizeX - posRow : pos - 2 * sizeY - sizeX + posRow + 1; } break; default: { (void) printf("findMovableTile: spaceType %d\n", spaceType); *tileRow = 0; *tilePos = 0; } } } static int nextToWall(int pos, int posRow, int spaceType) { switch (spaceType) { case TRBL: if (posRow < sizeY && pos == sizeX * posRow + posRow * (posRow - 1) / 2) return (HIGH); else if (posRow >= sizeY && pos == sizeY * (2 * posRow - sizeY + 3) - sizeX * posRow - 2 - posRow + 4 * sizeX * (sizeX - 1) / 2 - (2 * sizeX - posRow - 2) * (2 * sizeX - posRow - 1) / 2) return (LOW); else return (-1); case TLBR: if (posRow < sizeY && pos == sizeX * (posRow + 1) + posRow * (posRow + 1) / 2 - 1) return (HIGH); else if (posRow >= sizeY && pos == sizeY * (2 * posRow - sizeY + 1) - sizeX * (posRow + 1) + 1 + 4 * sizeX * (sizeX - 1) / 2 - (2 * sizeX - posRow - 2) * (2 * sizeX - posRow - 1) / 2) return (LOW); else return (-1); case ROW: if (posRow == 0) return (HIGH); else if (posRow == 2 * (sizeY - 1)) return (LOW); else return (-1); } return (-2); /* Unknown space formation. */ } static int movableCornerTiles(int direction, int spacePosition, int space2Position, int *position, int *posRow, int *space) { int spaceType, side = -1; if (spaceRow[ROW] <= frozenRows && space2Row[ROW] <= frozenRows && (direction == BL || direction == BR)) return FALSE; if (spaceRow[TRBL] <= frozenTrBl && space2Row[TRBL] <= frozenTrBl && (direction == RIGHT || direction == BR)) return FALSE; if (spaceRow[TLBR] <= frozenTlBr && space2Row[TLBR] <= frozenTlBr && (direction == LEFT || direction == BL)) return FALSE; /* positionOfTile[BLANK] */ spaceType = findSpaceType(space2Position, spacePosition, space2Row[ROW], spaceRow[ROW]); switch (spaceType) { case TRBL: if (direction == TR || direction == BL) return FALSE; side = nextToWall(space2Position, space2Row[ROW], spaceType); if (side != -1) { if ((side == HIGH && direction == RIGHT) || (side == HIGH && direction == BR) || (side == LOW && direction == LEFT) || (side == LOW && direction == TL)) return FALSE; } else side = (direction == TL || direction == LEFT); *space = (direction == BR || direction == LEFT) * BLANK2; break; case TLBR: if (direction == TL || direction == BR) return FALSE; side = nextToWall(space2Position, space2Row[ROW], spaceType); if (side != -1) { if ((side == LOW && direction == TR) || (side == LOW && direction == RIGHT) || (side == HIGH && direction == BL) || (side == HIGH && direction == LEFT)) return FALSE; } else side = (direction == TR || direction == RIGHT); *space = (direction == RIGHT || direction == BL) * BLANK2; break; case ROW: if (direction == LEFT || direction == RIGHT) return FALSE; side = nextToWall(space2Position, space2Row[ROW], spaceType); if (side != -1) { if ((side == LOW && direction == TR) || (side == HIGH && direction == BR) || (side == HIGH && direction == BL) || (side == LOW && direction == TL)) return FALSE; } else side = (direction == TR || direction == TL); *space = (direction == TR || direction == BR) * BLANK2; break; default: { (void) printf("movableCornerTiles: spaceType %d\n", spaceType); printf("%d %d %d %d\n", space2Position, spacePosition, space2Row[ROW], spaceRow[ROW]); *space = 0; } } findMovableTile(space2Position, space2Row[ROW], spaceType, side, position, posRow); return TRUE; } static int moveCornerSpaceDir(int direction, int spacePosition, int space2Position) { int position, posRow, space; calculateRows(spacePosition); calculateRows2(space2Position); if (movableCornerTiles(direction, spacePosition, space2Position, &position, &posRow, &space)) { moveCornerTiles(position, posRow, space); return TRUE; } return FALSE; } static char moveNoCornSpaceDir(int direction, int spacePosition) { calculateRows(spacePosition); /*printf("Dir%d SPACE%d, ROW %d, TRBL=%d, TLBR=%d\n", direction, spacePosition, spaceRow[ROW], spaceRow[TRBL], spaceRow[TLBR]);*/ switch (direction) { case TR: if (spaceRow[ROW] != 2 * sizeY - 2 && spaceRow[TLBR] != sizeX + sizeY - 2) { if (spaceRow[ROW] < frozenRows) return FALSE; if (spaceRow[TLBR] < frozenTlBr) return FALSE; moveNoCornTiles(tileNFrom(spacePosition, 1, TRBL, LOW), spaceRow[ROW] + 1); return TRUE; } break; case RIGHT: if (spaceRow[TRBL] != 0 && spaceRow[TLBR] != sizeX + sizeY - 2) { if (spaceRow[TLBR] < frozenTlBr) return FALSE; moveNoCornTiles(tileNFrom(spacePosition, 1, ROW, HIGH), spaceRow[ROW]); return TRUE; } break; case BR: if (spaceRow[ROW] != 0 && spaceRow[TRBL] != 0) { moveNoCornTiles(tileNFrom(spacePosition, 1, TLBR, HIGH), spaceRow[ROW] - 1); return TRUE; } break; case BL: if (spaceRow[ROW] != 0 && spaceRow[TLBR] != 0) { moveNoCornTiles(tileNFrom(spacePosition, 1, TRBL, HIGH), spaceRow[ROW] - 1); return TRUE; } break; case LEFT: if (spaceRow[TLBR] != 0 && spaceRow[TRBL] != sizeX + sizeY - 2) { if (spaceRow[TRBL] < frozenTrBl) return FALSE; moveNoCornTiles(tileNFrom(spacePosition, 1, ROW, LOW), spaceRow[ROW]); return TRUE; } break; case TL: if (spaceRow[ROW] != 2 * sizeY - 2 && spaceRow[TRBL] != sizeX + sizeY - 2) { if (spaceRow[ROW] < frozenRows) return FALSE; if (spaceRow[TRBL] < frozenTrBl) return FALSE; moveNoCornTiles(tileNFrom(spacePosition, 1, TLBR, LOW), spaceRow[ROW] + 1); return TRUE; } break; default: (void) printf("dir? %d\n", direction); } return FALSE; } /* FURTHER */ static void printLastData(int node) { if (backPath[node] > node || (node != 0 && backPath[node] == node)) { return; } getCurrent(node); if (node != 0) { (void) printf("%3d: %s\n", move[node], dirToString((int) backPoss[node])); } printPositions(positionOfTile); } /* FURTHER */ static void printLastHash(int index) { hashtype **oldChain = &(chain[index]); hashtype *ctemp = *oldChain; while (ctemp != NULL) { printLastData(ctemp->node); ctemp = ctemp->next; } } static void printDataMove(int node) { if (backPath[node] > node || (node != 0 && backPath[node] == node)) { return; } if (node != 0) { printDataMove(backPath[node]); } getCurrent(node); if (node != 0) { (void) fprintf(stderr, "%d: %d\n", move[node], backPoss[node]); } } static void printData(int node) { if (backPath[node] > node || (node != 0 && backPath[node] == node)) { return; } if (node != 0) { printData(backPath[node]); } getCurrent(node); if (node != 0) { (void) printf("%3d: %s\n", move[node], dirToString((int) backPoss[node])); } printPositions(positionOfTile); } static int getnum(char * message) { char buff[80]; (void) printf("%s: ", message); return((int) strtol(fgets(buff, 80, stdin), 0, 0)); } static void readData(int nodes) { #ifdef ARCH128 arch = 128; #elif defined( ARCH64 ) arch = 64; if (debug) (void) printf("%d bit architecture.\n", arch); #else arch = 8 * sizeof( bitmask ); (void) printf("Assuming %d bit architecture.\n", arch); #endif tiles = AREA - 1 - ((corners) ? 1 : 0); while (sizeX < 1) sizeX = getnum((char *) "Enter: # of sizeX >"); while (sizeY < 1 + ((corners) ? 1: 0)) sizeY = getnum((char *) "Enter: # of sizeY >"); if (tiles > ARRAYTWEAKS) { (void) printf("Be careful, you need lots of memory.\n"); inputSize = getnum((char *) "Enter: # of nodes to keep in memory >"); hashSize = getnum((char *) "Enter: size of hash >"); } else { if (tiles < NOFULLSOLUTION && nodes == 0) inputSize = minSizes[tiles]; else { /* 3 moves must be kept in memory to progress */ int minMem = 3 * moveSizes[tiles]; if (nodes == 0) inputSize = minMem; else inputSize = nodes; if (inputSize < minMem) { (void) printf("Nodes %lld < %d, changing\n", inputSize, minMem); inputSize = minMem; } if (inputSize < minSizes[tiles]) (void) printf( "Full path may not be printed\n"); } hashSize = hashSizes[tiles]; } size = inputSize; if (debug) (void) printf("size %d\n", size); bits = MINBITS(); if (bits == 0) { (void) printf("no moves needed\n"); exit(0); } units = MINUNITS(); numInUnit = MAXNUMINUNIT(); if (debug) (void) printf("bits %d, units %d, numInUnit %d\n", bits, units, numInUnit); bitmask = (1 << bits) - 1; freqmask = (int) (~((1 << FREQBITS) - 1)); if (units > 2) (void) printf("Key for hash may not be efficient.\n"); if (debug > 1) /* hashless check */ unitMem = (sizeof (char)) * units; resetTiles(); } static int isNewNode() { int unit, node; LONG *psPOT, *pnodeLog; LONG *pnodeLogFirst = &(nodeLog[newNode * units]); for (node = newNode; node >= newBottom; node--) { /* check if already done */ pnodeLog = pnodeLogFirst; psPOT = shrunkPositionOfTile; for (unit = 0; unit < units; unit++) { if (*pnodeLog != *psPOT) goto CONTINUE; /* I hate gotos */ pnodeLog++; psPOT++; } return FALSE; CONTINUE: pnodeLogFirst -= unitMem; } return TRUE; } static void searchBreadthFirst() { int localMoveSize = 0, moveSize = 0; char m; int foundSolution = 0; char *ppOT = positionOfTile; int moved = FALSE; int temp; for (;;) { /*printf("SPACE%d, ROW %d, TRBL=%d, TLBR=%d\n", ppOT[BLANK], spaceRow[ROW], spaceRow[TRBL], spaceRow[TLBR]);*/ LOOP: for (m = 0; m < (char) POSSIBILITIES; m++) { if (backPoss[currNode] == OPP_DIR(m)) { /*printf("not doing %d\n", m);*/ /* undoing previous move */ continue; /* move could be shorter, so ignore */ } if (corners) moved = moveCornerSpaceDir((int) m, ppOT[BLANK], ppOT[BLANK2]); else moved = moveNoCornSpaceDir((int) m, ppOT[BLANK]); if (moved) { if (debug) { (void) printf("breadth dir %s, last dir %s\n", dirToString(m), dirToString(backPoss[currNode])); printPositions(ppOT); } if (!(inHash())) { /*printf("not in hash\n");*/ if (debug > 1 && !isNewNode()) { /* hashless check */ (void) printf("got node:%d %lld\n", newNode + 1, *shrunkPositionOfTile); } newNode++; if (newNode >= size) { newNode = 0; } if ((newNode & freqmask) == newNode) { if (newNode == 0) (void) printf("loop:%d; ", loop + 1); (void) printf("node:%d; move:%d; collisions:%lld\n", newNode, move[currNode] + 1, c); } backPoss[newNode] = m; backPath[newNode] = currNode; move[newNode] = move[currNode] + 1; localMoveSize++; putCurrent(newNode); /* save node */ putInHash(hashNewIndex, newNode); if (partiallySolveRow(frozenRows) && checkSolvedByUnitRow(frozenRows)) { frozenRows += 1; printf("freezing row %d at move %d\n", frozenRows, move[newNode]); printData(newNode); currNode = newNode; goto LOOP; } if (partiallySolveTrBl(frozenTrBl) && checkSolvedByUnitTrBl(frozenTrBl)) { frozenTrBl += 1; printf("freezing trbl %d at move %d\n", frozenTrBl, move[newNode]); printData(newNode); currNode = newNode; goto LOOP; } if (partiallySolveTlBr(frozenTlBr) && checkSolvedByUnitTlBr(frozenTlBr)) { frozenTlBr += 1; printf("freezing tlbr %d at move %d\n", frozenTlBr, move[newNode]); printData(newNode); currNode = newNode; goto LOOP; } if (checkSolvedByUnit()) { (void) printf("loops: %d, size: %d, nodes: %d; moves: %d\n", loop, size, newNode + 1, move[newNode]); if (redirect) { (void) fprintf(stderr, "corners: %d\n", corners); (void) fprintf(stderr, "tiles.x: %d\n", sizeX); (void) fprintf(stderr, "tiles.y: %d\n", sizeY); (void) fprintf(stderr, "moves: %d\n", move[newNode]); (void) fprintf(stderr, "\nstartingPosition:\n"); printTilesDigit(startPosition); (void) fprintf(stderr, "\nmoves direction\n"); printDataMove(newNode); } printData(newNode); (void) printf("total nodes: %d * %d + %d\n", loop, size, newNode + 1); (void) printf("total nodes when found solution: %lld\n", (long long) loop * size + newNode + 1); (void) printf("moveSize: %d\n", moveSize); (void) printf("collisions: %lld\n", c); foundSolution = move[newNode]; (void) printf("total moves: %d\n", foundSolution); if (mode == MINIMUM_MOVES) exit(0); /* Do not exit as may find a better solution */ /* Done when number of moves for mode progresses */ } } getCurrent(currNode); /* backout */ } } if (newNode != currNode) { if (move[currNode] < move[(currNode + 1) % size]) { if (mode != FURTHER && foundSolution) { (void) printf("total nodes when complete: %lld\n", (long long) loop * size + newNode + 1); exit(0); } if (debug > 1) { printLastHash(hashNewIndex); } if (debug > 1) { /* hashless check */ newBottom = move[(currNode + 1) % size]; } if (localMoveSize > moveSize) { moveSize = localMoveSize; } localMoveSize = 0; hashNewIndex = (hashNewIndex + 1) % CHAINS; freeHash(hashNewIndex); } currNode++; if (currNode >= size) { currNode = 0; loop++; } getCurrent(currNode); } else { if (mode == FURTHER) (void) printf("Farthest point\n"); else if (!foundSolution) (void) printf("No solution\n"); (void) printf("loops: %d, size: %d, nodes: %d; moves: %d\n", loop, size, newNode + 1, move[newNode]); if (mode == FURTHER) printData(newNode); if (size < minSizes[tiles - 1]) (void) printf("total nodes: %d\n", loop * size + newNode + 1); else (void) printf("total nodes: %d * %d + %d\n", loop, size, newNode + 1); (void) printf("moveSize: %d\n", moveSize); (void) printf("collisions: %lld\n", c); (void) printf("total moves: %d\n", move[newNode]); if (mode == FURTHER) { printLastHash((hashNewIndex + CHAINS - 1) % CHAINS); } exit(0); } } } static void usage() { (void) fprintf(stderr, "usage: \"hexagons [-c] [-d debugLevel] [-i initial] [-s start_file] [-f finish_file] [-m mode] [-n nodesNumber] [-p] [-r] [-x X] [-y Y]\"\n"); (void) fprintf(stderr, "\tinitial:\t0 mirror (default)\n"); (void) fprintf(stderr, "\t\t1 mirror (default)\n"); (void) fprintf(stderr, "\t\t2 reverse\n"); (void) fprintf(stderr, "\t\t3 offset reverse\n"); (void) fprintf(stderr, "\tstart:\tstart positions (s)\n"); (void) fprintf(stderr, "\tfinish:\tfinish positions (f)\n"); (void) fprintf(stderr, "\tcorners:\ttiles have corners (c)\n"); (void) fprintf(stderr, "\tmode:\t0 match finish point (default)\n"); (void) fprintf(stderr, "\t\t1 find furthest point\n"); (void) fprintf(stderr, "\tpiecemeal:\tallow piecemeal solution (p)\n"); (void) fprintf(stderr, "\tredirect:\toutput log to stderr (r)\n"); (void) fprintf(stderr, "\tstart:\t0 offset (default)\n"); exit(1); } int main(int argc, char **argv) { int nodes = 0; argc--; argv++; while (argc) { if (argv[0][0] == '-') { switch (argv[0][1]) { case '\0': usage('a'); break; case 'c': corners = TRUE; break; case 'd': if (argc > 1) { argc--; argv++; debug = atoi(argv[0]); break; } else { usage('d'); } case 'i': if (argc > 1) { argc--; argv++; initial = atoi(argv[0]); if (initial < 0 || initial >= STARTS) initial = OFFSET; break; } else { usage('i'); } case 'f': argc--; argv++; strncpy(finishFile, argv[0], FILE_NAME_LENGTH); break; case 'm': if (argc > 1) { argc--; argv++; mode = atoi(argv[0]); if (mode < 0 || mode >= MODES) mode = MINIMUM_MOVES; break; } else { usage('m'); } case 'n': if (argc > 1) { argc--; argv++; nodes = atoi(argv[0]); break; } else { usage('n'); } case 'p': piecemeal = TRUE; break; case 'r': redirect = TRUE; break; case 's': argc--; argv++; strncpy(startFile, argv[0], FILE_NAME_LENGTH); break; case 'x': if (argc > 1) { argc--; argv++; sizeX = atoi(argv[0]); break; } else { usage('x'); } case 'y': if (argc > 1) { argc--; argv++; sizeY = atoi(argv[0]); break; } else { usage('y'); } default: usage('b'); } } argc--; argv++; } readData(nodes); #if !defined( __MSDOS__ ) && !defined( __CYGWIN__ ) /* This gets rid of the unwanted buffering in UNIX */ (void) setlinebuf(stdout); #endif searchBreadthFirst(); #ifdef VMS return 1; #else return 0; #endif }