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.
The rules were simple: follow the planks in order of Red, Blue, Green, starting from the single tyre next to the rules board, and get to the raised tyre in the centre.
We thought it would be a simple enough diversion for a few minutes; we’d quickly beat it and be on our way — so we thought.
Half an hour later, the six of us still hadn’t solved it. I remember thinking two things at the time: either this puzzle was intentionally impossible to solve to give parents more time at the café, or the children of Toowoomba possessed immense mental faculties far exceeding our own.
We eventually ran out of steam and we decided to move on. For myself though, the nerd sniping had just begun. We took some photos of the puzzle and left, deeply unsatisfied. I was burning to know what sort of complicated solution this puzzle must have, or indeed if it was solvable at all.
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 tyres are laid out and connected just like tessellated hexagons.
- 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.
Finally, we got home, settling in for an afternoon of drinking, eating, and (in my case) programming. I hadn’t brought a laptop along for the trip, so I ended up slogging through it with Pythonista on an iPad.
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:
From this chart, I transcribed the edges into a simple text-based format, of space-separated node, node, colour triples, to describe each plank. The ability to add comments was really useful, so I also included support for them in the parser as well. The full puzzle spec file is on GitHub, but here’s a small sample of the format:
# 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 greenProducing the chart, then describing every plank into a text file ended up being a terribly tedious task. Limited by the small iPad screen, it was a slow grind, switching back and forward between the photo, diagram, code, and text-files. The eating, drinking, and catching up we were actually there for made for slow progress too. All up, the specification file describes 85 planks (edges), connecting 38 tyres (nodes).
Hidden Depths
Finally, the puzzle was in a malleable format we could start playing with. Using the excellent NetworkX library, I got started trying to solve it. Straight away, I started realising a couple problems with my approach. The biggest flaw was thinking we could consider the puzzle a simple directed acyclic graph (DAG).
The first problem was that it’s not acyclic at all; there’s no rules about revisiting a node you’ve previously been too. This ultimately isn’t a problem, there’s no issue pathfinding within such a graph. Djikstra’s and similar algorithms take a breadth-first approach, which translates to the fact they wont get trapped searching infinite loops exploring overly long paths while other alternatives are still possible.
The next problem was that the graph wasn’t directed. Planks can be used to travel in both directions, provided the previous plank traversed was the correct preceding colour in the red-blue-green cycle.
This puzzle I had thought was a simple a DAG had now actually ended up as a directionless cyclical graph. On top of that, the issue of how to solve the colour constraints hadn’t gone away either, and in fact was starting to look quite a bit more hairy.
So now I was stuck. Djikstra’s is an elegant algorithm, but the colour pattern that had to be followed was overcomplicating every attempt to path-find within the puzzle. It was if each tyre had its own state, that changed depending what colour plank you took to get to it. If you took a green plank to get to a tyre, it was like the tyre itself was put into “green mode”, which reduced the edges you could take immediately to just red.
These three modes (one for each colour) the tyres would end up in was getting too inelegant to solve with a conventional priority queue metod. A new technique though was starting to shape up; what if instead of tracking the mode of each tyre, depending on where you’d been, what if we split the puzzle into different dimensions?
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.
A green plank now becomes a portal into the green dimension, only available to you from the blue dimension, and so on. Because the planks themselves could be taken both ways, this had the effect of creating two directed edges; both into the colour dimension of the plank, but from both tyres in the preceding dimension. Here’s an example of how three planks become six directed edges when the colours are split out:
This was the breakthrough I needed. The constraint of the colours was now encoded into the structure of the graph itself. Without knowing anything about the red-blue-green “rules” of the game, it was now impossible not to make valid moves just by following edges in the graph.
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.
This ended up being the product of the three start node colours with the three goal node colours. Finding a path from a tyre to any other was a matter of finding if any of nine paths were possible:
Of these nine, only one path is possible, Green-A to Green-D, but that means that starting on A, it’s possible to navigate to D. If more than one path was possible, picking the shortest one was necessary too.
An interesting consequence of the real-world puzzle’s starting tyre only having a red-plank, meant that in you were actually being forced to start the game in the “green dimension”.
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!
Here we can see that the output is the sequence of tyres to traverse, with coloured arrows representing the planks to take. We can see it’s a valid Red, Blue, Green sequence, taking three planks to get from “A” to “J”. Seeing it overlaid on the puzzle is a lot more satisfying though, and we can indeed see how we would get from “A” to “J”:
So, all we had to do now was plug in a request from node “A” to node “T” to the final answer. Drum roll…
No solution. I’d just thoroughly proven that it was impossible to solve the puzzle 😐
On one hand that was good. All our time hopping around at great risk to our ankles had meant that we hadn’t missed a possible solution. On the other hand though, what sort of crap childs’ puzzle is deliberately impossible? How unsatisfying and bizarre. This puzzle clearly would have taken a great deal of effort to actually build with real tyres and painted planks. Something just wasn’t making sense…
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.
This was something we had totally overlooked while there in person, and for a good time while trying simpler approaches looking at the photos later.
Zooming into the spot with the missing plank, there are clearly original nails and good deal of green paint residue left over from a plank that used to be there. This was a smoking gun; the next thing to try was to see if by virtually adding that plank back, the puzzle was solvable.
So taking of copy of the puzzle file, adding a line for the missing plank, we could run the algorithm again. Lo and behold, a valid 26 step path pops out! Note that the green plank is indeed critical, it’s used to get from “AB” to “AA”, about halfway through the solution:
So it worked! Some tyres are used multiple times in the solution. Even though you step onto the same physical tyres more than once, you are actually accessing them in different colour dimensions. This means that the apparent loops are actually necessary. A good example of this is the “Z” tyre. You are directly adjacent to the final tyre about two thirds of the way through, but yet you still need to take a whole route around the bottom left quadrant to just get back to “Z” in the right colour dimension to complete the puzzle (Green-Z to Red-T). Here’s the solution drawn out, with the double visits drawn as concentric circles, and the missing plank emphasied:
Seeing this solution made it all worth it. Did I actually go back and do the puzzle for real?—No. Did the hours of work make anyone’s life better?—No. Will I send the café owners an overly elaborate analysis of why they need to restore a single plank between two tyres?—Maybe.
But, seeing that solution pop out, after all that programming and detective work, the satisfaction was immense. All up it was a fun challenge, is something to talk about, and had a satisfying conclusion. I rate the experience 10/10, and encourage anyone curious to have a play with it. I didn’t go into the code much, but I hope the explanations are clear enough.
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.