Now what? I backtrace, and the backtrace is, you

know the process by which I figure out the physical cells in the path and so I'm

going to walk backwards from the label five.

From the five I'm going to find a four, from the four a three, a three and two

and so on, right, so we'll just animate that in.

So I'm going to find a five. The four I choose to find is the four to

the west, so I'm doing the horizontal thing first, and then I safe that to

continue to decrease the numbers, i have to go north.

And some that I call north and so there's my path so the path is 1, 2, 3, 4 cells

verticals and 1, 2 cells horizontal it's kind of an L shaped path from the source

in the upper left to the target in the bottom left.

Now there's something new and interesting.

I am not done. I am not going to label this as an

obstacle. This thing that I've just traced, this

path that I've just traced, becomes the source for the next phase of the

algorithm. I'm going to label everything in here as

a source, all of these cells are going to become the source, and I am going to

continue the algorithm. Okay, so what happens?

I put an S on every one of those cells, and then I'm just a little bit careful

when I do the maze routing step, you know?

I'm not going to try to take an S and expand it from a 1 to a 2 by labeling

another S, right? I'm only going to look at the empty

cells. So going forward this is the scenario.

That L shapes wire that was in the left part of the grid, all of those things are

sources now. We're going to expand this entire set of

source cells to find the next segment, so it doesn't need to be the case that the

source is just the cell. The source can be a bunch of cells.

And all we have to do is have you know an appropriate semantics for how we label

the adjacent neighbors. And the answer is we start by labeling

all of the cells that are one unit in length.

Right? And that's going to be just what you

think, it's going to be all the source cells.

They're one unit in length, which is to say, what are all the paths that are one

unit away from a source? And the answer is those are the source

cells. Right.

Now we're going to find all the paths that are two units away.

Alright, and the rule is you're allowed to label an empty square.

You're not allowed to empty a square that's got a number in it already.

So we're not going to try to take a one and overwrite it with a two.

So what are all the cells that are two units in length on a path from a source?

And the answer is it's sort of a little halo around the source cells.

And I'm just going to kind of draw that in a little bit, you know just because

it's kind of interesting. Okay.

It's this little halo. if the source is a cell, a single cell,

the halo is kind of a diamond. If the source is a complicated shape, the

halo is kind of a diamond that got kind of smeared over all of the source cells.

Right, so those are all of the cells on a path two units in length that starts from

any source, and you just keep going. What are all the cells that are three

units in length? Well there they are, it's another sort of

a halo around all of the twos, and what we can see is that the halo is kind of

marching across to the right. What are all the cells on paths of length

four from any source? Well the halo continues to march across

to the right. And it's kind of vertically going all the

way from the top of the grid to the bottom of the grid.

What are all the cells on paths of length five form any source cell.

And, you know, it continues to march, and in fact the grid is almost completely

filled up at this point. And Oh look, we have hit the target, or

we've, we've hit a target, in this case we've hit the single remaining target.

And next, we're going to do just what we did before.

We're going to take the five that we just labeled the target with.

And we're going to find a four, and then a three, and then a two, and then a one,

and we know that when we hit a one, we have found a source cell.

What's interesting is we don't know which source cell, we're going to find the most

appropriate source cell. In this case the closest source cell,

which when expanded will find a path of length five to hit the target.

So, I'm drawing it just like I did before, we started with a 5, 4, 3, 2, 1.

The pink thing, which is sort of almost the entire horizontal width of the six by

six grid, sort of in the top third, connects the target on the far right to

the source on the top left, and there we go.

That's the next segment on the path. And like I said, we didn't know which

part of the source we were going to start with, that's the right part.