Online since 2002. Over 3300 puzzles, 2600 worldwide members, and 270,000 messages.

TwistyPuzzles.com Forum

It is currently Wed Jul 23, 2014 4:06 pm

All times are UTC - 5 hours



Post new topic Reply to topic  [ 71 posts ]  Go to page Previous  1, 2
Author Message
 Post subject: Re: Rainbow Nautilus Solution
PostPosted: Fri Jan 25, 2013 12:59 am 
Offline
User avatar

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 13-twist state.
The 13-twist 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 non-solved state.

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: Rainbow Nautilus Solution
PostPosted: Fri Jan 25, 2013 3:33 am 
Offline
User avatar

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
rbow_naut_dist_m.png [ 25.38 KiB | Viewed 2512 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
 Profile  
 
 Post subject: Re: Rainbow Nautilus Solution
PostPosted: Fri Jan 25, 2013 6:32 am 
Offline
User avatar

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
 Profile  
 
 Post subject: Re: Rainbow Nautilus Solution
PostPosted: Fri Jan 25, 2013 11:49 am 
Offline
User avatar

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
rbow_naut_no_mid_adj_m.png [ 1.09 KiB | Viewed 2467 times ]
Attachment:
rbow_naut_no_mid_dist_m.png
rbow_naut_no_mid_dist_m.png [ 6.16 KiB | Viewed 2467 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
 Profile  
 
 Post subject: Re: Rainbow Nautilus Solution
PostPosted: Fri Jan 25, 2013 2:43 pm 
Offline
User avatar

Joined: Sat Sep 15, 2012 7:42 am
What causes the prominent stripe patterns on the grayscale adjacency matrix?

_________________
Call me Seth :)

Crazy2Face & Crazy3Face Puzzle Spreadsheet
Named 3x3x3 Bandaging Patterns


Top
 Profile  
 
 Post subject: Re: Rainbow Nautilus Solution
PostPosted: Fri Jan 25, 2013 5:26 pm 
Offline
User avatar

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 :D

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 (breadth-first-search) 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
rbow_exp_crappy_tree.png [ 9.14 KiB | Viewed 2419 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 vice-versa.

To illustrate how states are found in groups, I have overlayed the adjacency matrix graph onto the distance matrix graph and zoomed into the upper-left corner:
Attachment:
rbow_exp_overlay_no_color.png
rbow_exp_overlay_no_color.png [ 5 KiB | Viewed 2419 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
rbow_exp_overlay_with_color.png [ 5.98 KiB | Viewed 2419 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 lower-right corner of the full-size 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
 Profile  
 
 Post subject: Re: Rainbow Nautilus Solution
PostPosted: Sat Jan 26, 2013 2:46 am 
Offline

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 sub-set 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
 Profile  
 
 Post subject: Re: Rainbow Nautilus Solution
PostPosted: Sun Jan 27, 2013 12:36 am 
Offline
User avatar

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 shape-moding 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 sub-set 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 straight-line 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 10-degree slice though so I may not get around to this.

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: Rainbow Nautilus Solution
PostPosted: Sun Jan 27, 2013 6:45 am 
Offline

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 non-Groups 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:
90-20-90-60-40-60
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 90-degree pieces can be swapped, the 2 60-degree 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
 Profile  
 
 Post subject: Re: Rainbow Nautilus Solution
PostPosted: Sun Jan 27, 2013 7:07 am 
Offline
User avatar

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 straight-line 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:
90-20-90-60-40-60
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 90-degree pieces can be swapped, the 2 60-degree 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: 90-20-30-60-40-70-50.

_________________
Call me Seth :)

Crazy2Face & Crazy3Face Puzzle Spreadsheet
Named 3x3x3 Bandaging Patterns


Top
 Profile  
 
 Post subject: Re: Rainbow Nautilus Solution
PostPosted: Mon Jan 28, 2013 6:02 pm 
Offline
User avatar

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! :lol:

I tweaked my code to be able to handle arbitrary wedge configurations including the original design with 10 through 80 degree wedges.

The mass-produced 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 non-trivial :D

Edit: The branching-factor 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
 Profile  
 
 Post subject: Re: Rainbow Nautilus Solution
PostPosted: Tue Jan 29, 2013 2:15 pm 
Offline

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! :D


Top
 Profile  
 
 Post subject: Re: Rainbow Nautilus Solution
PostPosted: Tue Jan 29, 2013 3:10 pm 
Offline

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! :D

Yeah! Now I want this modified Nautilus that is much easier to scramble! :)


Top
 Profile  
 
 Post subject: Re: Rainbow Nautilus Solution
PostPosted: Tue Jan 29, 2013 3:27 pm 
Offline
User avatar

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! :D

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 Square-1.

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
 Profile  
 
 Post subject: Re: Rainbow Nautilus Solution
PostPosted: Tue Jan 29, 2013 8:48 pm 
Offline

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 Square-1.[...]

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. :twisted:


Top
 Profile  
 
 Post subject: Re: Rainbow Nautilus Solution
PostPosted: Wed Jan 30, 2013 1:50 am 
Offline

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
 Profile  
 
 Post subject: Re: Rainbow Nautilus Solution
PostPosted: Sat Feb 02, 2013 11:16 am 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
I re-wrote 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
 Profile  
 
 Post subject: Re: Rainbow Nautilus Solution
PostPosted: Mon Feb 04, 2013 11:05 am 
Offline

Joined: Wed Jan 14, 2009 6:37 pm
Location: The Great White North
bmenrigh wrote:
I re-wrote 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
 Profile  
 
 Post subject: Re: Rainbow Nautilus Solution
PostPosted: Thu Feb 07, 2013 9:38 am 
Offline
User avatar

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 23-24. 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 sub-task 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 31-35. 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 4-th 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
states.png [ 6.42 KiB | Viewed 1993 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 multi-thread 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
 Profile  
 
 Post subject: Re: Rainbow Nautilus Solution
PostPosted: Thu Feb 07, 2013 2:27 pm 
Offline

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/cgi-bin/pu ... ?pkey=2880


Top
 Profile  
 
 Post subject: Re: Rainbow Nautilus Solution
PostPosted: Thu Apr 10, 2014 12:13 pm 
Offline
User avatar

Joined: Wed Mar 12, 2014 5:16 am
New simulator. Now with Rainbow Nautilus simulation. viewtopic.php?f=1&t=27054


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 71 posts ]  Go to page Previous  1, 2

All times are UTC - 5 hours


Who is online

Users browsing this forum: No registered users and 7 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

Search for:
Jump to:  

Forum powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group