Resorting to Graph Theory to Beat a Children’s Game

At a café in Toowoomba, some friends and I were intrigued by a simple-looking puzzle made to entertain children. It was made of a few dozen tyres laid out, with coloured planks attaching them.

Image for post
Image for post
The puzzle IRL.
Image for post
Image for post
The rules of the puzzle.

Daydream Planning

For the following drives and rainforest-walk we did after, I started planning how to crack it. A few things came to mind:

  • The puzzle could likely be thought of as a directed acyclic graph. Tyres can be thought of as nodes, and planks between them can be thought of as edges.
  • A modified Dijkstra’s algorithm, would be our best bet to solve it. Enforcing the constraint of following the correct sequence of colours was going to be a complicating factor for sure. A plain implementation of Djikstra’s wasn’t going to cut it.
  • Using a heuristic required for an A* path-finding implementation (likely just Euclidian distance) would have been possible, but would have been overkill. It was a densely connected puzzle, but still tiny compared to what any computer can handle.

The Preparation

The first step was to get a good digital model of the puzzle. Digging through this excellent writeup on working with hexagons, I settled on the simplest Axial Coordinate system, and also labelled each node with an alphabet letter, Excel-style. Even making this chart, basing it off the photo of the tyres, took a good while:

Image for post
Image for post
A diagram of the puzzle, with coordinates, labels, and coloured edges drawn on.
# Start
A E red
# -3 Horizontal
B C blue
C D red
D E green
# -3 to -2 diagonals
B F red
B G green
C G blue
C H green

Hidden Depths

Image for post
Image for post

Ramping up the Dimensions

So I split the nodes up, making a “colour dimension” for each tyre. This tripled the number of nodes, but now planks were directional.

Image for post
Image for post
The tyre puzzle split into three simpler “colour dimensions”.
Image for post
Image for post
A simplified puzzle, and its expanded triple-dimension version.

So is it Solvable‽

In the end, implementing my own fancy Djikstra’s wasn’t even necessary, NetworkX’s already has it implemented as a part of the shortest_path() function. Because each real-world tyre was represented by three nodes in the graph though, I did make a little little helper to solve paths going from any colour of the starting node, to any colour of the goal node.

Image for post
Image for post
It was more useful to ask “can I get from A to D”, via any path possible.
Image for post
Image for post
The nine permutations of possible start and end tyres to get from A to D.

Results Time

Starting with some test cases, and later plugging in some verifiable paths into a helper command-line script, real solutions were popping out!

Image for post
Image for post
An example asking for a solution from tyre “A” to tyre “J”.
Image for post
Image for post
The same A➜E➜I➜J solution, visualised.
Image for post
Image for post

Send it to the Lab

During the slow process of studying the picture and writing the details of each plank into a text file, I found something interesting: there was no plank between tyres AA and AB. Feel free to try spot it in the topmost photo, or the flattened diagram too. There was simply a plank missing, when every other adjacent tyre was connected with one.

Image for post
Image for post
A single missing plank?
Image for post
Image for post
Image for post
Image for post
The full solution, made possible with the missing plank added back in.

Follow Up

I’ve since gotten the rough solution code off my iPad, cleaned it up, and put it up on GitHub for anyone to take a look. I’ve reworked how the puzzles are prepared and how the solutions are displayed, but the methodology is the same as described in this writeup.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store