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.

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:

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:

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.

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

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:

When ignoring the middle layer, the farthest distance between a pair of states is 21 moves (where a move is a flip).

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

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:

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.

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?

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.


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.

I don't follow you here.

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.


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.

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.

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.

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

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.

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


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.

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.

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.

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:

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:



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.

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.

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.


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.

Here's the branch survey results.

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.

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