View unanswered posts  View active topics
Author 
Message 
Brandon Enright

Post subject: Re: Rainbow Nautilus Solution Posted: Fri Jan 25, 2013 12:59 am 

Joined: Thu Dec 31, 2009 8:54 pm Location: Bay Area, California

quickfur wrote: bmenrigh wrote: as it is, I'm having trouble figuring out how to get to the 13twist state. The 13twist state requires that the middle layer not be solved. Without the middle layer the farthest you can get is 12 twists away. You have to arrange the puzzle such that the last twist performed puts the middle layer in a nonsolved state.
_________________ Prior to using my real name I posted under the account named bmenrigh.


Top 


Brandon Enright

Post subject: Re: Rainbow Nautilus Solution Posted: Fri Jan 25, 2013 3:33 am 

Joined: Thu Dec 31, 2009 8:54 pm Location: Bay Area, California

A few days ago it occurred to me that because the Rainbow Nautilus is a bandaged puzzle, it's states don't form a group. For a puzzle that does form a group like the Rubik's cube, if the farthest state from solve is 20 moves then the farthest distance from any state to any other state is 20 moves. That is NOT the case on the Rainbow Nautilus. Although the farthest state from solved (when including the middle layer) is 13 moves, the farthest distance between two states is actually greater. To measure this I decided to compute the distance matrix for all 978 states. The farthest distance between a pair of states is 22 moves. There are 320 unique pairs of states with this distance. Here is the distance matrix as an image: Attachment:
rbow_naut_dist_m.png [ 25.38 KiB  Viewed 2521 times ]
The columns + rows order is the same as the adjacency matrix I posted earlier. Solid black are the states with distance 0 (only the diagonal line for obvious reasons). Nearly black are the states with distance 1 (the adjacency matrix) White are the states with distance 22. Notice that the farthest distance states also happen to be much farther from solved than other states. In fact, of the 320 farthest pairs, 256 of the pairs are each 13 moves from solved and another 64 of them are each 12 moves from solved. Here is a table of the count for each distance for unique pairs of states: Code: 0 978 1 4032 2 16101 3 25464 4 46280 5 37632 6 41680 7 36064 8 48720 9 35568 10 35980 11 23936 12 27720 13 21568 14 26480 15 18112 16 14160 17 6336 18 5840 19 3072 20 1920 21 768 22 320
So there are 48720 distinct pairs of states (order doesn't matter) that are 8 moves from each other. Edit: I should mention that if you "shape mod" one of the farthest states into a solved state then god's number for the puzzle would be 22.
_________________ Prior to using my real name I posted under the account named bmenrigh.


Top 


Andrea

Post subject: Re: Rainbow Nautilus Solution Posted: Fri Jan 25, 2013 6:32 am 

Joined: Wed Apr 13, 2011 8:37 am Location: Germany

Hi Brandon, thanks for your for the changes in the program. I run it and get the correct results. My simulation and calculation ignore the middle layer. In the new table , each state has many more connectors.
Cheers, Andrea


Top 


Brandon Enright

Post subject: Re: Rainbow Nautilus Solution Posted: Fri Jan 25, 2013 11:49 am 

Joined: Thu Dec 31, 2009 8:54 pm Location: Bay Area, California

Since the "no middle" version of this puzzle is simpler and just as interesting and since the middle doesn't actually affect what states are reachable for the top and bottom layers, here is the adjacency and distance matrix for the puzzle without a middle layer: Attachment:
rbow_naut_no_mid_adj_m.png [ 1.09 KiB  Viewed 2476 times ]
Attachment:
rbow_naut_no_mid_dist_m.png [ 6.16 KiB  Viewed 2476 times ]
When ignoring the middle layer, the farthest distance between a pair of states is 21 moves (where a move is a flip).
_________________ Prior to using my real name I posted under the account named bmenrigh.


Top 


themathkid

Post subject: Re: Rainbow Nautilus Solution Posted: Fri Jan 25, 2013 2:43 pm 

Joined: Sat Sep 15, 2012 7:42 am


Top 


Brandon Enright

Post subject: Re: Rainbow Nautilus Solution Posted: Fri Jan 25, 2013 5:26 pm 

Joined: Thu Dec 31, 2009 8:54 pm Location: Bay Area, California

themathkid wrote: What causes the prominent stripe patterns on the grayscale adjacency matrix? Good question. I'll attempt to answer There are two things that make the stripe + block pattern stand out more than you'd otherwise expect. The first is an artifact of how states are found with BFS (breadthfirstsearch) and the second is that the bandaging on this puzzle makes states "farther away" than normal. To understand BFS imagine a tree like so: Attachment:
rbow_exp_crappy_tree.png [ 9.14 KiB  Viewed 2428 times ]
The way BFS works is that it starts at the top of the tree (solved state) which is the top dot. The first step is to find all of the direct children of that dot. That will find the 6 dots in a row below the top one. The second step it will find the 4 dots in a row below that. Then in the third step it will find the 10 dots in a row at the bottom. That is, a single "row" of the tree is found at each step. These rows represent how many moves away from the solved state they are. The bottom 10 dots are all 3 moves away from the solved state. BFS doesn't find all of the dots in a row at the same time though. They will be found in groups. For example, the red circle around three states are three states that are all adjacent to their parent dot. The same is true of the group of states circled in blue. It's easy to see all of the red dots are close together and all of the blue dots are close together. It should also be easy to see that all of the red dots are far away from the blue ones, and viceversa. To illustrate how states are found in groups, I have overlayed the adjacency matrix graph onto the distance matrix graph and zoomed into the upperleft corner: Attachment:
rbow_exp_overlay_no_color.png [ 5 KiB  Viewed 2428 times ]
Because the graph is symmetrical about the diagonal, all of the vertical lines that are below the diagonal are the SAME as the horizontal lines above the diagonal. They represent the same states. All of the vertical lines below the diagonal are states that were found together in one group just like the red and blue circles in my tree above. So, taking the red and blue groups in the tree example, here are the regions they'd represent on the distance matrix: Attachment:
rbow_exp_overlay_with_color.png [ 5.98 KiB  Viewed 2428 times ]
Remember that dark regions mean closer together and light regions mean farther apart. If you look carefully, when the "red" region crosses itself, it forms a dark square which shows that all of the states that were found together are close together. The same is true of the blue. But when you look at red and blue crossing each other, because they were found on opposite sides of the state tree, they form a lighter color rectangle. This effect is especially apparent in the lowerright corner of the fullsize distance matrix where BFS finds groups that are very far down on the state tree and on opposite sides so they form a checkerboard of alternating close and far groups. If the Rainbow Nautilus weren't such a bandaged puzzle there would be shortcuts between the states so that the shortest path wouldn't involve going up the tree and then back down the other side. That is, BFS forms the stripes and the bandaging exaggerates the contrast in the stripes.
_________________ Prior to using my real name I posted under the account named bmenrigh.


Top 


Jeffery Mewtamer

Post subject: Re: Rainbow Nautilus Solution Posted: Sat Jan 26, 2013 2:46 am 

Joined: Sun Nov 23, 2008 2:18 am

In regards to this analysis of the distances between any two states, I have to ask: 1. Is it a universal property of Doctrinaire puzzles that the maximum distance between any two states is equal to God's Number? 2. Is it a universal property of bandaged puzzles that the maximum distance is greater than God's number? 3. If the answer to 2 is no, does this property(whether or not the max distance is > or = God's number) divide bandaged puzzles into meaningful subclasses.
A few other things I was wondering about this puzzle: I would imagine that the fully unbanaged(36 wedges of 10 degrees each) would be fairly boring from an analysis of states and their connections, but what about undanaging in 20 and 30 degree pieces(40 is split into 2 20s, 50 is split into a 20 and a 30, 60 is split into 2 30s, 70 is split into 2 20s and a 30, and 90 is split into 3 30s)?
Also, it is obvious that the number of states reachable with legal moves is far smaller than the number of states into which the peices can be assembled. Keeping to seven pieces in both top and bottom layer, the are 7! ways of ordering the pieces in each layer, and 2^7 ways of swapping a piece with its chiral counterpart, give 7!*7!*2^7 as a lower bound on number of assembliable states, though the actual number is higher due to being able to swap any subset of pieces with another subset whos angles have the same sum. A natural extension to this train of thought is ask how many distinct universes these assembled states fall into(a universe being the subset of states which are connexted via legal moves, i.e. you have already analysed the universe containing the assembled state that has both layers containing seven pieces in increasing order of angle size and divided based on common chirality), but the questiosn that I find most interesting are: 1. Does the bandaging cause the various universes to be of differing sizes? 2. Assuming the answer to 1 is true, can one find the universe with the most and fewest states. 3. Does their exist an assembled state that renders the puzzle immobile, i.e. is there a universe of size 1?
_________________ Just so you know, I am blind.
I pledge allegiance to the whole of humanity, and to the world in which we live: one people under the heavens, indivisible, with Liberty and Equality for all.
My Shapeways Shop


Top 


Brandon Enright

Post subject: Re: Rainbow Nautilus Solution Posted: Sun Jan 27, 2013 12:36 am 

Joined: Thu Dec 31, 2009 8:54 pm Location: Bay Area, California

Jeffery Mewtamer wrote: In regards to this analysis of the distances between any two states, I have to ask: 1. Is it a universal property of Doctrinaire puzzles that the maximum distance between any two states is equal to God's Number? It is true for all puzzles with states that form a group. Is it a universal property that all doctrinaire puzzles form a group? I think so. Perhaps Oskar will come along and do his best to prove me wrong with some crazy new puzzle. Briefly, the logic / proof that god's number is equal to the maximum distance between any two states comes from the required properties of a group. A group has an identity element I and a bunch of other elements I'll call e1, e2, ... en. A form of "multiplication" is defined where en * em == eo. That is applying one state to another produces yet another state also in the group. All states have inverses so e1 * e1' == I. When we talk about the number of moves for a state, we really mean there are a set of generators that will take you from I to some state, en. So if you want to get from state e1 to state e2, you could do it by going through the identity like so: e1 * e1' * e2 == e2. We know we've done fewer than 2 * god's number of moves since from I we know both e1' and e2 use no more than god's number of moves. The important point though is that if we multiple e1' and e2 we get some other state we'll call em and so e1 * em == e2. Since em is also yet another state that takes no more than god's number of moves to achieve, no two states can ever be more than god's number of moves away. Jeffery Mewtamer wrote: 2. Is it a universal property of bandaged puzzles that the maximum distance is greater than God's number? No. The first counterexample that comes to mind is taking a pair of states from the Rainbow Nautilus that are the farthest away (22 moves) and shapemoding the puzzle so that one of those states is the solved position. Then to get to the other state would require 22 moves and 22 would be god's number. But since we know no other pair could exceed 22 moves (because a shape mod doesn't modify the reachable states) then god's number would be the maximum. Of course I'm assuming that the shape mod preserves the properties of each piece such that orientation and position are still distinguishable. Jeffery Mewtamer wrote: 3. If the answer to 2 is no, does this property(whether or not the max distance is > or = God's number) divide bandaged puzzles into meaningful subclasses. I don't follow you here. Jeffery Mewtamer wrote: A few other things I was wondering about this puzzle: I would imagine that the fully unbanaged(36 wedges of 10 degrees each) would be fairly boring from an analysis of states and their connections, but what about undanaging in 20 and 30 degree pieces(40 is split into 2 20s, 50 is split into a 20 and a 30, 60 is split into 2 30s, 70 is split into 2 20s and a 30, and 90 is split into 3 30s)? Fully unbandaging the puzzle would make it easy to count the total number of states and say a lot of things that only a computer can answer for the Rainbow Nautilus. It would also have too many states to fully enumerate and determining god's number computationally would be out of reach. Partially unbandaging the puzzle by slicing some of the pieces could cause a huge explosion in the number of states. Andrea's code is better suited for those sorts of computations because her code is faster and more memory efficient. My code does everything (slowly) and could probably be used to answer questions about kitchen sinks too. Jeffery Mewtamer wrote: Also, it is obvious that the number of states reachable with legal moves is far smaller than the number of states into which the peices can be assembled. Keeping to seven pieces in both top and bottom layer, the are 7! ways of ordering the pieces in each layer, and 2^7 ways of swapping a piece with its chiral counterpart, give 7!*7!*2^7 as a lower bound on number of assembliable states, though the actual number is higher due to being able to swap any subset of pieces with another subset whos angles have the same sum. A natural extension to this train of thought is ask how many distinct universes these assembled states fall into(a universe being the subset of states which are connexted via legal moves, i.e. you have already analysed the universe containing the assembled state that has both layers containing seven pieces in increasing order of angle size and divided based on common chirality), but the questiosn that I find most interesting are: 1. Does the bandaging cause the various universes to be of differing sizes? 2. Assuming the answer to 1 is true, can one find the universe with the most and fewest states. 3. Does their exist an assembled state that renders the puzzle immobile, i.e. is there a universe of size 1? If this puzzle formed a group the appropriate term for these "different universes" would be "orbits" but since it doesn't, I think universes is good enough. First, I'm not sure if there is a way to assemble the puzzle so that no flip move is possible. If you restricted assembly to using all 7 pieces on the top only on the top and all 7 on the bottom only on the bottom then I doubt you can restrict the puzzle to a single state. If you allowed any subset of the 14 for the top and bottom I suspect there are configurations where there isn't a straightline dividing both top and bottom into 180 degree halves. In that case the puzzle would have only one state. Allowing for arbitrary reassembly almost certainly had a big effect on the total number of states. I could probably do some random reassembly simulations to get an idea of the range of possibilities. First I want to change my code to be able to handle a 10degree slice though so I may not get around to this.
_________________ Prior to using my real name I posted under the account named bmenrigh.


Top 


Jeffery Mewtamer

Post subject: Re: Rainbow Nautilus Solution Posted: Sun Jan 27, 2013 6:45 am 

Joined: Sun Nov 23, 2008 2:18 am

Thinking about it some more, while the states of a bandaged puzzle are distinguishable even without stickers or shapeshifting, there is not "natuarl" solved state for a bandaged puzzle. You could take a bandaged cube without stickers and choose any arbitary state to sticker as the solution. Thus, the better question is probably: Do all bandaged puzzles have a variable God's number depending on which state is choosen for the solution?
Considering the link between puzzles and group theory, a few questions that arise: 1. Since it can be shown that any group has a God's number equal to the greatest distance between any two states, am I correct to assume this means all Groups have fixed God's Number? 2. Do all nonGroups have variable God's Number?
Also, I believe I have found a large number of assembled states that render the Nautilus into a fixed state.
Take a top layer consisting of six pieces in the following order: 902090604060 If I have added correctly, this symetrical arrangement of angles has no sets of consecutive angles adding to 180. Though this is not a unique state, as the 2 90degree pieces can be swapped, the 2 60degree pieces can be swapped, the 20 and 40 pieces can be swapped with their chiral counterparts from the bottom layer, and even swapping the 20 and 40 pieces maintains the unscamblable property. Combine these 2^5 variants on the top layer with 3 positions for the middle layer, and 8! permutations of the pieces in the bottom layer, and you have 3,870,720 ways of assembling the Nautilus that render it unscramblable, and I have my doubts that this is the is all such states.
_________________ Just so you know, I am blind.
I pledge allegiance to the whole of humanity, and to the world in which we live: one people under the heavens, indivisible, with Liberty and Equality for all.
My Shapeways Shop


Top 


themathkid

Post subject: Re: Rainbow Nautilus Solution Posted: Sun Jan 27, 2013 7:07 am 

Joined: Sat Sep 15, 2012 7:42 am

bmenrigh wrote: First, I'm not sure if there is a way to assemble the puzzle so that no flip move is possible. If you restricted assembly to using all 7 pieces on the top only on the top and all 7 on the bottom only on the bottom then I doubt you can restrict the puzzle to a single state. If you allowed any subset of the 14 for the top and bottom I suspect there are configurations where there isn't a straightline dividing both top and bottom into 180 degree halves. In that case the puzzle would have only one state. Jeffery Mewtamer wrote: Also, I believe I have found a large number of assembled states that render the Nautilus into a fixed state.
Take a top layer consisting of six pieces in the following order: 902090604060 If I have added correctly, this symetrical arrangement of angles has no sets of consecutive angles adding to 180. Though this is not a unique state, as the 2 90degree pieces can be swapped, the 2 60degree pieces can be swapped, the 20 and 40 pieces can be swapped with their chiral counterparts from the bottom layer, and even swapping the 20 and 40 pieces maintains the unscamblable property. Combine these 2^5 variants on the top layer with 3 positions for the middle layer, and 8! permutations of the pieces in the bottom layer, and you have 3,870,720 ways of assembling the Nautilus that render it unscramblable, and I have my doubts that this is the is all such states. You don't even need to use pieces from the both layer to achieve this. You can actually create a puzzle that is impossible to turn just by permuting the pieces on ONE layer. Example: 90203060407050.
_________________ Call me Seth
Crazy2Face & Crazy3Face Puzzle Spreadsheet Named 3x3x3 Bandaging Patterns


Top 


Brandon Enright

Post subject: Re: Rainbow Nautilus Solution Posted: Mon Jan 28, 2013 6:02 pm 

Joined: Thu Dec 31, 2009 8:54 pm Location: Bay Area, California

Jared wrote: timselkirk wrote: It would be interesting to see further analysis using the 10 degree piece, and to see ifsuch a piece would be physically workeable on a larger puzzle. See? Don't do it for me, do it for the inventor! I tweaked my code to be able to handle arbitrary wedge configurations including the original design with 10 through 80 degree wedges. The massproduced Rainbow Nautilus has 978 states which is really just 326 different states for the top and bottom layer times the 3 middle layer states. The state of the top layer is directly tied to the state of the bottom layer and there is no way to separate them. When you split the 90 degree wedge into a 10 degree and 80 degree wedge everything changes. The number of possible layer configurations for the top and bottom layers increases dramatically and the top and bottom layers can be changed independently of each other. This means the original design has millions of states and a "god's number" of at least 17. My program might not be up to the task of enumerating all of the states. Even if the computer I'm using doesn't run out of memory, it could take weeks to finish. I'll probably have to write a new program with speed and memory efficiency in mind if I'm going to be able to provide a complete analysis of the puzzle. So don't think I'm ignoring the question. It just turns out the answer is nontrivial Edit: The branchingfactor for each depth is very close to 2 and the number of states reachable at each depth for the version with a middle layer is almost exactly 3x the number of states when ignoring the middle layer. "god's number" will be O(log2(total states)) however I don't know how to estimate the total number of states because of the bandaging.
_________________ Prior to using my real name I posted under the account named bmenrigh.


Top 


Jared

Post subject: Re: Rainbow Nautilus Solution Posted: Tue Jan 29, 2013 2:15 pm 

Joined: Mon Aug 18, 2008 10:16 pm Location: Somewhere Else

bmenrigh wrote: When you split the 90 degree wedge into a 10 degree and 80 degree wedge everything changes. The number of possible layer configurations for the top and bottom layers increases dramatically and the top and bottom layers can be changed independently of each other. This makes me unbelievably happy!


Top 


quickfur

Post subject: Re: Rainbow Nautilus Solution Posted: Tue Jan 29, 2013 3:10 pm 

Joined: Wed Jan 14, 2009 6:37 pm Location: The Great White North

Jared wrote: bmenrigh wrote: When you split the 90 degree wedge into a 10 degree and 80 degree wedge everything changes. The number of possible layer configurations for the top and bottom layers increases dramatically and the top and bottom layers can be changed independently of each other. This makes me unbelievably happy! Yeah! Now I want this modified Nautilus that is much easier to scramble!


Top 


Brandon Enright

Post subject: Re: Rainbow Nautilus Solution Posted: Tue Jan 29, 2013 3:27 pm 

Joined: Thu Dec 31, 2009 8:54 pm Location: Bay Area, California

quickfur wrote: Jared wrote: bmenrigh wrote: When you split the 90 degree wedge into a 10 degree and 80 degree wedge everything changes. The number of possible layer configurations for the top and bottom layers increases dramatically and the top and bottom layers can be changed independently of each other. This makes me unbelievably happy! Yeah! Now I want this modified Nautilus that is much easier to scramble! My biggest concern with a very scrambleable version of the Rainbow Nautilus is that there may not be a reasonable method to solve it. I'm expecting it to be much worse than the Square1. I made major improvements to the speed of my program last night and now I'm running into memory issues. For the version WITHOUT a middle layer, this is what I have so far: Code: Starting with 1 state at depth 0 Added 16 states at depth 1 Added 61 states at depth 2 Added 130 states at depth 3 Added 194 states at depth 4 Added 284 states at depth 5 Added 578 states at depth 6 Added 986 states at depth 7 Added 1832 states at depth 8 Added 3464 states at depth 9 Added 6672 states at depth 10 Added 14716 states at depth 11 Added 31604 states at depth 12 Added 66380 states at depth 13 Added 132754 states at depth 14 Added 270050 states at depth 15 Added 546234 states at depth 16 Added 1099600 states at depth 17 Added 2197188 states at depth 18 Added 4391118 states at depth 19 Added 8771318 states at depth 20 Added 17513904 states at depth 21 Added 34770838 states at depth 22 [... out of memory ...]
The version with a middle layer has approximately 3x as many states at each depth. After chatting with GuiltyBystander, he pointed out there is a way to trade space usage for time by using a different search algorithm ( https://en.wikipedia.org/wiki/Iterative ... rst_search). I'm currently using BFS which I've incorrectly been calling "iterative deepening". There are still some details I need to work out.
_________________ Prior to using my real name I posted under the account named bmenrigh.


Top 


quickfur

Post subject: Re: Rainbow Nautilus Solution Posted: Tue Jan 29, 2013 8:48 pm 

Joined: Wed Jan 14, 2009 6:37 pm Location: The Great White North

bmenrigh wrote: [...] My biggest concern with a very scrambleable version of the Rainbow Nautilus is that there may not be a reasonable method to solve it. I'm expecting it to be much worse than the Square1.[...] But that's what makes it fun! When I first saw the Rainbow Nautilus, I was eager to buy it because I was expecting a really pathological solution method. I was a bit disappointed that the puzzle turned out to be so simple. (It's still a beautiful puzzle, though!) A modified Rainbow Nautilus with a completely crazy solution method is right up my alley.


Top 


Jeffery Mewtamer

Post subject: Re: Rainbow Nautilus Solution Posted: Wed Jan 30, 2013 1:50 am 

Joined: Sun Nov 23, 2008 2:18 am

Who would have thought that such a small change to the physical pieces would result in such a HUGE change in the puzzle's state graph. Simply dividing the 90 degree wedge into 10 and 80 really causes this puzzle to breaks its restrictions.
_________________ Just so you know, I am blind.
I pledge allegiance to the whole of humanity, and to the world in which we live: one people under the heavens, indivisible, with Liberty and Equality for all.
My Shapeways Shop


Top 


Brandon Enright

Post subject: Re: Rainbow Nautilus Solution Posted: Sat Feb 02, 2013 11:16 am 

Joined: Thu Dec 31, 2009 8:54 pm Location: Bay Area, California

I rewrote the program in C to save memory and go faster. I'm not doing enough memory saving though so with a machine with 64GB of RAM I'm only able to get two more depths: Code: Found 68752682 states at depth 23 Found 134996382 states at depth 24 Right now each state takes up 118 bytes. I'm going to have to make every bit count. I should be able to get down to 8 bytes which should get me 3 more depths down the search tree. After that I'll have to use files. Edit: I cut states down much smaller: Code: Found 261614750 states at depth 25 Found 496738140 states at depth 26
However I'll only be able to get to 27 or 28 with my current memory limits. To get beyond that either requires disk usage or very smart encoding of states. A smart encoding of states would result in much faster code.
_________________ Prior to using my real name I posted under the account named bmenrigh.
Last edited by Brandon Enright on Tue Feb 05, 2013 2:41 am, edited 1 time in total.


Top 


quickfur

Post subject: Re: Rainbow Nautilus Solution Posted: Mon Feb 04, 2013 11:05 am 

Joined: Wed Jan 14, 2009 6:37 pm Location: The Great White North

bmenrigh wrote: I rewrote the program in C to save memory and go faster. I'm not doing enough memory saving though so with a machine with 64GB of RAM I'm only able to get two more depths: Code: Found 68752682 states at depth 23 Found 134996382 states at depth 24 Right now each state takes up 118 bytes. I'm going to have to make every bit count. I should be able to get down to 8 bytes which should get me 3 more depths down the search tree. After that I'll have to use files. I wonder, if there's a way to prune the search tree by some sort of symmetry somehow? E.g., if state X leads to states Y1, Y2, Y3, but Y1, Y2, Y3 are equivalent to each other under some kind of bijective mapping, then you really only need to store Y1 (and subsequent states leading from it). That way, you can reduce the breadth of the search tree somewhat, and hopefully make it more tractable memory (and time)wise.


Top 


GuiltyBystander

Post subject: Re: Rainbow Nautilus Solution Posted: Thu Feb 07, 2013 9:38 am 

Joined: Wed May 13, 2009 4:58 pm Location: Vancouver, Washington

After watching this thread and listening to Brandon talk about the problem in IRC, I decided to take a stab at it a few days ago. Took a little while and a few attempts, but I finally got it working on the boring nautilus and my answers lined up with Brandonâ€™s. My raw state representation (~25 bytes) is more efficient than Brandon's (108 bytes), but I only have 24GB or RAM and I'm using java which is less efficient about pointers and some memory management so first attempt only got to depth 2324. The next step was to compress the complex state down to a single 8 byte number. Along with a few change to which data structures I was using, I managed to get to depth 25. But Brandon and I both realize that even with our highest feasible compression wouldn't be enough to fit in his machine's RAM. We were beginning to plan and dread writing to the terribly slow hard disk. I knew I had to find a different way. My new plan was to find a way to enumerate all possible states and use a single bit to say if that state is connected to the solution or not. The problem is that my best compression would mean I need 15! bits, which is 163.5GB. So that's a problem. I had to find a way eliminate some of these states. My next subtask would be to try and count the number of ways to just assemble the puzzle. With a bit of trickery, I found that number is 36,346,060,800. With even more trickery and a bit of voodoo I managed to find a way to construct a unique puzzle from a number [0, 36346060800). This mean a bit for each state would only take up 4.5 GB making it within the realm of possibility. Unfortunately my first incarnation of this compression was horribly slow, but I manage to speed it up enough that I was happy to run it. I can get more technical on this compression if anyone is really interested. At this point Brandon had finished his latest version and had beat my previous record and reached depth 26. So at Feb 4, 11pm I set my program off running to catch up. Brandon had the speed advantage and a head start, but his would soon feel the claustrophobic effects of limited RAM. Mine required 15 GB, but that was all it needed. In the morning I had reached depth 29 and Brandon conceded after I conquered a few more layers. I was curious how many of 36 billion states were valid. Of course all of those states can be reached with a screwdriver, but surely some of them were would have no valid turns to them right? So while my other program was doing the real work, I made a 2nd program to try and survey the 36 billion. I quickly found that nearly 60% of all states had no valid moves. This was great news because it meant our search would terminate earlier than we first thought. There are only about 15 billion states had even the possibility of being reached. Full results of the survey are below. For the next day and a half I could predict when the next depth would finish and we would both sit on the edge of our seats waiting for the results. While we waiting, we would try to guess the branching factor and the god number of the puzzle. For most of the depths, the average branching factor was about 2. Early on we thought the god number might be as high as 30. After we got our latest versions going, we saw it could easily hit 3135. When we finally hit the peak at 32, we figured it would quickly drop off like most puzzles do and maybe sputter to a stop at 40. But it kept going... At around 35, Brandon had been making some pretty accurate prediction using some 4th order polynomial fits, but they had some odd quirks to them that we didn't expect/understand. I tried plotting depth vs. branching factor and started noticing something unusual. The new branching factor was asymptotically approaching 0.5 which happens to be the inverse of what it had been for half the puzzle so far. It was like there was another solve state on the other side with a 2x branching factor and we were exploring it backwards. We never dreamed the counts would look they way they did in the end. Brandon has a few more graphs I'm sure he'll post. Here's my favorite which shows how the state counts are nearly mirrored. Attachment:
states.png [ 6.42 KiB  Viewed 2002 times ]
You'll notice I have half the states as Brandon. That's because I "removed" a "symmetry." I put it in quotes because in my mind, Brandon had added extra redundant state. This also doesnâ€™t include the boring middle layer. Code: Depth: 0 States: 1 Depth: 1 States: 8 Time: 0.004 secs Depth: 2 States: 30 Time: 2.980 secs Depth: 3 States: 65 Time: 4.014 secs Depth: 4 States: 97 Time: 5.205 secs Depth: 5 States: 142 Time: 6.901 secs Depth: 6 States: 289 Time: 9.084 secs Depth: 7 States: 493 Time: 12.011 secs Depth: 8 States: 916 Time: 15.296 secs Depth: 9 States: 1732 Time: 19.069 secs Depth: 10 States: 3336 Time: 23.223 secs Depth: 11 States: 7358 Time: 27.595 secs Depth: 12 States: 15802 Time: 32.209 secs Depth: 13 States: 33190 Time: 36.981 secs Depth: 14 States: 66377 Time: 41.965 secs Depth: 15 States: 135025 Time: 47.311 secs Depth: 16 States: 273117 Time: 53.320 secs Depth: 17 States: 549800 Time: 61.368 secs Depth: 18 States: 1098594 Time: 72.517 secs Depth: 19 States: 2195559 Time: 89.728 secs Depth: 20 States: 4385659 Time: 119.609 secs Depth: 21 States: 8756952 Time: 174.181 secs Depth: 22 States: 17385419 Time: 279.785 secs Depth: 23 States: 34376341 Time: 485.209 secs Depth: 24 States: 67498191 Time: 880.727 secs Depth: 25 States: 130807375 Time: 1629.431 secs Depth: 26 States: 248369070 Time: 3259.869 secs Depth: 27 States: 456374712 Time: 6111.764 secs Depth: 28 States: 795897596 Time: 11345.480 secs Depth: 29 States: 1282299554 Time: 20642.498 secs Depth: 30 States: 1844213378 Time: 35356.627 secs Depth: 31 States: 2277968724 Time: 56246.249 secs Depth: 32 States: 2331533621 Time: 82080.951 secs Depth: 33 States: 1935175339 Time: 109618.968 secs Depth: 34 States: 1311873044 Time: 127410.676 secs Depth: 35 States: 758332585 Time: 138490.341 secs Depth: 36 States: 398251084 Time: 144570.194 secs Depth: 37 States: 200888899 Time: 147473.355 secs Depth: 38 States: 100367992 Time: 148928.933 secs Depth: 39 States: 50187942 Time: 149647.722 secs Depth: 40 States: 25268222 Time: 150012.476 secs Depth: 41 States: 12838950 Time: 150200.073 secs Depth: 42 States: 6591588 Time: 150298.098 secs Depth: 43 States: 3398560 Time: 150351.668 secs Depth: 44 States: 1762886 Time: 150381.937 secs Depth: 45 States: 926124 Time: 150401.094 secs Depth: 46 States: 496436 Time: 150412.535 secs Depth: 47 States: 268654 Time: 150421.243 secs Depth: 48 States: 145376 Time: 150427.766 secs Depth: 49 States: 74484 Time: 150433.652 secs Depth: 50 States: 36968 Time: 150439.023 secs Depth: 51 States: 18300 Time: 150444.167 secs Depth: 52 States: 8560 Time: 150449.129 secs Depth: 53 States: 3488 Time: 150454.417 secs Depth: 54 States: 1356 Time: 150459.050 secs Depth: 55 States: 580 Time: 150462.897 secs Depth: 56 States: 224 Time: 150465.461 secs Depth: 57 States: 44 Time: 150467.377 secs Depth: 58 States: 0 Time: 150468.623 secs Total: 14311166208 Here's the branch survey results. Code: branches states 0 21254727168 2 7837443584 4 5710360576 6 520886784 8 884349440 10 82944 12 129994752 16 2095104 18 5721088 20 27648 24 353280 30 9216 32 9216
Future work: Brandon and I have a few plans on what to do next. First thing we want to know is what those 44 states look like. We'll probably convert my code to some faster C++ and multithread it so we get results it out in a couple hours rather than days. We'd also love to figure out what the shape of the connected graph is. Unfortunately, there's way to many states to get an of accurate picture. Perhaps we'll try some other initial settings and see what the god number is to reach them. I'd like to thank Brandon for his help. He let me bounce my ideas off him and he ran earlier versions of my program on his monster of a machine. I couldn't have done this without him.
_________________ Real name: Landon Kryger


Top 


Jared

Post subject: Re: Rainbow Nautilus Solution Posted: Thu Feb 07, 2013 2:27 pm 

Joined: Mon Aug 18, 2008 10:16 pm Location: Somewhere Else

I think I might have an idea for making the original puzzle possible  or at least making an equivalent version. If you make a circular grooved middle layer that can hold a ring of 36 marbles on two sides, and then somehow bandage the marbles together in chains, it would have to be a big puzzle but it could work. Here's what gave me the idea: http://www.twistypuzzles.com/cgibin/pu ... ?pkey=2880


Top 


Boris

Post subject: Re: Rainbow Nautilus Solution Posted: Thu Apr 10, 2014 12:13 pm 

Joined: Wed Mar 12, 2014 5:16 am


Top 


Who is online 
Users browsing this forum: Google [Bot], perfredlund and 10 guests 

You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot post attachments in this forum


