Random Tower of Hanoi

Play a random position

The board above was dealt, not stacked. The rules are exactly the ones you already know — one disk at a time, only the top disk of a tower, never a larger disk onto a smaller one — and the goal is still every disk on tower C. Shuffle deals a new position; Reset puts the one you are playing back the way it was dealt.

Every arrangement of the disks across the three towers is a legal position, and that is worth a moment. You never have to check whether a scramble is valid, because within a tower the order is not a choice: the disks on it must run largest at the bottom, so a set of disks on a peg has exactly one legal arrangement. With 5 disks there are 3⁵ = 243 positions in total, and all of them are reachable from all of the others.

Why a scrambled start is harder

It is not harder because the puzzle is bigger. A dealt position is usually closer to solved than a full stack is, and takes fewer moves. It is harder because the method everyone is taught stops applying.

The textbook recursion is a sentence about a stack: move the top n − 1 disks to the spare tower, move the largest disk across, bring the n − 1 back. Every step of it assumes the disks you are talking about are already in a pile. From a scramble they are not, and there is nothing to recite — which is precisely why this is the board that tells you whether you understood the idea or memorised its shape.

It also breaks the habit that makes people good at the ordinary game and no good at this one. On a full stack the first move is always the same, and with a little practice a player stops deciding anything at all. Here the first move is a question every time.

Solving from any position

There is a rule, it is short, and it gives the shortest solution every time. It is the same idea as the textbook recursion with the assumption taken out.

1. Find the largest disk that is not already home. Everything larger is on tower C and beneath it, and can be forgotten about — nothing will ever move it again.
2. It has to get to the goal tower, and to move at all it needs every smaller disk off its own tower and off the goal tower. There are three towers, so that leaves exactly one place for all of them. No choice is being made here.
3. So solve that smaller problem first — put every smaller disk onto that one tower — then move the large disk across, and start again.

Because nothing in those three steps is a decision, no cleverer route exists: the position of the largest misplaced disk forces where everything else must be before it can move. That is what lets this board do something no other Tower of Hanoi site does — tell you the exact number of moves between the position on screen and a finished puzzle, from any position, at any time. It is the number in the readout under the statistics, and it is a fact rather than an estimate.

Press Hint on any dealt board and then work out why that is the move. It is always step 1 applied to whatever is in front of you.

How far from solved is it?

Here is the pleasant surprise. The average distance from a random position to a solved board is not an ugly constant that has to be measured — it is exactly two thirds of 2ⁿ − 1.

The proof is the rule above, counted. Work down from the largest disk:

1. Each disk has one tower it needs to be on — decided by the disks larger than it.
2. If it is already there, it costs nothing. If not, disk k costs 2^k−1 moves: its own move, plus carrying the finished smaller stack back on top of it.
3. A random deal puts each disk on each tower with probability one third, so each disk is already right one time in three and wrong two times in three.

The expected total is therefore two thirds of 2ⁿ⁻¹ + 2ⁿ⁻² + … + 1 — two thirds of 2ⁿ − 1.

The worst case catches people out. 2ⁿ positions are the full 2ⁿ − 1 moves away — 32 of the 243 at 5 disks — and they are the ones where every disk is on a wrong tower. The two tidiest positions on the board, a complete stack on tower A or tower B, are among them. A board that looks like chaos has usually had several of its large disks accidentally settled, and settled large disks are where almost all of the work is.

The deals on this page are not quite uniform, for that reason. A genuinely uniform draw sometimes hands over a position that is over in five moves, which is not a puzzle — so anything under 2ⁿ⁻¹ moves from solved is thrown back, and the deal is drawn again. That floor is what it costs to move the largest disk once, so every position you are dealt contains at least one full clearing of the stack above it.

What this is good practice for

Three things, and they are the three that carry over.

Reading a position. The single most useful habit in this puzzle is to stop looking at the disks and look for the largest one that is out of place. On a full stack that is always the bottom disk, so the habit never has to form; here it has to form on the first move. It is also the habit that makes the strategies page make sense.

Recursion that is not a shape. If you are learning recursion with this puzzle — and a great many people are — then solving from a scramble is the test of whether the idea landed. The recursive call in the textbook version is always hanoi(n − 1, …) with the same three towers permuted. From a dealt position you have to work out what the smaller problem actually is before you can call it, which is the part that matters and the part the template hides.

Not trusting how a board looks. The efficiency readout is unforgiving here in a way it is not on a fresh stack, because a scramble tempts you into a plausible-looking move that undoes a large disk's work. When it says you are four moves off optimal, you are four moves off optimal, and the number can never go back down.

When you want the same idea with a fixed puzzle and other people playing it, the daily challenge is one scramble a day, the same one for everybody. When you want to set the position yourself rather than be dealt one, the solver takes any arrangement and returns the shortest solution from it.

Questions about random starts