Maze Problem

Have you ever read a Games Magazine? I guess "read" is not the proper word. It's a magazine of puzzles, like crossword puzzles and whatnot, so just reading through it wouldn't be very enjoyable. If you are a member of my family, and since you are reading this blog, the odds are pretty good you are, you have at least tried some of the puzzles. Today I am going to talk about a puzzle that I liked doing because it's a math-y thing and I'm pleased with myself for having solved it. If Will Shores or whoever wants to complain, then he can email me and I'll take this down. I sort of doubt that will happen.

Anyway, on the cover of this latest issue, there is a puzzle entitled "Lost in the Pyramid." It is a 7 x 7 grid of squares in different colors. The object is to get from the center square to one of the edges, with the path touching one and only one of each color square along the way. The last square, then, has to be one of the edge squares, but not one of the four corner squares. I have translated the colors into letters so as to make this possible to blog. Hopefully the formatting works out, but if not, you should at least be able to follow along by making your own representation. Here's what the puzzle looks like (the letters-color correspondence is obviously arbitrary):

ADDLLLT
AEJMTTT
AFJNOSU
BBJVQSU
CGKKQRU
CHIPQRR
CHIPPPR

Obviously not quite square when I type it like that (I think J's are too thin), but hopefully you get the idea. You start at the V, and have to draw a path touching one of each letter and end at an edge. I am going to refer to each square with a redundant nomenclature of X(y, z) where X is the letter and y and z the row and column number, starting from the top left [A(1,1)] and proceeding to the bottom right [R(7,7)].

I'll get to the solution, but since you might want to figure it out yourself, I'll include a picture break here.


Mmm, Stag. I'm not sure why this beer brewed in Milwaukee is the local beer of choice, but it seems to be.

My method for solving this was to turn it into a graph theory problem. That is, each square is a vertex, and adjacent squares are connected by edges. We proceed by removing edges and vertices until only one path remains. So, initially, the graph should look like a big grid [I would be a poor explainer of graph theory to note that you can draw the graph in any shape you'd like as long as you preserve the relationship between vertices and edges], which is what it is. The obvious first move would be to remove all edges between two letters of the same kind, since no path could contain two of the same letters. There are too many to list here specifically and anyone should be able to do this step on their own. Another convenient preliminary step is to mark all squares which are the only ones with their corresponding letters. That may be confusing wording. If there is only one of a letter in the grid, mark it, as the path necessarily contains that square. That is E(2,2); F(3,2); M(2,4); N(3,4); O(3,5); G(5,2); V(4,4). I am using bold here to represent a vertex we know (or are showing) to be in the path. I will try to keep that notation going throughout.

Note that some of the squares we have marked as included in the path are adjacent. One might be tempted to suppose the path runs from one marked square to the next, but take heed that this is not necessarily true. Note that N(3,4) is adjacent to both M(2,4) and O(3,5). We can't distinguish which of these it will be, if it is even one of these at all. The path could even pass through J(3,3); we don't know if it is in the path or not. Now, onto the parts that require a bit more reasoning. I am going to label my steps so that I can refer to them like a real mathematician might.

1. If we look at A(1,1), we can see that there is only one edge for us to use [we already eliminated the A-A edge]. Then A(1,1) must be the final vertex on our path. However, it is a corner vertex, and, thus, cannot be final. So, we may eliminate A(1,1) and the corresponding edge. The same process can be used to remove T(1,7); C(7,1); and R(7,7), all our corner vertices.

2. Examine R(6,7). Only one edge remains, to U(5,7). From that vertex, only one other edge remains, to R(5,6). Then any path through R(6,7) contains two R's; we may eliminate R(6,7). I won't mention eliminating the edges from an eliminated vertex anymore, this should be obvious.

3. This is really a key step, so if you are paying attention, pay attention. U(4,7) and U(5,7) have only one edge and are possible final vertices. U(3,7) has only two, one of which leads to T(2,5), which similarly can only be final. Thus, if a U is contained in the path, either that U is final, or T(2,5) is final. Since a U is necessarily contained in the path, we have determined that our final vertex is one of these four vertices [a U or T(2,5)]. Then obviously, no other vertex can be final.

4. By applying (3), we may now remove any vertex along the edge of the grid (sorry for the edge/edge) confusion with only one edge. That is A(2,1); H(7,2); P(7,6); D(1,2); C(6,1); L(1,6).

5. Another application of (3) yields I(7,3); L(1,5); and P(7,5) out.

6. Another application yields P(7, 4) out.

7. R(6,6) now has only one remaining edge but can't be final, as it is not along an edge, so we may eliminate it, as well.

8. We have removed vertices, so we may mark some others as in the path as in our preliminary step. D(1,3); L(1,4); A(3,1); C(5,1); H(6,2); I(6,3); R(5,6); P(6,4).

9. Since A(3,1) has only two edges, B(4,1).

10. Then B(4,2) is out.

11. E(2,2) has only two edges, so J(2,3).

12. Then J(3,3) and J(4,3) are out.

13. As in (6), Q(6,5) is out.

14. We know C(5,1)-G(5,2) is in our path. Assume G(5,2)-K(5,3). Then K(5,3)-I(6,3). If we continue to P(6,4), then the path contains no H (it is impossible to get to). If, instead, we suppose I(6,3)-H(6,2), we have essentially cut ourselves off and must end at H, which is impossible. Thus G-K is impossible, so we must have G(5,2)-H(6,2)-I(6,3)-P(6,4).

15. Then K(5,4).

16. Since each vertex in the obvious path E(2,2)-...-P(6,4) has only two edges, we can confirm our suspicions that J(2,3)-E(2,2)-...-P(6,4)-K(5,4) is part of our path (a sub-path, I suppose). Note, we don't yet know the order, that is, which end connects to the V, and which to the edge.

17. From J(2,3), we have two options, D(1,3) or M(2,4). If we assume the latter, we have cut off our only D and L, so we must have J(2,3)-D(1,3)-L(1,4)-M(2,4).

At this point, the solution is close enough that one could probably guess one's way to the end, but I have my reasons for wanting to continue in this fashion, despite the next two steps being quite involved in terms of logic trees. Regardless of where we look, we are going to have to start using more complicated logic trees to find contradictions, etc., so let's just start at the beginning, that is V, and try each of the wrong first steps. By eliminating them, we leave ourselves with only the correct solution.

18. Assume V(4,4)-Q(4,5). Then either Q(4,5)-S(4,6) or Q(4,5)-O(3,5). The former yields two short (they leave out letters) paths, both to U's, so we must have Q(4,5)-O(3,5). Passing to S(3,6) again leads to a short path, so that possibility is out. Passing to T(2,5) means leaving out N(3,4), so that is out. Our final possibility here is V(4,4)-Q(4,5)-O(3,5)-N(3,4)-M(2,4)-...-K(5,4)-Q(5,5), but this path contains two Q's and is thus out. With all possibilities eliminated, we conclude V-Q is out.

19. Assume V-K. Then we must have V(4,4)-K(5,4)-...M(2,4). Passing to T(2,5) again leaves out N(3,4) as in (18), so that is out. Passing to N(3,4) leaves out T(2,5), so T(2,7) must be (the final step) in the path. Then working backwards we have O(3,5)-S(3,6)-U(3,7)-T(2,7). One more step back leads to either N(3,4) or Q(4,5). If we suppose N(3,4), then our path is set and leaves out R, so that possibility is out. Stepping back to Q(4,5) leads to another V-Q, which is out by our assumption V-K. Then our assumption [V-K] is out, so we must have V(4,4)-N(3,4).

That was an awful lot of work to show one edge between two vertices we already knew were in the path. It gets easier, though.

20. K(5,4) has only two edges, so K(5,4)-Q(5,5); then Q(4,5) is out.

21. Similarly, Q(5,5)-R(5,6).

22. Then either U(4,7) or U(5,7) must be final, so we may remove T(2,7) and U(3,7).

23. As in (6), we may remove S(3,6).

24. Then S(4,6) and R(5,6)-S(4,6)-U(4,7).

25. Then U(5, 7) is out.

26. T(2,5).

27. We now know every vertex in the path, and all but a few edges. We just need to determine how to get from N(3,4) to M(2,4). As in 17, we can easily verify N-O-T-M is the only path with all the letters.

That's it, then, we have the full path:
V(4,4)
N(3,4)
O(3,5)
T(2,5)
M(2,4)
L(1,4)
D(1-3)
J(2,3)
E(2,2)
F(3,2)
A(3,1)
B(4,1)
C(5,1)
G(5,2)
H(6,2)
I(6,3)
P(6,4)
K(5,4)
Q(5,5)
R(5,6)
S(4,6)
U(4,7)

It took a bit, but it's worth it, right?