/* # # Copyright (c) 2001 - 2004 David Albert Bagley, bagleyd@tux.org # # 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! cc -O panex.c -o nap nohup nice nap 9 2>&1 > nap.out & /usr/platform/sun4u/sbin/prtdiag -v Old System Configuration: Sun Microsystems sun4u Sun Enterprise 220R (1 X UltraSPARC-II 450MHz) System clock frequency: 113 MHz Memory size: 2048 Megabytes New System Configuration: Sun Microsystems sun4u Sun Fire V1280 (4 X UltraSPARC-III+ 1200MHZ) System clock frequency: 150 MHZ Memory size: 8GB Using 1 of 4 CPUs */ /* Coded after reading "Some Results on the Panex Puzzle" */ /* by Mark Manasse & Danny Sleator of AT&T Bell Laboratories, */ /* and Victor K. Wei of Bell Communications Research. */ /* Also got some help from Nick Baxter . */ /* This program calculates the panex puzzle problem. */ /* 'N' (usually 10) purple and yellow tiles need to be exchanged. */ /* Input: */ /* # of purple or yellow tiles */ /* # of nodes you expect it to take to search for a solution. */ /* (See minSizes table below.) */ /* Output: */ /* The optimum route to exchange the tiles, but must obey rule */ /* no tile can go through another tile (on 2d plane) and no tile can */ /* sink below its initial starting point. Tiles can only move from one */ /* stack to another along the top. The width between stacks is one tile */ /* width. If it takes 2^22 nodes to search for a solution then it will */ /* print the node and its current move (panex order 6 and above). As it */ /* stands now a full solution will not be printed for order 7 or more. */ /* int minMoves[11] = {3, 13, 42, 128, 343, */ /* 881, 2189, 5359, 13023, 31537, 76245}; */ /* 10..11 are not proven but likely. */ /* minTime[9] = {0., 0., 0., 0.5sec, 5sec, */ /* 1min 42sec, 38min 8sec, 14 hours 16min 13sec, 5 days 15 minutes}; */ /* By extrapolation... order 10: >2 years */ /* (All but the last were done on a Sun Ultra-4, 2 Gig RAM (64 Arch)) */ /* Also may need 7.78*2*Gig = 15.4Gig of RAM for order 10 */ /* To get this to program to run for order 7, the memory had to be cut */ /* down but this throws away the path to the answer and just leaves you */ /* with the number of moves. */ /* TODO * Confirm level 10. */ /*Farthest move from - - - A - a B - b C - c D - d E - e F - f G - g H - h I - i int farthestMove[9] = {3, 13, 44, 137, 377, 964, 2384, 5820, 14128}; minTime[9] = {0., 0., 0., 0.5sec, 10sec, 3min 32sec, 1hr 49min, 1day 13hrs 20min, /*new CPU*/ 9days 10hrs 48min}; Note: I disallow moving a piece to the top middle position. It is simple to add that position in by this method (note all nonsolution (except panex 1 nonsolution) cases have the middle position 1 down filled):: In cases where one side is filled to the top: by moving the tile from the other side to the middle, it will be in the topmost position guarantees one extra move. The only way to proceed is to undo the move or move the same piece forward. In cases where positions of the left or right top pieces are both in the farthest set the moving of this piece to the middle would guarantee one extra move since the only way to proceed is to move the piece to a move that is in the set. Note the two above cases are not mutually exclusive and 4-6 have them but they still add up to only 1 extra move. The solution cases and the nonsolution panex 1 case would not have the top middle position filled in the next move so these would not make a difference for an additional move. So if you allow top middle positions the maximum would be int farthestMove[9] = {3, 13, 45, 138, 378, 965, 2385, 5821, 14129}; The mirror image would be an anti-solution... farthest position from a solution. Due to symmetry and the unavoidable exchange of the final 2 pieces longest path (p) where s is the number of moves in the solution and f the farthest number of moves in a path (f). p =~ 2(f - s) + s = 2f - s Farthest moves 1: 3 moves A - - a - - (solution) - - - a - A 2: 13 moves (solution) - - - a - A b - B - - - - a A b - B 3: 44 moves a - - B A - b - - c - C A - - B a - b - - c - C 4: 137 moves - - b B A a C - - c - - d - D - - b B a A C - - c - - d - D b - - B a A C - - c - - d - D b - - B A a C - - c - - d - D 5: 377 moves - - b c a A C - B D - - d - - e - E b - - a A c C - B D - - d - - e - E - - b a A c C - B D - - d - - e - E b - - c a A C - B D - - d - - e - E 6: 964 moves - - b c a A C - B D - - E d - e - - f - F b - - a A c C - B D - - E d - e - - f - F - - b a A c C - B D - - E d - e - - f - F b - - c a A C - B D - - E d - e - - f - F 7: 2384 moves - - B C a A b - c - - e E d D F - - f - - g - G B - - a A C b - c - - e E d D F - - f - - g - G - - B a A C b - c - - e E d D F - - f - - g - G B - - C a A b - c - - e E d D F - - f - - g - G - - b c a A C - B e - - E d D F - - f - - g - G b - - a A c C - B e - - E d D F - - f - - g - G - - b a A c C - B e - - E d D F - - f - - g - G b - - c a A C - B e - - E d D F - - f - - g - G 8: 5820 moves - - B C a A b - c - - e d D f F - E G - - g - - h - H B - - a A C b - c - - e d D f F - E G - - g - - h - H - - B a A C b - c - - e d D f F - E G - - g - - h - H B - - C a A b - c - - e d D f F - E G - - g - - h - H - - b c a A C - B e - - d D f F - E G - - g - - h - H b - - a A c C - B e - - d D f F - E G - - g - - h - H - - b a A c C - B e - - d D f F - E G - - g - - h - H b - - c a A C - B e - - d D f F - E G - - g - - h - H - - B C a A b - c - - e f d D F - E G - - g - - h - H B - - a A C b - c - - e f d D F - E G - - g - - h - H - - B a A C b - c - - e f d D F - E G - - g - - h - H B - - C a A b - c - - e f d D F - E G - - g - - h - H - - b c a A C - B e - - f d D F - E G - - g - - h - H b - - a A c C - B e - - f d D F - E G - - g - - h - H - - b a A c C - B e - - f d D F - E G - - g - - h - H b - - c a A C - B e - - f d D F - E G - - g - - h - H 9: 14128 moves - - B C a A b - c - - E d D f e - g G - F H - - h - - i - I B - - a A C b - c - - E d D f e - g G - F H - - h - - i - I - - B a A C b - c - - E d D f e - g G - F H - - h - - i - I B - - C a A b - c - - E d D f e - g G - F H - - h - - i - I - - b c a A C - B E - - d D f e - g G - F H - - h - - i - I b - - a A c C - B E - - d D f e - g G - F H - - h - - i - I - - b a A c C - B E - - d D f e - g G - F H - - h - - i - I b - - c a A C - B E - - d D f e - g G - F H - - h - - i - I - - B C a A b - c - - E f d D e - g G - F H - - h - - i - I B - - a A C b - c - - E f d D e - g G - F H - - h - - i - I - - B a A C b - c - - E f d D e - g G - F H - - h - - i - I B - - C a A b - c - - E f d D e - g G - F H - - h - - i - I - - b c a A C - B E - - f d D e - g G - F H - - h - - i - I b - - a A c C - B E - - f d D e - g G - F H - - h - - i - I - - b a A c C - B E - - f d D e - g G - F H - - h - - i - I b - - c a A C - B E - - f d D e - g G - F H - - h - - i - I - - B C a A b - c - - e d D f g - E G - F H - - h - - i - I B - - a A C b - c - - e d D f g - E G - F H - - h - - i - I - - B a A C b - c - - e d D f g - E G - F H - - h - - i - I B - - C a A b - c - - e d D f g - E G - F H - - h - - i - I - - b c a A C - B e - - d D f g - E G - F H - - h - - i - I b - - a A c C - B e - - d D f g - E G - F H - - h - - i - I - - b a A c C - B e - - d D f g - E G - F H - - h - - i - I b - - c a A C - B e - - d D f g - E G - F H - - h - - i - I - - B C a A b - c - - e f d D g - E G - F H - - h - - i - I B - - a A C b - c - - e f d D g - E G - F H - - h - - i - I - - B a A C b - c - - e f d D g - E G - F H - - h - - i - I B - - C a A b - c - - e f d D g - E G - F H - - h - - i - I - - b c a A C - B e - - f d D g - E G - F H - - h - - i - I b - - a A c C - B e - - f d D g - E G - F H - - h - - i - I - - b a A c C - B e - - f d D g - E G - F H - - h - - i - I b - - c a A C - B e - - f d D g - E G - F H - - h - - i - I Level 1 could not have the top middle position filled except for two trivial symmetrical cases both are found before the solution. Level 2 if you allow one to put a tile in the upper middle this takes 13 moves also. (Checked via computer search as the only additional one). - A - - a - b - B Since the rest of the levels allows a move to the top center, already adding one to the count, this takes care of the remainder. */ /* #define FURTHER 1 */ #define MEET_AT_MIDDLE 1 /* 4x savings from mail by Nick Baxter The paper also describes a 4x savings, taking advantage of the symmetry of the puzzle, and by attacking the solution from both ends. This makes the "solution" check a bit more complicated (for each new node x, you must compute and check for x', x* and x*' as well as just x). But this saves a lot of space. Depending on the problem, the number of states being analyzed by the Dykstra algorithm could grow rapidly as the number of moves increases. The number of states could also remain constant or go down, but this is less common. I think you characterized the growth for this puzzle as increasing, but modest. Let's say the average growth rate for new nodes each turn is p (p>1), and the minimal solution is 2n. That gives us (p^(2n)-1)/(p-1) total nodes if we just go from start to finish. If on the other hand we solve simultaneously from either end, then the number of nodes visited is just 2(p^n-1)/(p-1). The latter approach saves (p^n-1)^2 nodes! I think I'm +/-1 off on the exponents, but you get the idea. Remember that p is growth rate of NEW nodes. If p is just +1%, then this is 10^19 nodes for level 7! So solving from both ends can save a lot of search space. Panex has both color and mirror symmetries. Solving from the goal is really the same search, but with the puzzle mirrored OR the colors swapped. Their notation was x* is a color swap, and x' is a mirror image. If x is reachable from the start in n moves, then x' and x* are reachable from the finish in n moves. So every time you add a new position to the list, you check to see if x' or x* are already there. If so, then you've found a solution for the entire puzzle that is potentially minimal. So, as you are building a new n-list for n+1 moves, and you find a matching x' or x*, it will corresponding to an n or n+1 move path from the end, giving a 2n+1 or 2n+2 solution. Because of this, I believe you have to continue building the complete n-list because a 2n+2 solution could still be improved by a 2n+1 solution. It's conceivable that a 1 move savings could be overlooked if this isn't done carefully. There is also the case of x'* (x*' is the same). If x is n moves from the start, then so is x'*. Thus if x'* is already on a list, you do not need to add x. This gives additional space savings. The cost is that you have to compute x', x*, and x'* each time you need to check if a node exists yet. The assumption is that the space savings is worth this work. */ #include #include #define FALSE 0 #define TRUE 1 #define LEFT 0 #define MIDDLE 1 #define RIGHT 2 #define MAXSTACKS 3 /* maximum number of stacks */ #define KINDS 2 /* number of different colors of tiles */ #define POSSIBILITIES 6 /* maximum number of possible moves */ #define CHAINS 3 /* for deleting nodes from hash table */ #define ARRAYTWEAKS 10 /* if <= tiles it will consult array for tweaks */ #define FREQBITS 22 /* sets frequency of what node & move its at now */ /* Note: Reset fullSolution to FALSE if you do not have the memory. size can not be set lower than the maximum number of nodes it takes to make "CHAINS" moves anywhere in the search... Also if the size is greater than minSizes a solution path can not be generated. */ /*#define ARCH128 */ /*#define ARCH64*/ #define DOUBLE_UNSIGNED 1 /* double sized hash */ #ifdef ARCH128 #include using namespace std; const int len = 128; /* does not work past panex 4 due to to_ulong() conversion, also slow */ #define TO_LONG(x) (x).to_ulong() #define LONG bitset #elif defined( ARCH64 ) #define TO_LONG(x) (x) #define LONG unsigned long long #else #define TO_LONG(x) (x) #define LONG unsigned long #endif #ifdef DOUBLE_UNSIGNED /* panex 10 or less */ #define HASHESH(x) (TO_LONG(*x+((*(x+1))*253))%hashSize) #else /* panex 4 or less */ /* panex 6 or less if ARCH64 */ #define HASHESH(x) (TO_LONG(*x)%hashSize) #endif static int MEMSTACKS = (sizeof (char)) * MAXSTACKS; static int EMPTY; /* already assumes l is not EMPTY */ #define tileNumber(l) ((l < tiles) ? l : l - tiles) #define tileNum(l) ((l < tiles) ? ((l) << 1) : (((l - tiles) << 1) + 1)) #define numTile(l) ((l >> 1) + ((l & 1) ? tiles : 0)) #define tileChar(l) ((l == EMPTY) ? '-' : ((l < tiles) ? l + 'A' :\ l + 'a' - tiles)) static int fullSolution[ARRAYTWEAKS] = {TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE}; static int hashSizes[ARRAYTWEAKS] = {31, 253, 1021, 65533, 131071, 262141, 1048573, 8388607, 259000001, 259000001}; /* Maximum number of nodes for a move. Seems to grow by a factor of 7.77 */ /* moveSizes must be at least 3* this value to insure proper operation. */ /* This is only for finding the number of moves... a full path is not */ /* generated. */ #if 1 #define CEILING 40000000 #elif 0 #define CEILING 249000000 #endif #ifdef MEET_AT_MIDDLE /* If using CEILING it must be at least 3 * moveSizes to work. */ static int moveSizes[ARRAYTWEAKS] = {2, 9, 56, 411, 3158, 23273, 180126, 1361077, 10578363, /*?*/ 83000000}; /* The number of nodes seems to go up roughly by a factor of 18.8. */ static long long minSizes[ARRAYTWEAKS] = {4, 39, 608, 11552, 216578, 4060357, 75977723, 1424658852, 26750202138, /*?*/ 50290380020}; /* If using CEILING it must be at least 3 * moveSizes to work. */ #elif defined( FURTHER ) static int moveSizes[ARRAYTWEAKS] = {2, 10, 63, 412, 3158, 23273, 180126, 1361077, 10578363, /*?*/ 83000000}; /* The number of nodes seems to go up roughly by a factor of 20. */ static long long minSizes[ARRAYTWEAKS] = {6, 82, 1536, 29336, 555584, 10475616, 196687040, 3710370688, 69798594048, /*?*/ 1312213568102}; #else static int moveSizes[ARRAYTWEAKS] = {2, 9, 56, 411, 3158, 23273, 180126, 1361077, 10578363, /*?*/ 83000000}; /* The number of nodes seems to go up roughly by a factor of 20. */ static long long minSizes[ARRAYTWEAKS] = {5, 82, 1504, 28827, 544976, 10338816, 194975071, 3671881192, 69105921539, /*?*/ 1306101917087}; #endif /* minBits[] = ceil(log2(MAXSTACKS * (tiles + 1))) arch = 32 or 64 maxNumInUnit = MIN(floor(arch / minBits), KINDS * tiles) minUnits = ceil(KINDS * tiles / maxNumInUnit) */ static int minBits[11] = {3, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6}; #ifdef ARCH128 static int maxNumInUnit128[11] = {2, 4, 6, 8,10,12,14,16,18,20,22}; static int minUnits128[11] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}; #elif defined ( ARCH64 ) static int maxNumInUnit64[11] = {2, 4, 6, 8,10,12,12,12,12,10,10}; /*static int minUnits64[11] = {1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 3};*/ static int minUnits64[11] = {1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 3}; #else static int maxNumInUnit32[11] = {2, 4, 6, 8, 6, 6, 6, 6, 6, 5, 5}; static int minUnits32[11] = {1, 1, 1, 1, 2, 2, 3, 3, 3, 4, 5}; #endif static LONG *nodeLog = NULL; static char *backPoss = NULL; static int *move = NULL, *backPath = NULL; static int newNode = 0, currNode = 0; #ifdef HASHLESS /* slow but good to check the hashes are working */ static int newBottom = 0; static int unitMem; #endif static LONG *startTiles = NULL, *finishTiles = NULL; typedef struct _hashtype { int node; struct _hashtype *next; } hashtype; static hashtype **hash; static hashtype *chain[CHAINS]; static int hashNewIndex; static long long c /* , nc, fc, fnc */; static char *tileOfPosition = NULL; /* easier to see */ static char *positionOfTile = NULL; /* takes up less memory */ static LONG *shrunkPositionOfTile = NULL; /* takes even less memory */ static LONG *colorPositionOfTile = NULL; /* color swap of previous */ static LONG *mirrorColorPositionOfTile = NULL; /* mirror of previous */ static LONG *mirrorPositionOfTile = NULL; /* mirror of sPOT */ static int tiles; /* # of tiles of the same kind */ static int height; /* tiles + 1 */ static int areaPositions; /* MAXSTACKS * (tiles + 1) */ static int areaTiles; /* KINDS * tiles */ static int size, hashSize; static long long inputSize; static int bits, units, numInUnit; static LONG bitmask; static int freqmask; static int loop; /* chosen by efficiency */ /*static int fromPoss[POSSIBILITIES]={0, 0, 1, 1, 2, 2};*/ static int toPoss[POSSIBILITIES]={1, 2, 2, 0, 0, 1}; #define fromPoss(n) (n >> 1) /*#define toPoss(n) (((n + MAXSTACKS) >> 1) % MAXSTACKS) */ static void setColorSwap() { LONG *pcPOT = colorPositionOfTile; char *ppOT = positionOfTile; int j, shift, n = 0; for (;;) { shift = 0; *pcPOT = 0; for (j = 0; j < numInUnit; j++) { if (n % 2) ppOT--; else ppOT++; *pcPOT |= (((LONG) *ppOT) << shift); if (n % 2) { ppOT++; ppOT++; } shift += bits; n++; if (n >= areaTiles) { return; } } pcPOT++; } } static void setMirrorImage(LONG *psPOT, LONG *pmPOT) { int j, shift, n = 0; unsigned long value; for (;;) { shift = 0; *pmPOT = 0; for (j = 0; j < numInUnit; j++) { value = TO_LONG((*psPOT >> shift) & bitmask); value = (value / MAXSTACKS) * MAXSTACKS + MAXSTACKS - 1 - (value % MAXSTACKS); *pmPOT |= (((LONG) value) << shift); shift += bits; n++; if (n >= areaTiles) { return; } } psPOT++; pmPOT++; } } static void freeHash(int index) { hashtype **oldChain = &(chain[index]); hashtype *ctemp = *oldChain; hashtype **oldHashPt; hashtype *htemp, *temp; while (ctemp) { oldHashPt = &(hash[HASHESH(&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; } } #if DEBUG static void printHash(){ int i; for (i = 0; i < hashSize; i++) { hashtype *temp = hash[i]; while (temp != NULL) { (void) printf("%d: %d %ld\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[HASHESH(psPOT)]; while (temp != NULL) { tempsPOT = psPOT; pnodeLog = &(nodeLog[temp->node * units]); for (i = 0; i < units; i++) { if (*pnodeLog != *tempsPOT) goto HASHCONTINUE; pnodeLog++; tempsPOT++; } return TRUE; HASHCONTINUE: temp = temp->next; } setColorSwap(); setMirrorImage(colorPositionOfTile, mirrorColorPositionOfTile); psPOT = mirrorColorPositionOfTile; temp = hash[HASHESH(psPOT)]; while (temp != NULL) { tempsPOT = psPOT; pnodeLog = &(nodeLog[temp->node * units]); for (i = 0; i < units; i++) { if (*pnodeLog != *tempsPOT) goto MIRRORCOLORCONTINUE; pnodeLog++; tempsPOT++; } return TRUE; MIRRORCOLORCONTINUE: temp = temp->next; } return FALSE; } #ifdef MEET_AT_MIDDLE #define COLORSWAP #define MIRRORIMAGE /* The same as previous except that it returns node with shortest path */ static int checkInHash( LONG *pcPOT, LONG *pmPOT) { LONG *tempsPOT, *pnodeLog; hashtype *temp; int i, flag = -1; #ifdef COLORSWAP temp = hash[HASHESH(pcPOT)]; while (temp != NULL) { tempsPOT = pcPOT; pnodeLog = &(nodeLog[temp->node * units]); for (i = 0; i < units; i++) { if (*pnodeLog != *tempsPOT) goto CHASHCONTINUE; pnodeLog++; tempsPOT++; } if ((flag == -1) || (move[flag] > move[temp->node])) flag = temp->node; CHASHCONTINUE: temp = temp->next; } #endif #ifdef MIRRORIMAGE temp = hash[HASHESH(pmPOT)]; while (temp != NULL) { tempsPOT = pmPOT; pnodeLog = &(nodeLog[temp->node * units]); for (i = 0; i < units; i++) { if (*pnodeLog != *tempsPOT) goto CMIRRORCOLORCONTINUE; pnodeLog++; tempsPOT++; } if ((flag == -1) || (move[flag] > move[temp->node])) flag = temp->node; CMIRRORCOLORCONTINUE: temp = temp->next; } #endif return flag; } #endif 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 putInHash(int index, int node) { hashtype **oldHashPt = &(hash[HASHESH(&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; char *ppOT = positionOfTile; int j, shift, n = 0; for (;;) { shift = 0; *psPOT = 0; for (j = 0; j < numInUnit; j++) { *psPOT |= (((LONG) *ppOT) << shift); shift += bits; ppOT++; n++; if (n >= areaTiles) { *pnodeLog = *psPOT; return; } } *pnodeLog = *psPOT; psPOT++; pnodeLog++; } } static void getCurrent(int node) { int stack, position, j, shift, n = 0; LONG *pnodeLog = &(nodeLog[node * units]); LONG *psPOT = shrunkPositionOfTile; char *ppOT = positionOfTile; char *ptOP = tileOfPosition; for (position = 0; position < height; position++) for (stack = 0; stack < MAXSTACKS; stack++) { *ptOP = EMPTY; ptOP++; } for (;;) { shift = 0; *psPOT = *pnodeLog; for (j = 0; j < numInUnit; j++) { *ppOT = (char) TO_LONG((((LONG) *psPOT) >> shift) & bitmask); tileOfPosition[(int) *ppOT] = numTile(n); shift += bits; ppOT++; n++; if (n >= areaTiles) return; } pnodeLog++; psPOT++; } } static void printStacks() { int position, stack; char *ptOP = tileOfPosition; for (position = 0; position < height; position++) for (stack = 0; stack < MAXSTACKS; stack++) { (void) printf("%c", tileChar(*ptOP)); if (stack == MAXSTACKS - 1) (void) printf("\n"); else (void) printf(" "); ptOP++; } } static void printOtherStacks() { int position; char *ptOP = tileOfPosition, *temp; for (position = 0; position < height; position++) { temp = ptOP; temp++; temp++; (void) printf("%c ", tileChar(*temp)); temp = ptOP; temp++; (void) printf("%c ", tileChar(*temp)); (void) printf("%c\n", tileChar(*ptOP)); ptOP++; ptOP++; ptOP++; } } #ifdef DEBUG static void printKinds() { int tile, kind; char *ppOT = positionOfTile; for (tile = 0; tile < tiles; tile++) for (kind = 0; kind < KINDS; kind++) { (void) printf("%d", *ppOT); if (kind == KINDS - 1) (void) printf("\n"); else (void) printf(" "); ppOT++; } } static void printOtherKinds() { int tile, kind, value; char *ppOT = positionOfTile; for (tile = 0; tile < tiles; tile++) for (kind = 0; kind < KINDS; kind++) { value = (*ppOT / MAXSTACKS) * MAXSTACKS + MAXSTACKS - 1 - *ppOT % MAXSTACKS; (void) printf("%d", value); if (kind == KINDS - 1) (void) printf("\n"); else (void) printf(" "); ppOT++; } } #endif static void resetTiles() { int tile, l, m, n; 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 (positionOfTile) (void) free((void *) positionOfTile); if (!(positionOfTile = (char *) calloc(areaTiles, sizeof (char)))) { memoryError("positionOfTile"); } if (tileOfPosition) (void) free((void *) tileOfPosition); if (!(tileOfPosition = (char *) calloc(areaPositions, sizeof (char)))) { memoryError("tileOfPosition"); } if (shrunkPositionOfTile) (void) free((void *) shrunkPositionOfTile); if (!(shrunkPositionOfTile = (LONG *) calloc(units, sizeof (LONG)))) { memoryError("shrunkPositionOfTile"); } if (colorPositionOfTile) (void) free((void *) colorPositionOfTile); if (!(colorPositionOfTile = (LONG *) calloc(units, sizeof (LONG)))) { memoryError("colorPositionOfTile"); } if (mirrorPositionOfTile) (void) free((void *) mirrorPositionOfTile); if (!(mirrorPositionOfTile = (LONG *) calloc(units, sizeof (LONG)))) { memoryError("mirrorPositionOfTile"); } if (mirrorColorPositionOfTile) (void) free((void *) mirrorColorPositionOfTile); if (!(mirrorColorPositionOfTile = (LONG *) calloc(units, sizeof (LONG)))) { memoryError("mirrorColorPositionOfTile"); } 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"); } m = 0; n = MAXSTACKS; for (tile = 0; tile < tiles; tile++) { l = m / numInUnit; startTiles[l] |= (n << (bits * (m % numInUnit))); positionOfTile[m] = n; /* mirrorColorPositionOfTile[l] = */ shrunkPositionOfTile[l] = startTiles[l]; finishTiles[l] |= ((n + 2) << (bits * (m % numInUnit))); /* mirrorPositionOfTile[l] = colorPositionOfTile[l] = finishTiles[l]; */ n += 2; m++; l = m / numInUnit; startTiles[l] |= (n << (bits * (m % numInUnit))); positionOfTile[m] = n; /* mirrorColorPositionOfTile[l] = */ shrunkPositionOfTile[l] = startTiles[l]; finishTiles[l] |= ((n - 2) << (bits * (m % numInUnit))); /* mirrorPositionOfTile[l] = colorPositionOfTile[l] = finishTiles[l]; */ n++; m++; } putCurrent(currNode); #ifdef DEBUG for (l = 0; l < units; l++) (void) printf("start %x\n", startTiles[l]); for (l = 0; l < units; l++) (void) printf("finish %x\n", finishTiles[l]); #endif getCurrent(currNode); move[0] = 0; backPoss[0] = 0; /* needed for first pass */ loop = 0; hashNewIndex = 0; c = 0; /* nc = 0; fc = 0; fnc = 0; */ } static int checkSolved() { int unit; LONG *pfT = finishTiles; LONG *psPOT = shrunkPositionOfTile; for (unit = 0; unit < units; unit++) { if (*pfT != *psPOT) return FALSE; pfT++; psPOT++; } return TRUE; } static int moveATile(int fromStack, int toStack) { int fromPosition = -1; int position; char *ptOPF = &(tileOfPosition[fromStack]); LONG *psPOT; for (position = 0; position < height; position++) { if (*ptOPF != EMPTY) { fromPosition = position; break; } ptOPF += MEMSTACKS; } if (fromPosition < 0) { return FALSE; } else { /* request move */ int toPosition; char *ptOPT = &(tileOfPosition[toStack]); /* Do not have to check middle stack since we do not allow one to put something there. */ if (*ptOPT != EMPTY) return FALSE; { /* topOfStack and panex rule */ toPosition = tileNumber(*ptOPF) + 1; position = 1; ptOPT += MEMSTACKS; if (toStack == 1) { if (*ptOPT != EMPTY) /* this move is legal but not helpful */ return FALSE; ptOPT += MEMSTACKS; position = 2; } for (; position <= toPosition; position++) { if (*ptOPT != EMPTY) { toPosition = (position - 1); break; } ptOPT += MEMSTACKS; } ptOPT -= MEMSTACKS; } /* slide tile */ { int tile = tileNum(*ptOPF); int offset = bits * (tile % numInUnit); int index = tile / numInUnit; *ptOPT = *ptOPF; position = toStack + toPosition * MAXSTACKS; positionOfTile[tile] = position; *ptOPF = EMPTY; psPOT = &(shrunkPositionOfTile[index]); *psPOT &= ~((LONG) bitmask << offset); *psPOT |= ((LONG) position << offset); } } return TRUE; } #ifdef FURTHER static void printLastData(int node) { if (backPath[node] > node || (node != 0 && backPath[node] == node)) { return; } getCurrent(node); if (node != 0) { (void) printf("%3d: %d, %d\n", move[node], fromPoss((int) backPoss[node]), toPoss[(int) backPoss[node]]); } printStacks(); } static void printLastHash(int index) { hashtype **oldChain = &(chain[index]); hashtype *ctemp = *oldChain; while (ctemp != NULL) { printLastData(ctemp->node); ctemp = ctemp->next; } } #endif 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: %d, %d\n", move[node], fromPoss((int) backPoss[node]), toPoss[(int) backPoss[node]]); } printStacks(); } static void printOtherData(int node, int otherMove) { getCurrent(node); printOtherStacks(); if (backPath[node] > node || (node != 0 && backPath[node] == node)) { return; } if (node != 0) { (void) printf("%3d: %d, %d\n", otherMove, 2 - toPoss[(int) backPoss[node]], 2 - fromPoss((int) backPoss[node])); printOtherData(backPath[node], otherMove + 1); } } #ifdef MEET_AT_MIDDLE static void printAllData(int node, int otherNode) { printData(node); (void) printf("~~~~~~~~~\n"); printOtherData(otherNode, move[node] + 1); } #endif static int getnum(char * message) { char buff[80]; (void) printf("%s: ", message); return((int) strtol(gets(buff), 0, 0)); } static void readData(int level, int nodes) { tiles = level; while (tiles < 1) tiles = getnum((char *) "Enter: # of tiles >"); #ifdef ARCH128 #ifdef DOUBLE_UNSIGNED if (minUnits128[tiles - 1] > 2) (void) printf("Key for hash may not be efficient.\n"); if (minUnits128[tiles - 1] < 2) { (void) printf("Probably will error out, try compiling without DOUBLE_UNSIGNED or ARCH128.\n"); } #else if (minUnits128[tiles - 1] > 1) (void) printf("Key for hash may not be efficient.\n"); #endif #elif defined( ARCH64 ) #ifdef DOUBLE_UNSIGNED if (minUnits64[tiles - 1] > 2) (void) printf("Key for hash may not be efficient.\n"); if (minUnits64[tiles - 1] < 2) { (void) printf("Probably will error out, try compiling without DOUBLE_UNSIGNED or ARCH64.\n"); } #else if (minUnits64[tiles - 1] > 1) (void) printf("Key for hash may not be efficient, try DOUBLE_UNSIGNED.\n"); #endif #else #ifdef DOUBLE_UNSIGNED if (minUnits32[tiles - 1] > 2) (void) printf("Key for hash may not be efficient, try ARCH64.\n"); if (minUnits32[tiles - 1] < 2) { (void) printf("Probably will error out, try not compiling without DOUBLE_UNSIGNED.\n"); } #else if (minUnits32[tiles - 1] > 1) (void) printf("Key for hash may not be efficient, try DOUBLE_UNSIGNED or ARCH64.\n"); #endif #endif height = tiles + 1; areaTiles = KINDS * tiles; areaPositions = MAXSTACKS * height; EMPTY = 2 * tiles; 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 (fullSolution[tiles - 1] && nodes == 0) inputSize = minSizes[tiles - 1]; else { inputSize = nodes; if (inputSize == 0) inputSize = CEILING; if (inputSize < 3 * moveSizes[tiles - 1]) { inputSize = 3 * moveSizes[tiles - 1]; (void) printf("Nodes to small, trying %lld\n", inputSize); } if (inputSize < minSizes[tiles - 1]) (void) printf( "Full path will not be printed\n"); } hashSize = hashSizes[tiles - 1]; } size = inputSize; bits = minBits[tiles - 1]; #ifdef ARCH128 units = minUnits128[tiles - 1]; numInUnit = maxNumInUnit128[tiles - 1]; #elif defined( ARCH64 ) units = minUnits64[tiles - 1]; numInUnit = maxNumInUnit64[tiles - 1]; #else units = minUnits32[tiles - 1]; numInUnit = maxNumInUnit32[tiles - 1]; #endif bitmask = (1 << bits) - 1; freqmask = (int) (~((1 << FREQBITS) - 1)); #ifdef HASHLESS unitMem = (sizeof (char)) * units; #endif resetTiles(); } #ifdef HASHLESS 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; } #endif static void searchBreadthFirst() { int localMoveSize = 0, moveSize = 0; #ifdef MEET_AT_MIDDLE int otherNode; #endif char m; for (;;) { for (m = 0; m < (char) POSSIBILITIES; m++) { if (toPoss[(int) backPoss[currNode]] == fromPoss((int) m)) continue; /* move could be shorter, so ignore */ if (moveATile(fromPoss((int) m), toPoss[(int) m])) { if (!(inHash())) { #ifdef HASHLESS if (!isNewNode()) { (void) printf("got node:%d %ld\n", newNode + 1, *shrunkPositionOfTile); } #endif 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); #ifndef FURTHER setMirrorImage(shrunkPositionOfTile, mirrorPositionOfTile); #ifdef MEET_AT_MIDDLE if ((otherNode = checkInHash( colorPositionOfTile, mirrorPositionOfTile)) != -1) #else if (checkSolved()) #endif { #ifdef MEET_AT_MIDDLE (void) printf("loops: %d, size: %d, nodes: %d; moves: %d, otherMoves: %d\n", loop, size, newNode + 1, move[newNode], move[otherNode]); printAllData(newNode, otherNode); (void) printf("loops: %d, size: %d, nodes: %d; moves: %d, otherMoves: %d\n", loop, size, newNode + 1, move[newNode], move[otherNode]); #else (void) printf("loops: %d, size: %d, nodes: %d; moves: %d\n", loop, size, newNode + 1, move[newNode]); printData(newNode); #endif (void) printf("total nodes: %d * %d + %d\n", loop, size, newNode + 1); (void) printf("total nodes: %lld\n", (long long) loop * size + newNode + 1); (void) printf("moveSize: %d\n", moveSize); (void) printf("collisions: %lld\n", c); (void) printf("total moves: %d\n", move[newNode] #ifdef MEET_AT_MIDDLE + move[otherNode] #endif ); exit(0); } #endif } getCurrent(currNode); /* backout */ } } if (newNode != currNode) { if (move[currNode] < move[(currNode + 1) % size]) { /* if (move[newNode] == 12) printLastHash(hashNewIndex); */ #ifdef HASHLESS newBottom = move[(currNode + 1) % size]; #endif if (localMoveSize > moveSize) { moveSize = localMoveSize; } localMoveSize = 0; hashNewIndex = (hashNewIndex + 1) % CHAINS; freeHash(hashNewIndex); } currNode++; if (currNode >= size) { currNode = 0; loop++; } getCurrent(currNode); } else { #ifdef FURTHER (void) printf("Farthest point\n"); #else (void) printf("No solution\n"); #endif (void) printf("loops: %d, size: %d, nodes: %d; moves: %d\n", loop, size, newNode + 1, move[newNode]); printData(newNode); if (tiles <= 7) (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]); #ifdef FURTHER printLastHash((hashNewIndex + CHAINS - 1) % CHAINS); #endif exit(0); } } } static void usage() { (void) fprintf(stderr, "usage: \"panex [-n nodesNumber] levelNumber\"\n"); exit(1); } int main(int argc, char **argv) { int level = 0; int nodes = 0; argc--; argv++; while (argc) { if (argv[0][0] == '-') { switch (argv[0][1]) { case '\0': usage(); break; case 'n': if (argc > 1) { argc--; argv++; nodes = atoi(argv[0]); break; } else { usage(); } default: usage(); } } else level = atoi(argv[0]); argc--; argv++; } readData(level, nodes); #if !defined( __MSDOS__ ) && !defined( __CYGWIN__ ) /* This gets rid of the unwanted buffering in UNIX */ (void) setlinebuf(stdout); #endif if (!checkSolved()) { searchBreadthFirst(); } else printData(0); #ifdef VMS return 1; #else return 0; #endif }