# Brute-force solver for Gear Octahedron - flawed method?

I am working on a program to brute-force a LanLan Gear Octahedron I bought second-hand (and scrambled). I have no background in "cubing" and just fancied solving the problem.

The structure comprises 8 "Centre" pieces (at the centre of each face); 6 "Corner" pieces; and 12 "Edge" pieces each holding a "Gear" sub-piece whose teeth mesh with adjoining pieces.

The puzzle's main movement is rotation on one of 3 axes. The 4x Corner and 4x Edge pieces along the middle of the axis remain static, but their Gears turn 300 degrees (5/6 of a full rotation). The remaining groups of pieces on either side of them each rotate 90 degrees in opposing directions.

I modelled the state of each piece, so whole states could be stored as BLOBs in a database, like so:

Centre:
position       8 values / 3 bits
1 nibble
x8 pieces                 4 bytes

Corner:
position       6 values / 3 bits
orientation    8 values / 3 bits
2 nibbles
x6 pieces                 6 bytes

Edge:
position      12 values / 4 bits
orientation    2 values / 1 bit
gear rotation  6 values / 3 bits
2 nibbles
x12 pieces               12 bytes

Total state              22 bytes


From each state there are 6 possible moves (3 axes, 2 directions).

My solver starts from a given (scrambled) state and iterates through every possible move in turn (while simultaneously doing the same in reverse from the winning state). Each time a novel state results from a move, a database record is added comprising the new state, a pointer to the previous state, and the move that was made. The progression through states is like so:

1. For each possible move from current state:
• Skip if move is simply the last move in reverse
• Skip if same move has been repeated 6 times (rotation on one axis returns all pieces to their original state after 12 turns, so only allow 6 turns in each direction)
• If the new state exists in the opposing search tree, win.
• If new state exists in this tree, skip.
• Insert new state into database.
2. Move current state to next record in database.

I think this is exhaustive, but it can't be, because both trees fail after the 1327104th row inserted: when trying to progress to the next state after this one (which represents a depth of 17 moves), there is no next record to progress to as no further novel states have been found.

Unless my code is buggy (conceivable) or I was sold a nobbled puzzle (also can't rule out), there's a flaw in the above logic that is causing me to rule out possible moves erroneously. Can anyone identify one?

Update: At first, based on the revelation that my app yielded two non-overlapping maximal sets of states, I concluded that my logic and coding were correct but the initial state data I entered was incorrect. However I checked this and that was not the case.

In fact my earlier conclusion was flawed: having generated the correct number of possible states does not mean the state-representation and transition code are flawless, merely that the flaws do not prevent this outcome.

## Final outcome:

I made several moves with the puzzle and compared them with the states in the database, to the point that I was satisfied that my coding was correct. Next, I looked for the state in my "forward" tree that was closest to the win state, and vice versa (closest to initial state in the reverse tree).

In both cases, three Gears differed by the same offset. I ran the solver with these adjustments, and now have a completed puzzle except for the three gears that have been tampered.

• Why do you think the puzzle should have more than 1327104 states? It is in fact equivalent to the Gear Mastermorphix (same mechanism but shaped as a tetrahedron) which has that number of states. The movement of pieces is quite restricted. For example, the edge pieces in one slice will never mingle with those in the other two slices. Commented Jan 15, 2020 at 16:42
• Sounds like your code is working if it found the correct number of states. Do both the start and end states write to the same tree? If so, you might have a race condition. Or perhaps you are not searching the visited states tree correctly in your code? Or perhaps the syntax is slightly different between the two states (if there are two trees that are complete but don't overlap at all, that seems the likely answer). Commented Jan 15, 2020 at 20:19
• @Jaap Scherphuis I didn't know how many states it would have (my maths isn't all that hot), I just thought my code would methodically find the route to the win state. I did wonder if the number was significant as I learned it's a perfect square (1152^2). If what you say is correct I must have a coding flaw, as I actually have twice that many states (across the two search trees) that my app sees as all unique. Commented Jan 15, 2020 at 20:45
• @Dr Xorile per Jaap Scherphuis's comment I do indeed have two complete and (so I thought) non-overlapping trees, so it seems the answer is my state representation, not my logic, is faulty. You've both provided the answer to my question, but not in answer format. I think I'm right in saying that extending the question to refocus on my coding would be inappropriate, but if either of you put it formally in an answer I'll accept. Commented Jan 15, 2020 at 21:06
• Just let us know how it goes! Commented Jan 15, 2020 at 21:13

The Gear Octahedron puzzle actually has 1,327,104 states. On my website I have a page about the Gear Mastermorphix, which is an equivalent puzzle (same mechanism, but with a tetrahedral outer shape). On that page there is an explanation as to how that number comes about:

• 4! permutations of the triangular face centres (one of them is held steady and serves as a fixed reference point)
• (4!/2)3 permutations of the edges. The edges fall into three orbits, as they never leave the slice they are in (permutation parities all match the face piece parity, hence the division by 2).
• 4 orientations of the edges (edge orientation can be defined such that every move flips the whole middle slice)
• 23 orientations of the gears inside the edges

Combined that makes 4!⋅ (4!/2)3 ⋅ 4 ⋅ 23 = 1,327,104 possible states.

I also calculated the number of states at each depth using two different metrics - repeated turns of the same face either count as one move or as several. The results are shown in the table below.

0 1 2 3 4 5 6 7 8 9 10 Total
0 1 1
1 6 6
2 6 24 30
3 6 48 96 150
4 6 60 276 384 726
5 6 72 396 1,200 1,440 3,114
6 3 96 512 2,346 4,176 4,554 11,687
7 96 660 3,108 11,016 11,088 10,686 36,654
8 72 852 4,599 15,630 29,409 25,444 16,677 92,683
9 72 828 4,716 21,630 47,706 51,462 38,616 18,840 183,870
10 39 774 5,262 20,751 55,209 78,889 86,076 28,962 2,709 278,671
11 672 3,840 20,100 51,480 80,208 84,180 66,696 1,440 308,616
12 494 3,090 12,624 34,392 57,806 87,603 38,061 5,242 239,312
13 288 1,464 6,510 13,200 34,176 35,964 32,370 768 124,740
14 133 681 522 6,846 5,498 16,572 9,369 554 40,175
15 48 144 240 1,992 648 2,946 384 6,402
16 60 108 72 27 267
Total 1 33 579 6,029 30,690 114,543 254,124 346,221 366,444 197,316 11,124 1,327,104

It shows that in the worst case it takes 16 moves to solve the puzzle (or 10 if repetitions are not counted as separate moves).

So it seems like your program generates the unique states of the puzzle correctly, but possibly something in your encoding is off so that your two tables don't meet up. Make sure that you keep the same piece as a reference point, otherwise the two tables might differ by a rotation of the whole puzzle. You could for example keep the yellow triangular piece fixed in space at the DBL (down back left) location, oriented such that the yellow-red edge lies in the equator, and then only allow moves of the F, R, U corners. Do this on both tables, reorienting the puzzle(s) to make that so before starting your searches.

• Thank you for revealing the significance of the number 1327104! I did suspect it was non-coincidental but lacked the insight to understand why. Now I know not only that my logic is OK, but so is my DB design and state-transition code. So that just leaves (a) my inputting of the scrambled state (which I'm reviewing now) or (b) that a certain market-stall lady in Hong Kong has an evil sense of humour and sold me a nobbled puzzle ;) Commented Jan 18, 2020 at 12:49
• @Headbank I edited the last paragraph, cause I was describing it in terms of the gear cube rather than the gear octahedron, which is confusing. Commented Jan 18, 2020 at 16:03
• Ah, I see what you mean. The approach I took was similar but I keep a corner-piece fixed: the one "facing me" (xyz = 0,0,1 in my mapping). This seemed the easiest way for me to mediate between a simple spatial description for coding purposes, and being able to describe move sequences back to myself ergonomically on completion. Commented Jan 19, 2020 at 14:33
• It actually looks like the puzzle is in fact physically compromised. Looking at the data amassed, I noticed that in the reverse tree (from winning state), the edge pieces can have no more than 3 distinct gear-rotation states among them at once, whereas in the forward tree (from the initial state) no states have less than 3, and some up to 5 distinct states. Commented Jan 27, 2020 at 16:39
• @Headbank: The four gears in one layers all move in concert, so if one is correct (relative to its edge piece) then the other three should be correct too. If the puzzle is a little loose, it is possible to make a gear skip a tooth, first on one side and then on the other, especially part-way through a move. You don't need to disassemble the puzzle to fix the problem. Commented Jan 28, 2020 at 8:21