Bicolour Tower of Hanoi

Play bicolour Hanoi

The board above starts with two towers of 3 sizes, one on A and one on C. Each tower alternates colour from the bottom up, and the two are mirror images: wherever tower A has a teal disk, tower C has the amber disk of the same size. Tower B is empty, and it is all the room you get.

Finish with each of A and C in a single colour. Because A began with a teal disk at its foot, it has to end amber all the way up, and C has to end teal. Drag a disk, or click a tower to lift its top disk and click another to drop it; the size stepper moves two disks at a time, because disks come in pairs.

The amber disks carry a white ring inside their edge, so the two sets can be told apart without relying on colour, and every announcement names the colour of the disk it describes.

The rules, and the one that changed

One disk at a time, only the top disk of a tower, and never a larger disk onto a smaller one. Those are the ordinary rules, unchanged.

What changed is a consequence rather than a rule. With two disks of every size, "never larger onto smaller" says nothing about two disks of the same size — so either may sit on the other. On an ordinary board a tower's order is forced: give it a set of disks and there is exactly one legal way to stack them. Here, every size a tower holds both of can be stacked two ways round, and that freedom is the whole difficulty.

It is also why the ordinary puzzle's best trick stops working. On a scrambled ordinary board you can always solve by finding the largest disk that is out of place, because where it has to go forces where everything above it has to be. Here the largest out-of-place disk has a twin that looks the same shape, and which of the two should move first is a real choice.

Why the bottom disks are the hard part

Look at the starting board and it seems nearly done: the two biggest disks are already on the two tower bases. That is the trap. Each is on the wrong base — each has to finish at the foot of the other tower — so the two largest disks must trade places, and nothing else can settle until they have.

To lift either of them, every other disk has to be off it — and there are only three towers. So at some point in any solution, one of the two largest disks is alone on its base, the other is somewhere it can be moved to, and every smaller disk, both colours, is piled on the one remaining tower. Getting everything into that shape and back out of it is most of the work, and at 3 sizes it is where most of the 29 moves go.

A useful way to play it: do not try to sort colours as you go. Clear the way for the swap first, make it, and sort on the way back.

How many moves it takes

Every number in this table is the exact minimum, found by searching the puzzle completely — the method is the next section. The board plays 2 to 5 sizes; one size is listed because it is the smallest case worth checking by hand.

Check the first row yourself: one teal disk on A, one amber on C.

1. Move one of them to B.
2. Move the other across.
3. Move the first to the tower the other just left.

That is 3 moves, and two cannot do it: each disk has to change towers, and a disk dropped straight onto its twin lands on top, where the goal needs it at the bottom.

The first two values, 3 and 10, agree with the published solutions — the 1988 competition's and Nathan Bowler's from 2004. For three sizes he gives a 30-move sequence and a formula that produces 30 — and ends by asking, honestly, "Is that right?" It is very nearly. His sequence is a correct solution, and it plays legally on this board; but the exhaustive search finds one that is a move shorter, 29, and the gap widens at larger sizes. The table trusts the search, because a search that has looked at every position cannot have missed a shorter route.

Solving it by searching every position

The ordinary puzzle is solved by an argument. This one, on this site, is solved by counting — and it can be, because the puzzle is smaller than it looks.

A position is decided size by size. The two disks of one size are either on the same tower — three towers, and two ways to stack them — or on two different towers, which is six ordered pairs. That is twelve possibilities per size, and the sizes do not constrain each other's placement, because within a tower the sizes always fall into descending order by themselves. So 3 sizes have exactly 12³ = 1,728 positions, and five have 248,832.

Every one of those can be written down as a number, and then a breadth-first search starts at the finished board and works outwards: everything one move away is distance 1, everything one move from those is distance 2, and so on until the whole puzzle is labelled. Moves in this puzzle can always be played backwards, so a distance measured outwards from the finish is exactly the distance back to it.

The result is a table with one entry per position, and it turns the solver into a lookup. From wherever the board is, Auto Solve and Hint find a move that lowers the distance by one and play it. The readout under the statistics is the table entry for the position on screen, which is why it can say how far you are from a perfect game as a fact — something only three boards on this site can do, and the only one where the fact comes from counting rather than from proof.

Questions about bicolour Hanoi