/* cc -O panex.c -lm -o nap 2>&1 | more date > now ; nohup nice ./nap 10 2>&1 > nap.out & # # Copyright (c) 2001 - 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! Older /usr/platform/sun4u/sbin/prtdiag -v System Configuration: Sun Microsystems sun4u Sun Enterprise 220R (1 X UltraSPARC-II 450MHz) System clock frequency: 113 MHz Memory size: 2 GB Old /usr/platform/sun4u/sbin/prtdiag -v 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 New head /proc/meminfo MemTotal: 16058756 kB head /proc/cpuinfo cpu MHz : 1255.525 Newer head /proc/meminfo MemTotal: 32539256 kB head /proc/cpuinfo cpu MHz : 2300.000 */ /* 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 singleTower[10]= {1, 3, 9, 24, 58, */ /* 143, 345, 836, 2018, 4875}; T(n) */ /* int minMoves[11] = {3, 13, 42, 128, 343, */ /* 881, 2189, 5359, 13023, 31537, 76245}; */ /* 1-10 confirmed by this program. X(n) */ /* 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.6Gig of RAM for order 10 */ /* minTime[9] = {0., 0., 0., 0., 1sec, */ /* 3 sec, 1min 35sec, 33min 46sec, 10 hours 59 min 52 sec}; */ /* Increased this when went to 32 Gig RAM */ /* minTime[10] = {0., 0., 0., 0., 1sec, */ /* 3 sec, 1min 35sec, 33min 46sec, 10 hours 59 min 52 sec */ /* 14.5 days}; */ /* 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. */ /* Farthest move from - - - A - a B - b C - c D - d E - e F - f G - g H - h I - i int farthestMove[10] = {3, 13, 44, 137, 377, 964, 2384, 5820, 14128, 34196}; 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[10] = {3, 13, 45, 138, 378, 965, 2385, 5821, 14129, 34197}; 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 (listing all solutions for 1-10) Level 1 farthest positions (2) 3: 1, 0 A - - a - - 3: 1, 2 (solution) - - - a - A Level 2 farthest positions (2) 13: 0, 2 (solution) - - - a - A b - B 13: 0, 2 - - - - a A b - B Level 3 farthest positions (2) 44: 2, 0 a - - B A - b - - c - C 44: 2, 1 A - - B a - b - - c - C Level 4 farthest positions (4) 137: 0, 1 - - b B A a C - - c - - d - D 137: 0, 1 - - b B a A C - - c - - d - D 137: 2, 1 b - - B a A C - - c - - d - D 137: 2, 1 b - - B A a C - - c - - d - D Level 5 farthest positions (4) 377: 0, 1 - - b c a A C - B D - - d - - e - E 377: 2, 1 b - - a A c C - B D - - d - - e - E 377: 0, 1 - - b a A c C - B D - - d - - e - E 377: 2, 1 b - - c a A C - B D - - d - - e - E Level 6 farthest positions (4) 964: 0, 1 - - b c a A C - B D - - E d - e - - f - F 964: 2, 1 b - - a A c C - B D - - E d - e - - f - F 964: 0, 1 - - b a A c C - B D - - E d - e - - f - F 964: 2, 1 b - - c a A C - B D - - E d - e - - f - F Level 7 farthest positions (8) 2384: 0, 1 - - B C a A b - c - - e E d D F - - f - - g - G 2384: 2, 1 B - - a A C b - c - - e E d D F - - f - - g - G 2384: 0, 1 - - B a A C b - c - - e E d D F - - f - - g - G 2384: 2, 1 B - - C a A b - c - - e E d D F - - f - - g - G 2384: 0, 1 - - b c a A C - B e - - E d D F - - f - - g - G 2384: 2, 1 b - - a A c C - B e - - E d D F - - f - - g - G 2384: 0, 1 - - b a A c C - B e - - E d D F - - f - - g - G 2384: 2, 1 b - - c a A C - B e - - E d D F - - f - - g - G Level 8 farthest positions (16) 5820: 0, 1 - - B C a A b - c - - e d D f F - E G - - g - - h - H 5820: 2, 1 B - - a A C b - c - - e d D f F - E G - - g - - h - H 5820: 0, 1 - - B a A C b - c - - e d D f F - E G - - g - - h - H 5820: 2, 1 B - - C a A b - c - - e d D f F - E G - - g - - h - H 5820: 0, 1 - - b c a A C - B e - - d D f F - E G - - g - - h - H 5820: 2, 1 b - - a A c C - B e - - d D f F - E G - - g - - h - H 5820: 0, 1 - - b a A c C - B e - - d D f F - E G - - g - - h - H 5820: 2, 1 b - - c a A C - B e - - d D f F - E G - - g - - h - H 5820: 0, 1 - - B C a A b - c - - e f d D F - E G - - g - - h - H 5820: 2, 1 B - - a A C b - c - - e f d D F - E G - - g - - h - H 5820: 0, 1 - - B a A C b - c - - e f d D F - E G - - g - - h - H 5820: 2, 1 B - - C a A b - c - - e f d D F - E G - - g - - h - H 5820: 0, 1 - - b c a A C - B e - - f d D F - E G - - g - - h - H 5820: 2, 1 b - - a A c C - B e - - f d D F - E G - - g - - h - H 5820: 0, 1 - - b a A c C - B e - - f d D F - E G - - g - - h - H 5820: 2, 1 b - - c a A C - B e - - f d D F - E G - - g - - h - H Level 9 farthest positions (32) 14128: 0, 1 - - B C a A b - c - - E d D f e - g G - F H - - h - - i - I 14128: 2, 1 B - - a A C b - c - - E d D f e - g G - F H - - h - - i - I 14128: 0, 1 - - B a A C b - c - - E d D f e - g G - F H - - h - - i - I 14128: 2, 1 B - - C a A b - c - - E d D f e - g G - F H - - h - - i - I 14128: 0, 1 - - b c a A C - B E - - d D f e - g G - F H - - h - - i - I 14128: 2, 1 b - - a A c C - B E - - d D f e - g G - F H - - h - - i - I 14128: 0, 1 - - b a A c C - B E - - d D f e - g G - F H - - h - - i - I 14128: 2, 1 b - - c a A C - B E - - d D f e - g G - F H - - h - - i - I 14128: 0, 1 - - B C a A b - c - - E f d D e - g G - F H - - h - - i - I 14128: 2, 1 B - - a A C b - c - - E f d D e - g G - F H - - h - - i - I 14128: 0, 1 - - B a A C b - c - - E f d D e - g G - F H - - h - - i - I 14128: 2, 1 B - - C a A b - c - - E f d D e - g G - F H - - h - - i - I 14128: 0, 1 - - b c a A C - B E - - f d D e - g G - F H - - h - - i - I 14128: 2, 1 b - - a A c C - B E - - f d D e - g G - F H - - h - - i - I 14128: 0, 1 - - b a A c C - B E - - f d D e - g G - F H - - h - - i - I 14128: 2, 1 b - - c a A C - B E - - f d D e - g G - F H - - h - - i - I 14128: 0, 1 - - B C a A b - c - - e d D f g - E G - F H - - h - - i - I 14128: 2, 1 B - - a A C b - c - - e d D f g - E G - F H - - h - - i - I 14128: 0, 1 - - B a A C b - c - - e d D f g - E G - F H - - h - - i - I 14128: 2, 1 B - - C a A b - c - - e d D f g - E G - F H - - h - - i - I 14128: 0, 1 - - b c a A C - B e - - d D f g - E G - F H - - h - - i - I 14128: 2, 1 b - - a A c C - B e - - d D f g - E G - F H - - h - - i - I 14128: 0, 1 - - b a A c C - B e - - d D f g - E G - F H - - h - - i - I 14128: 2, 1 b - - c a A C - B e - - d D f g - E G - F H - - h - - i - I 14128: 0, 1 - - B C a A b - c - - e f d D g - E G - F H - - h - - i - I 14128: 2, 1 B - - a A C b - c - - e f d D g - E G - F H - - h - - i - I 14128: 0, 1 - - B a A C b - c - - e f d D g - E G - F H - - h - - i - I 14128: 2, 1 B - - C a A b - c - - e f d D g - E G - F H - - h - - i - I 14128: 0, 1 - - b c a A C - B e - - f d D g - E G - F H - - h - - i - I 14128: 2, 1 b - - a A c C - B e - - f d D g - E G - F H - - h - - i - I 14128: 0, 1 - - b a A c C - B e - - f d D g - E G - F H - - h - - i - I 14128: 2, 1 b - - c a A C - B e - - f d D g - E G - F H - - h - - i - I Level 10 farthest positions (64) 34196: 0, 1 - - B C a A b - c - - E d D F e - g f - h H - G I - - i - - j - J 34196: 2, 1 B - - a A C b - c - - E d D F e - g f - h H - G I - - i - - j - J 34196: 0, 1 - - B a A C b - c - - E d D F e - g f - h H - G I - - i - - j - J 34196: 2, 1 B - - C a A b - c - - E d D F e - g f - h H - G I - - i - - j - J 34196: 0, 1 - - b c a A C - B E - - d D F e - g f - h H - G I - - i - - j - J 34196: 2, 1 b - - a A c C - B E - - d D F e - g f - h H - G I - - i - - j - J 34196: 0, 1 - - b a A c C - B E - - d D F e - g f - h H - G I - - i - - j - J 34196: 2, 1 b - - c a A C - B E - - d D F e - g f - h H - G I - - i - - j - J 34196: 0, 1 - - B C a A b - c - - E F d D e - g f - h H - G I - - i - - j - J 34196: 2, 1 B - - a A C b - c - - E F d D e - g f - h H - G I - - i - - j - J 34196: 0, 1 - - B a A C b - c - - E F d D e - g f - h H - G I - - i - - j - J 34196: 2, 1 B - - C a A b - c - - E F d D e - g f - h H - G I - - i - - j - J 34196: 0, 1 - - b c a A C - B E - - F d D e - g f - h H - G I - - i - - j - J 34196: 2, 1 b - - a A c C - B E - - F d D e - g f - h H - G I - - i - - j - J 34196: 0, 1 - - b a A c C - B E - - F d D e - g f - h H - G I - - i - - j - J 34196: 2, 1 b - - c a A C - B E - - F d D e - g f - h H - G I - - i - - j - J 34196: 0, 1 - - B C a A b - c - - e d D F g - E f - h H - G I - - i - - j - J 34196: 2, 1 B - - a A C b - c - - e d D F g - E f - h H - G I - - i - - j - J 34196: 0, 1 - - B a A C b - c - - e d D F g - E f - h H - G I - - i - - j - J 34196: 2, 1 B - - C a A b - c - - e d D F g - E f - h H - G I - - i - - j - J 34196: 0, 1 - - b c a A C - B e - - d D F g - E f - h H - G I - - i - - j - J 34196: 2, 1 b - - a A c C - B e - - d D F g - E f - h H - G I - - i - - j - J 34196: 0, 1 - - b a A c C - B e - - d D F g - E f - h H - G I - - i - - j - J 34196: 2, 1 b - - c a A C - B e - - d D F g - E f - h H - G I - - i - - j - J 34196: 0, 1 - - B C a A b - c - - e F d D g - E f - h H - G I - - i - - j - J 34196: 2, 1 B - - a A C b - c - - e F d D g - E f - h H - G I - - i - - j - J 34196: 0, 1 - - B a A C b - c - - e F d D g - E f - h H - G I - - i - - j - J 34196: 2, 1 B - - C a A b - c - - e F d D g - E f - h H - G I - - i - - j - J 34196: 0, 1 - - b c a A C - B e - - F d D g - E f - h H - G I - - i - - j - J 34196: 2, 1 b - - a A c C - B e - - F d D g - E f - h H - G I - - i - - j - J 34196: 0, 1 - - b a A c C - B e - - F d D g - E f - h H - G I - - i - - j - J 34196: 2, 1 b - - c a A C - B e - - F d D g - E f - h H - G I - - i - - j - J 34196: 0, 1 - - B C a A b - c - - E d D f e - g h - F H - G I - - i - - j - J 34196: 2, 1 B - - a A C b - c - - E d D f e - g h - F H - G I - - i - - j - J 34196: 0, 1 - - B a A C b - c - - E d D f e - g h - F H - G I - - i - - j - J 34196: 2, 1 B - - C a A b - c - - E d D f e - g h - F H - G I - - i - - j - J 34196: 0, 1 - - b c a A C - B E - - d D f e - g h - F H - G I - - i - - j - J 34196: 2, 1 b - - a A c C - B E - - d D f e - g h - F H - G I - - i - - j - J 34196: 0, 1 - - b a A c C - B E - - d D f e - g h - F H - G I - - i - - j - J 34196: 2, 1 b - - c a A C - B E - - d D f e - g h - F H - G I - - i - - j - J 34196: 0, 1 - - B C a A b - c - - E f d D e - g h - F H - G I - - i - - j - J 34196: 2, 1 B - - a A C b - c - - E f d D e - g h - F H - G I - - i - - j - J 34196: 0, 1 - - B a A C b - c - - E f d D e - g h - F H - G I - - i - - j - J 34196: 2, 1 B - - C a A b - c - - E f d D e - g h - F H - G I - - i - - j - J 34196: 0, 1 - - b c a A C - B E - - f d D e - g h - F H - G I - - i - - j - J 34196: 2, 1 b - - a A c C - B E - - f d D e - g h - F H - G I - - i - - j - J 34196: 0, 1 - - b a A c C - B E - - f d D e - g h - F H - G I - - i - - j - J 34196: 2, 1 b - - c a A C - B E - - f d D e - g h - F H - G I - - i - - j - J 34196: 0, 1 - - B C a A b - c - - e d D f g - E h - F H - G I - - i - - j - J 34196: 2, 1 B - - a A C b - c - - e d D f g - E h - F H - G I - - i - - j - J 34196: 0, 1 - - B a A C b - c - - e d D f g - E h - F H - G I - - i - - j - J 34196: 2, 1 B - - C a A b - c - - e d D f g - E h - F H - G I - - i - - j - J 34196: 0, 1 - - b c a A C - B e - - d D f g - E h - F H - G I - - i - - j - J 34196: 2, 1 b - - a A c C - B e - - d D f g - E h - F H - G I - - i - - j - J 34196: 0, 1 - - b a A c C - B e - - d D f g - E h - F H - G I - - i - - j - J 34196: 2, 1 b - - c a A C - B e - - d D f g - E h - F H - G I - - i - - j - J 34196: 0, 1 - - B C a A b - c - - e f d D g - E h - F H - G I - - i - - j - J 34196: 2, 1 B - - a A C b - c - - e f d D g - E h - F H - G I - - i - - j - J 34196: 0, 1 - - B a A C b - c - - e f d D g - E h - F H - G I - - i - - j - J 34196: 2, 1 B - - C a A b - c - - e f d D g - E h - F H - G I - - i - - j - J 34196: 0, 1 - - b c a A C - B e - - f d D g - E h - F H - G I - - i - - j - J 34196: 2, 1 b - - a A c C - B e - - f d D g - E h - F H - G I - - i - - j - J 34196: 0, 1 - - b a A c C - B e - - f d D g - E h - F H - G I - - i - - j - J 34196: 2, 1 b - - c a A C - B e - - f d D g - E h - F H - G I - - i - - j - J 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. */ /* 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 #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 24 /* sets frequency of what node & move its at now */ #define NOFULLSOLUTION 7 /* lower this if you do not have the memory */ /* Note: For full solution 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. */ int debug = 0; int mode = 0; int arch = 8; int start = 0, finish = 3; #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 */ #ifdef NO_TOP_MIDDLE /* not enough gain... 5 * 20 = 100 bits instead of 120, still takes 128 bits to store */ /* May squish more by top tiles are more restricted but not enough, 88 bits min */ #define MINBITS() CEIL(log2(MAXSTACKS * (tiles + blanks) - 1)) #else #define MINBITS() CEIL(log2(MAXSTACKS * (tiles + blanks))) #endif /* max tiles to store in a unit of memory */ #define MAXNUMINUNIT() MIN(((int) (arch / MINBITS())), KINDS * tiles) #define MAXNUMINUNITX() MIN(((int) (arch / MINBITSX())), KINDS * tiles) /* min units to store all tiles */ #define MINUNITS() CEIL((double) (KINDS * tiles) / MAXNUMINUNIT()) #define MINUNITSX() CEIL((double) (KINDS * tiles) / MAXNUMINUNITX()) #define MEET_AT_MIDDLE 0 #define SINGLE 1 #define STRAIGHT 2 #define FURTHER 3 #define MODES 4 /*#define ARCH128*/ /*#define ARCH64*/ #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 #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 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)) #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 setSingle(t,p) singleTiles[t / numInUnit] |= SETBIT(t,p) #define setStartMid(t,p) startMidTiles[t / numInUnit] |= SETBIT(t,p) #define setFinishMid(t,p) finishMidTiles[t / numInUnit] |= SETBIT(t,p) /* Want to make large enough that doubling does not make much difference */ /* in the speed. Effects the number of collisions, should be a prime. */ /* If too big and its a waste of memory. */ static int hashSizes[ARRAYTWEAKS] = {31, 253, 1021, 65537, 131071, 262147, 1048573, 8388617, 259000013, 518000009}; /* Maximum number of nodes for a move. Seems to grow by a factor of 7.77 */ /* This is only for finding the number of moves... a full path is not */ /* generated. If too small will cause a segmentation fault. */ static int moveSizes[MODES][ARRAYTWEAKS] = { {2, 9, 56, 411, 3158, 23273, 180126, 1361077, 10578363, 83201059}, {0, 8, 46, 267, 1811, 11665, 85962, 653281, 4928953, 37263856}, {2, 9, 56, 411, 3158, 23273, 180126, 1361077, 10578363, 83201059}, {2, 10, 63, 412, 3158, 23273, 180126, 1361077, 10578363, 83201059}}; /* Min size to print full solution. loops * (3 * moveSize) + extra nodes */ /* The number of nodes seems to go up roughly by a factor of 18.8 - 20.0. */ static long long minSizes[MODES][ARRAYTWEAKS] = { {4, 45, 616, 11620, 218855, 4078382, 76119619, 1421709390, 26750202138LL, 502690628108LL}, {3, 16, 220, 2945, 41731, 626746, 9987583, 167748781, 3070103757LL, 56350596083LL}, {5, 82, 1504, 28827, 544976, 10338816, 194975071, 3671881192LL, 69105921539LL, 1300222252185LL}, {6, 82, 1536, 29336, 555584, 10475616, 196687040, 3710370688LL, 69798594048LL, 1312962527744LL}}; 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; static LONG *startTiles = NULL, *finishTiles = NULL; static LONG *startMidTiles = NULL, *finishMidTiles = NULL; static LONG *singleTiles = 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 blanks = 1; static int height; /* tiles + blanks */ static int areaPositions; /* MAXSTACKS * (tiles + blanks) */ 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 & 1) ppOT--; else ppOT++; *pcPOT |= (((LONG) *ppOT) << shift); if (n & 1) { 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[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)]; 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[LOOKUP(psPOT)]; while (temp != NULL) { tempsPOT = psPOT; pnodeLog = &(nodeLog[temp->node * units]); for (i = 0; i < units; i++) { if (*pnodeLog != *tempsPOT) goto CSMICONTINUE; pnodeLog++; tempsPOT++; } return TRUE; CSMICONTINUE: temp = temp->next; } return FALSE; } /* 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[LOOKUP(pcPOT)]; while (temp != NULL) { tempsPOT = pcPOT; pnodeLog = &(nodeLog[temp->node * units]); for (i = 0; i < units; i++) { if (*pnodeLog != *tempsPOT) goto CSCONTINUE; pnodeLog++; tempsPOT++; } if (debug) (void) printf("colorswap %d %d\n", move[temp->node], move[newNode]); if ((flag == -1) || (move[flag] > move[temp->node])) flag = temp->node; CSCONTINUE: temp = temp->next; } #endif #ifdef MIRRORIMAGE temp = hash[LOOKUP(pmPOT)]; while (temp != NULL) { tempsPOT = pmPOT; pnodeLog = &(nodeLog[temp->node * units]); for (i = 0; i < units; i++) { if (*pnodeLog != *tempsPOT) goto MICONTINUE; pnodeLog++; tempsPOT++; } if (debug) (void) printf("mirrorimage %d %d\n", move[temp->node], move[newNode]); if ((flag == -1) || (move[flag] > move[temp->node])) flag = temp->node; MICONTINUE: temp = temp->next; } #endif return flag; } 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[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; 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 setPositionOfTile(LONG *psPOT) { int stack, j, shift, n = 0; char *ppOT = positionOfTile; for (;;) { shift = 0; for (j = 0; j < numInUnit; j++) { *ppOT = (char) TO_LONG((((LONG) *psPOT) >> shift) & bitmask); if (debug > 1) (void) printf("positionOfTile %d %d\n", numTile(n), *ppOT); shift += bits; ppOT++; n++; if (n >= areaTiles) return; } psPOT++; } } static void printShrunkStack(LONG *psPOT) { int stack, position, j, shift, n = 0; char *ppOT = positionOfTile; char *ptOP = tileOfPosition; for (position = 0; position < height; position++) for (stack = 0; stack < MAXSTACKS; stack++) { *ptOP = EMPTY; ptOP++; } ptOP = tileOfPosition; for (;;) { shift = 0; for (j = 0; j < numInUnit; j++) { *ppOT = (char) TO_LONG((((LONG) *psPOT) >> shift) & bitmask); if (debug > 1) (void) printf("positionOfTile %d %d\n", numTile(n), *ppOT); tileOfPosition[(int) *ppOT] = numTile(n); shift += bits; ppOT++; n++; if (n >= areaTiles) goto BREAKOUT; } psPOT++; } BREAKOUT: 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 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, unit; 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 (singleTiles) (void) free((void *) singleTiles); if (!(singleTiles = (LONG *) calloc(units, sizeof (LONG)))) { memoryError("singleTiles"); } if (startMidTiles) (void) free((void *) startMidTiles); if (!(startMidTiles = (LONG *) calloc(units, sizeof (LONG)))) { memoryError("startMidTiles"); } if (finishMidTiles) (void) free((void *) finishMidTiles); if (!(finishMidTiles = (LONG *) calloc(units, sizeof (LONG)))) { memoryError("finishMidTiles"); } 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"); } for (tile = 0; tile < tiles; tile++) { setStart((2 * tile), ((tile + blanks) * MAXSTACKS)); setStart((2 * tile + 1), ((tile + blanks) * MAXSTACKS + 2)); } for (tile = 0; tile < tiles; tile++) { setFinish((2 * tile), ((tile + blanks) * MAXSTACKS + 2)); setFinish((2 * tile + 1), ((tile + blanks) * MAXSTACKS)); } for (tile = 0; tile < tiles; tile++) { setSingle((2 * tile), ((tile + blanks) * MAXSTACKS + 1)); setSingle((2 * tile + 1), ((tile + blanks) * MAXSTACKS + 2)); } if (debug) { (void) printf("single\n"); printShrunkStack(singleTiles); (void) printf("\n"); } if (tiles > 3) { setStartMid(0, (MAXSTACKS + 2)); setStartMid(1, MAXSTACKS); setStartMid(2, (2 * MAXSTACKS)); setStartMid(3, (2 * MAXSTACKS + 2)); for (tile = 2; tile < tiles - 1; tile++) { setStartMid((2 * tile), ((tile + 1) * MAXSTACKS + 2)); setStartMid((2 * tile + 1), ((tile + 1) * MAXSTACKS)); } tile = tiles - 1; setStartMid((2 * tile), ((tile + 1) * MAXSTACKS + 1)); setStartMid((2 * tile + 1), (tile * MAXSTACKS + 1)); } else { for (tile = 0; tile < tiles; tile++) { setStartMid((2 * tile), ((tile + 1) * MAXSTACKS)); setStartMid((2 * tile + 1), ((tile + 1) * MAXSTACKS + 2)); } } if (debug) { (void) printf("startMid\n"); printShrunkStack(startMidTiles); (void) printf("\n"); } if (tiles > 3) { setFinishMid(0, (MAXSTACKS + 2)); setFinishMid(1, MAXSTACKS); setFinishMid(2, (2 * MAXSTACKS)); setFinishMid(3, (2 * MAXSTACKS + 2)); for (tile = 2; tile < tiles - 1; tile++) { setFinishMid((2 * tile), ((tile + 1) * MAXSTACKS + 2)); setFinishMid((2 * tile + 1), ((tile + 1) * MAXSTACKS)); } tile = tiles - 1; setFinishMid((2 * tile), ((tile + 1) * MAXSTACKS + 1)); setFinishMid((2 * tile + 1), (tile * MAXSTACKS + 1)); } else { for (tile = 0; tile < tiles; tile++) { setFinishMid((2 * tile), ((tile + 1) * MAXSTACKS + 2)); setFinishMid((2 * tile + 1), ((tile + 1) * MAXSTACKS)); } } if (debug) { (void) printf("finishMid\n"); printShrunkStack(finishMidTiles); (void) printf("\n"); } for (unit = 0; unit < units; unit++) { if (start == -1) shrunkPositionOfTile[unit] = singleTiles[unit]; else if (start == 0) shrunkPositionOfTile[unit] = startTiles[unit]; else if (start == 1) shrunkPositionOfTile[unit] = startMidTiles[unit]; else if (start == 2) shrunkPositionOfTile[unit] = finishMidTiles[unit]; else shrunkPositionOfTile[unit] = finishTiles[unit]; } setPositionOfTile(shrunkPositionOfTile); putCurrent(currNode); if (debug) { for (unit = 0; unit < units; unit++) (void) printf("single %llx\n", singleTiles[unit]); for (unit = 0; unit < units; unit++) (void) printf("start %llx\n", startTiles[unit]); for (unit = 0; unit < units; unit++) (void) printf("finish %llx\n", finishTiles[unit]); for (unit = 0; unit < units; unit++) (void) printf("startMid %llx\n", startMidTiles[unit]); for (unit = 0; unit < units; unit++) (void) printf("finishMid %llx\n", finishMidTiles[unit]); } getCurrent(currNode); move[0] = 0; backPoss[0] = -1; /* needed for first pass */ loop = 0; hashNewIndex = 0; c = 0; /* nc = 0; fc = 0; fnc = 0; */ } static int checkSolved() { int unit; LONG *psPOT = shrunkPositionOfTile; LONG *pfT = NULL; if (finish <= 0) pfT = startTiles; else if (finish == 1) pfT = startMidTiles; else if (finish == 2) pfT = finishMidTiles; else pfT = finishTiles; 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 as 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; } /* FURTHER */ static void printLastData(int node) { if (backPath[node] > node || (node != 0 && backPath[node] == node)) { return; } getCurrent(node); if (node != 0) { (void) printf("%d: %d, %d\n", move[node], fromPoss((int) backPoss[node]), toPoss[(int) backPoss[node]]); } printStacks(); } /* FURTHER */ static void printLastHash(int index) { hashtype **oldChain = &(chain[index]); hashtype *ctemp = *oldChain; while (ctemp != NULL) { printLastData(ctemp->node); ctemp = ctemp->next; } } 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("%d: %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("%d: %d, %d\n", otherMove, 2 - toPoss[(int) backPoss[node]], 2 - fromPoss((int) backPoss[node])); printOtherData(backPath[node], otherMove + 1); } } static void printAllData(int node, int otherNode) { printData(node); (void) printf("~~~~~~~~~\n"); printOtherData(otherNode, move[node] + 1); } 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 level, int nodes) { int t; #ifdef ARCH128 arch = 128; #elif defined( ARCH64 ) arch = 64; #else arch = 8 * sizeof( bitmask ); (void) printf("Assuming %d bit architecture.\n", arch); #endif tiles = level; while (tiles < 1) tiles = getnum((char *) "Enter: # of tile pairs >"); t = tiles - 1; height = tiles + blanks; areaTiles = KINDS * tiles; areaPositions = MAXSTACKS * height; EMPTY = 2 * tiles; if (t > 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[mode][t]; else { /* 3 moves must be kept in memory to progress */ int minMem = 3 * moveSizes[mode][t]; 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[mode][t]) (void) printf( "Full path may not be printed\n"); } hashSize = hashSizes[t]; } size = inputSize; bits = MINBITS(); units = MINUNITS(); numInUnit = MAXNUMINUNIT(); if (debug) (void) printf("size %d, bits %d, units %d, numInUnit %d\n", size, 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(); } /* hashless, debug level 2 check */ 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; int otherNode; char m; int foundSolution = 0; 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())) { 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 (mode != FURTHER) { setMirrorImage(shrunkPositionOfTile, mirrorPositionOfTile); if (((mode == MEET_AT_MIDDLE) && ((otherNode = checkInHash( colorPositionOfTile, mirrorPositionOfTile)) != -1) && (!foundSolution || (foundSolution > move[newNode] + move[otherNode]))) || ((mode != MEET_AT_MIDDLE) && (checkSolved()))) { if (mode == 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); } (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] + ((mode == MEET_AT_MIDDLE) ? move[otherNode] : 0); (void) printf("total moves: %d\n", foundSolution); if (mode == STRAIGHT) 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 (move[newNode] == 12) 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[mode][tiles - 1]) (void) printf("total nodes: %lld\n", (long long) 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: \"panex [-d debugLevel] [-m mode] [-n nodesNumber] [-s start] [-f finish] numTilePairs\"\n"); (void) fprintf(stderr, "\tmode:\t0 meet in middle (default)\n"); (void) fprintf(stderr, "\t\t1 match single stack move\n"); (void) fprintf(stderr, "\t\t2 match finish point\n"); (void) fprintf(stderr, "\t\t3 find farthest point\n"); (void) fprintf(stderr, "\tstart:\tposition to start -1-3, default 0\n"); (void) fprintf(stderr, "\tfinish:\tposition to finish 0-3, default 3\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 'd': if (argc > 1) { argc--; argv++; debug = atoi(argv[0]); break; } else { usage(); } case 'f': if (argc > 1) { argc--; argv++; finish = atoi(argv[0]); break; } else { usage(); } case 'm': if (argc > 1) { argc--; argv++; mode = atoi(argv[0]); if (mode < 0 || mode >= MODES) mode = MEET_AT_MIDDLE; break; } else { usage(); } case 'n': if (argc > 1) { argc--; argv++; nodes = atoi(argv[0]); break; } else { usage(); } case 's': if (argc > 1) { argc--; argv++; start = 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 }