# YJ Floppy Ghost Cube



## xyzzy (Nov 10, 2017)

Far as I can tell, the _actual_ name of this puzzle is "Guimo Yijie Ghost Cube", which translates into the wonderfully redundant "One-Layer Ghost Cube Ghost Cube", and "floppy" isn't part of its official name. (I assume it's a translation convention, like changing "yileng" to "Fisher".)

I'm posting this in the theory section because I don't actually have this puzzle yet and I was a bit curious about its solving process. Essentially, while the shape of the puzzle changes with every move, the shapeshifting aspect is only for "obfuscation" purposes (like mirror blocks or the original ghost cube) and doesn't complicate the solve if you know all the shapes by heart. There also aren't any identical pieces.

Just like on a floppy cube, the five "edges" have orientation (they can be flipped), but they cannot move. Unlike a floppy cube, the five "corners" also have orientation, and any corner piece can move to any of the five corner locations in any of two orientations. (On a floppy cube, it might look like corners can be flipped, but a corner can never be flipped "in place".)

Every move has order 2: if you turn one side 180° twice, it's the same as not turning it at all. Also, each move flips one edge, flips two corners, and does a 2-cycle on adjacent corners, so all 5! = 120 corner permutations are attainable, EO parity is always the same as corner permutation parity, and CO parity is always even. It turns out that there aren't any other restrictions (you can get 3-cycles pretty easily along with a pure edge flip; pure corner flip is a bit trickier but still possible), so the puzzle has 5! 2^(5−1) 2^(5−1) = 30720 states.

30720 is pretty small for a computer to handle, so I did my thing with it. Here's the distance distribution.
0: 1
1: 5
2: 15
3: 40
4: 105
5: 275
6: 670
7: 1500
8: 3140
9: 5825
10: 7752
11: 6415
12: 3395
13: 1270
14: 282
15: 30

So God's number for this puzzle is 15, which seems surprisingly high for such a small puzzle. Anyway, before I wrote the code to enumerate the cases, I also tried to work out (on paper!) bounds for God's number, just for fun, and I managed to get as far as a lower bound of 10 moves and an upper bound of 22 moves, which weren't too far off from the true value! (I'll type out the details when I get the time to—I think there's something interesting here.)


----------



## Max Cruz (Nov 10, 2017)

Wow. Great job with the analysis. I agree - this puzzle has more complexity than meets the eye.


----------



## xyzzy (Nov 11, 2017)

(Continuing where we left off.) You might have noticed that most of the entries in the distance distribution table are multiples of 5, except at distances 0, 10 and 14. This is because of symmetry: of the 30720 states, exactly five of them have fivefold "rotational" symmetry, and the rest have no symmetry at all. The five symmetric states are the solved state, the clockwise 5-cycle, the anticlockwise 5-cycle, the clockwise "star" 5-cycle, and the anticlockwise "star" 5-cycle, which are at distances 0, 14, 14, 10, and 10, respectively. The asymmetric states always come in bunches of five, which explains why the other distances have a number of states that is an exact multiple of five.

On to the "paper and pen" bounds for God's number. The lower bound of 10 moves was obtained with a counting argument. Basically, we count the number of move sequences up to some length $$n$$, then see if this number exceeds the total number of states (= 30720). The naïve way of counting move sequences of length exactly $$n$$ is to note that there are 5 possible faces to turn for each move, so there are $$5^n$$ move sequences. This gives a lower bound of 7 moves, since $$1+5+\cdots+5^7=97656\ge30720$$ and $1+5+\cdots+5^6=19531<30720$.

The slightly less naïve way of counting is to note that you never need to do the same move twice, since that's the same as doing nothing. You have five choices for the first move, as before, but for the second move onwards, you can pick any of the four moves different from the previous move. With this method of counting, we have $$1+5+5\cdot4+\cdots+5\cdot4^6=27306<30720$$ move sequences up to 7 moves, and $$1+5+5\cdot4+\cdots+5\cdot4^7=109226\ge30720$$ move sequences up to 8 moves, so our lower bound improves to 8 moves.

We're still overcounting a lot of move sequences that are strictly different but functionally identical. Let's label the moves as A, B, C, D, E in clockwise order. AC and CA are different as move sequences, but result in the same overall movement of pieces on the puzzle. Likewise for BD/DB, CE/EC, DA/AD, EB/BE. If we forbid CA, DB, EC, AD and BE from showing up within our move sequences, the branching factor drops to 3: after an A move, A and D are forbidden, but we still have three options (and the same applies for the other faces). Since $$1+5+5\cdot3+\cdots+5\cdot3^8=49206\ge30720$$ our lower bound increases again by one move, to 9 moves.

Rather than forbidding CA, DB, EC, AD and BE, we could also pick other options to use as forbidden subsequences. For instance, we could forbid CA, DB, EC, DA and EB. This complicates the analysis a bit, because we have broken the symmetry between all five faces and now we have to keep track of which face was last turned. I worked this out by hand up to 9 moves, saw that the total number of move sequences was less than 30720, and that let me conclude a lower bound of 10 moves. (If you're lazy, you can also get Wolfram Alpha to compute the number of move sequences at n moves for you.)

For the upper bound, I split the puzzle into four stages, going from ⟨A,B,C,D,E⟩ to ⟨A,B,C,D⟩ to ⟨A,B,C⟩ to ⟨A,B⟩ and finally to the solved state. The last stage is the easiest to explain: when the puzzle is in a 2-gen state, you literally just alternate between A and B. If you choose the correct face to start with, this can be solved in at most 6 moves (but if you don't, this can take up to 11 moves).

For the first stage, the abstract description "you no longer need the E face after this stage" tells us what the end result should be, but not how to get there. In the subgroup ⟨A,B,C,D⟩, the edge on the E face will never move, so it must be solved; also, corners will never flip in place but can otherwise be freely permuted. If we use ⟨A,B,C,D⟩ to define a corner orientation reference, then the E move flips the two corners it swaps. The coset space ⟨A,B,C,D⟩\⟨A,B,C,D,E⟩ has 32 elements, and I did a breadth-first search on this coset space to get an upper bound of 6 moves. (The worst case of 6 moves is attained when four corners are flipped (wrt ⟨A,B,C,D⟩) and the non-flipped corner is adjacent to the E edge.)

The second stage solves the "D-E" corner and the D edge; this has ten cases (5 for where the corner is, 2 for whether the edge is flipped). The upper bound is 5 moves, with two distinct worst cases: (i) D-E corner in place, but D edge flipped; (ii) D-E corner in E-A location, D edge not flipped. The third stage is similar, also with an upper bound of 5 moves. In total, this gives an upper bound of 6 + 5 + 5 + 6 = 22 moves for the whole puzzle.

If we'd gone with a more "human" approach to solving the puzzle (e.g. solving it piece by piece), we would most likely get a much worse bound here. Pure edge flips take 6 (adjacent), 10 (non-adjacent), or 12 (4-flip) moves, and pure corner flips take 12 moves; if you have to spend 10-12 moves on an alg, that doesn't leave a lot of room (10-12 moves) for the rest of the solve.


----------



## Hazel (Feb 28, 2018)

This is a bit late but I don't think enough to break forum etiquette (right?)
I've solved this puzzle a bunch of times, and I'd say solving it piece by piece is at least the easiest way to teach yourself to solve it. Without that much practice, I've used that method to get a 12.697 Ao50, but I definitely believe objectively superior methods could be created. I don't understand really any of that math, but I suppose it kind of makes sense that God's number is 15 considering there are 5 turnable layers, as opposed to 4 on a regular 3x3x1.
I might play with the cube more to try to find a better method than just blockbuilding up to the last layer and then flipping the last corners and edges if needed. Maybe I'll be able to break my UWR's, even.


----------

