A-Maze-Ing

Today was my last computer science lab of the semester, so I thought I'd share this problem we discussed...

The Problem:

Given a grid of empty and filled spaces, find the number of shortest paths from start to finish.

Example 1:


S 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 F

S is start, F is finish, and 0 is an empty space. Programmatically, we can determine that the answer is 84 paths. Now we just need a mathematical solution.

The length of a shortest path is 9 steps, for instance, 4 steps down and then 5 steps right. So, given 9 steps, at each step we have the option of moving vertically or horizontally, but we have to move 4 horizontal steps total. That sounds like a Combination!

Paths(S, F) = ₉C₃ = 84

And there we get our answer.

Example 2:


S 0 0 0 0 0 0
0 0 0 X 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 F

S is start, F is finish, 0 is an empty space, and X is a filled space. Programmatically, the answer is 54. Let's try combinations again.

Paths(S, F) = ₉C₃ = 84
Paths(S, X) = ₃C₁ = 3

Hmm... that doesn't help much. Or does it? 84 – 54 = 30. But where do we get a 10? On a guess, I tried:

Paths(X, F) = ₅C₂ = 10

Wow! Now we have the theory:

Number of Paths = Paths(S, F) – (Paths(S, X) · Paths(X, F))
Number of Paths = 84 – (3 · 10)
Number of Paths = 54

Does this work in other cases? Let's try it out.

Example 3


S 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 Y 0 0 0 0
0 0 0 0 0 0 F

Again, S is start, F is finish, 0 is an empty space, and now Y the a filled space. The answer is still 54.

Paths(S, F) = ₉C₃ = 84
Paths(S, Y) = ₄C₂ = 6
Paths(S, Y) = ₅C₁ = 5

Number of Paths = Paths(S, F) – (Paths(S, Y) · Paths(Y, F))
Number of Paths = 84 – (6 · 5)
Number of Paths = 54

Looks like we have a winner!

Example 4:


S 0 0 0 0 0 0
0 0 0 X 0 0 0
0 0 Y 0 0 0 0
0 0 0 0 0 0 F

In our final example, S is start, F is finish, 0 is an empty space, and this time both X and Y are filled spaces. The answer is 24.

This example combines both of the previous examples, so perhaps we can apply our theory twice:

Paths(S, F) = ₉C₃ = 84

Paths(S, X) = ₃C₁ = 3
Paths(X, F) = ₅C₂ = 10

Paths(S, Y) = ₄C₂ = 6
Paths(S, Y) = ₅C₁ = 5

Number of Paths = Paths(S, F) – (Paths(S, X) · Paths(X, F)) – (Paths(S, Y) · Paths(Y, F))
Number of Paths = 84 – (3 · 10) – (6 · 5)
Number of Paths = 24

It appears that this solution works, but I haven't tested it in any other situations yet. For now, this is my answer, and I'm sticking to it. Chris out!

Edit 2007-05-05

After thinking about it, I figured out why we multiply the two path counts. For every possible path from start to the filled square, there are a certain number of paths from the filled square to finish. All of those whole paths are no good. For example...

S 0 0 0 0 0 0   S 0 0 0 0 0 0   S 0 0 0 0 0 0
1 2 X 3 4 5 0   1 2 X 3 0 0 0   1 2 X 0 0 0 0
0 0 0 0 0 6 0   0 0 0 4 0 0 0   0 0 3 4 5 6 0
0 0 0 0 0 7 F   0 0 0 5 6 7 F   0 0 0 0 0 7 F

S 1 2 0 0 0 0   S 1 2 0 0 0 0   S 1 2 0 0 0 0
0 0 X 3 4 5 0   0 0 X 3 0 0 0   0 0 X 0 0 0 0
0 0 0 0 0 6 0   0 0 0 4 0 0 0   0 0 3 4 5 6 0
0 0 0 0 0 7 F   0 0 0 5 6 7 F   0 0 0 0 0 7 F

In the above grids, grids in the same row have the same path from start to the filled square, and different paths from the filled square to finish, and the opposite for columns. This is not all possible paths, just some examples. The number of starting paths multiplied by the number of ending paths is the total number of paths through the filled square, all of which are invalid paths. Therefore, this number is subtracted from the total number of paths to get the answer.

Edit 2007-05-07

A bit more experimentation, and I've come up with a general solution for cases where the filled spaces are only increasing; that is, filled spaces are only below and/or to the right of the previous filled space. For those with MathML enabled browsers (I think most are), you can view that solution here. For those who can't view the MathML, why not try Mozilla Firefox?