Solving O'Gear Brain Teaser with Haskell Graph Search
Declan showed me a brain teaser his friend sent him. Apparently, it's known
as the Hanayama O'Gear Puzzle. It consists of a bronze colored metal cube with a captive gear which can roll from
face to face on the cube. The gear can also rotate between two directions on each face. Some edges of the cube are
made so that the gear can't roll over them. One tooth of the gear and one face of the cube have a special cut-out.
Only when the special tooth is engaged with the special face can the gear be freed. The object of the puzzle is to
manipulate the gear into this orientation. Here's a video
of the puzzle in action.
I tried solving the puzzle for about fifteen minutes before deciding to use a computer. My basic strategy was to
treat the problem as a graph search, where the nodes of the graph are the different states the cube and gear can be
in. At any time, you can only do three things: rotate, roll forward, and roll backward. I figured that the limited
set of moves and possible positions would prevent the search space from getting too big.
I marked up the cube with stickers, naming each face and defining its 'north' direction. I also marked the gear by
labeling each tooth and setting a forward rotation direction.
I don't know Haskell very well, so I thought using it would be a fun challenge. Plus, I had Haskell guru Phil to ask for help and advice. A lot of the code is just defining the
connectivity of the puzzle. I used a list to keep track of the links between different faces and a pattern-matched
function to keep track of the possible rotations. I defined north on each face so that these rotations were always
the same. A north-facing gear could only rotate to the east, and a south-facing one could only rotate west.
Beyond the trickiness of defining directions and connectivity, I just implemented a straightforward breadth-first
search. The program creates a list of all states accessible from the starting state. Because the list is generated
with successive expansions of the search frontier, it is naturally sorted by search depth. I take advantage of
Haskell's lazy evaluation, creating an infinite list of accessible states but only ever calculating a few of them.
You can run it with a command like, solve (GearState Top South 4 ). This code, and a different Python
solver I wrote are available in my Github.