Video Transcript
Welcome back! So, in the last part, I showed a way to solve Towers of Hanoi just by counting up in
binary, a solution that I learned from computer scientist Keith Schwarz. If somehow you landed here without watching that, you probably wanna go check it
out. Here, in this video, I wanna describe a constrained variant of that puzzle and how it
relates to finding a curve that fills Sierpinski’s triangle.
KEITH: The problem variant is that the, you know, some- you can think of these discs
are in a line. You’re only allowed to move a disk from one spindle to an adjacent one. And, so, now the question is, solve Towers of Hanoi.
GRANT: So, for example, like in a previous one, we start by moving disc zero to
B. And the next move was to move disc one over to C. But you can’t do that because you can’t get one straight over to C.
KEITH: Exactly! So-so it’s more complicated. But the idea for this modified version is still similar. So if I wanna move disc three, let’s say I’m trying to get it from A to C. So, as before, I can’t move disc three unless this tower above it — two, one, and
zero — are out of the way. So, ultimately, I’d like to get this tower to be not blocking it. But there’s two ways it can block it now. So, previously, it just had to not be on top. Now it has to not only not be on top, it can’t be adjacent either. So, really, what I wanna do is take this tower of zero, one, and two and somehow, I
don’t know, get it to thing C, then move disc three over. Then get it off of C back to A. Then move disc three from spindle B to spindle C. And then move that tower all the way back.
The smaller case breaks down essentially the same way. You solve it for two discs, move disc number two, solve for two again, move disc
number two, then solve for two discs yet again. As you keep subdividing in this self-similar pattern, expanding each subproblem into
its own set of subproblems. Eventually, you get to the smallest subproblem of them all, moving a tower of size
one, which just involves moving disc number zero twice.
As with the unconstrained case, this is gonna give you the most efficient solution,
since at every scale you’re only doing what you have to do. You have to move that subtower with zero, one, and two over to peg C if you plan on
moving disc number three. And you have to move it back to A in order to move disc three again. And you have to move it all the way back to C a third time. There’s just never any room for inefficiency once you break it down in terms of
subproblems like this. And just as the unconstrained puzzle mirrored the pattern of counting in binary, the
breakdown of this constrained problem is mirrored by counting in base three, also
known as ternary. Here, let’s take a moment and talk about what base three feels like, what the rhythm
of counting there is.
So, as you know, our usual counting system, base 10, has 10 separate digits and
binary, or base two, has two separate digits. So ternary is a system of representing numbers where you only have three distinct
symbols available, zero, one, and two.
KEITH: I don’t even know what you call those. So, it’s not a bit; it’s not a digit; is it-is it at trit? That just- I-I think we were talking about this earlier. Like it just doesn’t sound right.
They are indeed called trits. But hey, if that sounds a little bit off to you, just ask a French speaker how they
feel about our convention of calling binary digits “bits”.
Anyway, back to what we were doing, let’s think about the rhythm of counting in
ternary. You start by just counting through the trits, zero, one, two. Then, you have to roll over to a second trit in the threes place. Then, you count to four, which is one, one; five, which is one, two; and you have to
roll over again to two, zero, representing six. Then two, one; two, two, at which point you have to roll over twice to the nines
place, writing the number nine as one, zero, zero. Just like base two and base 10, there’s a certain self-similarity to this
pattern. At all scales, it looks like counting up to some amount, rolling over, counting to
that same amount, rolling over again. Then counting to that same amount a third time.
But this is the pattern that we just saw with the constrained Towers of Hanoi. Do a subtask, make some kind of larger movement, do a subtask, make that same larger
movement. Then do the subtask a third time. So just like binary counting mirrors the solution to the unconstrained Towers of
Hanoi, counting in ternary is gonna mirror the recursive pattern for solving the
constrained Towers of Hanoi. This gives a really nice and methodical way to solve the constrained problem just by
counting. Every time you’re only changing that last trit, move disc number zero. So for the first two moves when you’re counting one, two, you’ll be moving disc
zero. Whenever you roll over just once to the threes place, such as when you count from two
up to three represented by one, zero, you move disc number one.
And continuing on like this, you’d flip the last, move zero; flip the last, move
zero; roll over writing two, zero; and then move disc one. Then twice more, you flip the last and move disc zero. Then whenever you roll over twice to the nines place, you move disk number two. Again, it’s pretty fun to just sit back and watch this play out. It takes a while, though. For four discs, you’re gonna have to count all the way up to two, two, two, two,
which is ternary for three to the fourth minus one, which is 80. That means that solving this involves 80 steps. Nevertheless, like I said before, this is the most efficient solution.
KEITH: But this also then gives you something very cool. You can ask, “How many different configurations are there for-for Towers of
Hanoi?”
Actually, let’s take a moment and think about this. How many total configurations of discs on pegs are possible, where the disks on a
given peg have to be in descending order of size? The answer is three to the fourth, 81 possible states that your puzzle can be in. To see this, notice that there are three choices for where to put that biggest
disc. Then three choices for where to put the next biggest disc. And for each successive disc, you have three choices for where to place it.
And remember, this process of solving by counting in ternary involves taking three to
the fourth minus one steps. Which means, from start to end, you’re gonna hit 81 different configurations. And if you think about it, it can’t hit a given configuration twice. If it did, there would be some more efficient solution out there by working up to the
first time where you hit that configuration, then skipping over everything in
between that and the second time you hit that same configuration, then just
continuing.
KEITH: I have, in a sense, sort of a grand tour. This will not only solve Towers of Hanoi. This will go through every single possible configuration of the disks.
Pretty cool, right? Well, here’s where things get awesome. For those of you familiar with graphs, there is a very beautiful structure to these
configurations. What I’m gonna do is represent each one of these configurations with a dot, a node in
our graph. Then, we say that two different configurations are connected if you could move from
one to the other with some legal Towers of Hanoi move. And this time, I mean an unconstrained move. So configurations are still considered connected even if it requires a move from peg
A to peg C. When you go through and connect all of the configurations like this, finding all the
edges that represent some kind of move, the graph structure for Towers of Hanoi has
this suspiciously familiar shape.
Now, let’s zoom in on it, and think about where this pattern is coming from. For example, this node here representing the start state with all the discs on peg A
is gonna be connected to this one, which is the result of moving disc zero over to
peg B. And both of those are connected to this one, which is the result of moving disc zero
to peg C. These three configurations make up a little triangle in our graph. That is, the three configurations are all mutually connected to each other. In fact, any configuration is gonna be part of one of these triangles somewhere in
the graph. You just consider what happens as you freely move around disc number zero among the
three pegs.
Now, to understand how these little triangular islands are interconnected, take a
look at these two nodes. They differ only by a movement of disc number one from peg A to peg C. So they’re gonna be connected by an edge. This edge is kind of a bridge between two different triangle islands. In fact, those two triangles, along with this other one, form kind of a metatriangle
when you consider all the movements of disc one. Each little clump of three nodes here represents a different position for disc number
one. And the triforce pattern as a whole represents all configurations you can get by
moving around discs number one or zero.
And self-similarly, a movement of disc number two gives you a bridge from one of
these triforce patterns to a new one. And the three possible places where disc two can live give us these three separate
triforce patterns, which are each connected by a little bridge. The fact that there are only two nodes in one of these triforce patterns that has an
edge going out of the pattern itself is just a reflection of the fact that it’s hard
to move disc number two. That only happens in those very special configurations where disc one and disc zero
are both out of the way.
As you consider more and more discs, this pattern continues. The graph structure for Towers of Hanoi configurations is one big Sierpinski
triangle. Isn’t that crazy?! So now let’s think about what it means for this method of solving the constrained
problem by counting in ternary to walk through all possible configurations. What it’s gonna give us is a way to wander through this graph and hit each node once
and only once. This is crazy to me. If you just look at the Sierpinski graph structure, it’s not clear at first that such
a path is even possible. And yet, we found one just by counting. If that’s not beautiful, I don’t know what is.
Alright! So for this last animation here, I’m gonna show the path that walks through the
Sierpinski graph according to the way in which ternary counting solves the
constrained Towers of Hanoi puzzle. If I fade out that graph just to emphasize the path, here’s what it looks like for
higher and higher orders, corresponding to Towers of Hanoi with more and more
discs. What you’re seeing is very similar to the idea of space-filling curves that I talked
about in the Hilbert curve video. It’s just that the limit here fills a fractal instead of the square. Isn’t that crazy?! You can have a curve that fills Sierpinski’s triangle, which I totally don’t think of
as a curve-type thing.
