Brute-force solver for Gear Octahedron - flawed method?

Question

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.

Answer 1

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)³ 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)
• 2³ orientations of the gears inside the edges

Combined that makes 4!⋅ (4!/2)³ ⋅ 4 ⋅ 2³ = 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.