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