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?

So Long, Japan

And thanks for all the fish

Miyajima

With only a week of living in Japan left, I figured I should go do something cool, and since I hadn't yet been to see Miyajima, that became the goal. Miyajima is an island off the coast of Hiroshima (actually part of the city, I think) that is one of the three great sites in Japan, the other two being Kyoto's Ama no Hashidate (kind of far away) and Miyagi prefecture's Matsushima (really far away). Joining me on this trip and thankfully handling pretty much all the details, faithful friend Mie, seen here riding on a boat.


Our journey started at the local train station, but didn't really start getting update-worthy until we got to Hiroshima. Hiroshima still has streetcars, so we took one of those for the sake of taking one (it wasn't that far) to the peace park. I already posted a bunch of crap about that, and we didn't spend any real time there, so there aren't going to be any pictures of that. From the park, though, one can take a boat down the river and out to Miyajima, which we did.




You can see the atomic dome there. While the boat is on the river, you can stand on the deck outside, which we obviously did, but once you get to the ocean, you have to go back inside and they speed up, the boat bouncing around like crazy. While we were taking pictures and whatnot, a guy offered to take a picture of the two of us, which I don't have because it was with Mie's camera. Mie offered to take a picture of him and his friend, and so I tried to get out of the way, but they thought it was funny and took a picture with me, too. I also don't have that picture.


This is what Miyajima is famous for, its shrine. The actual name of the island is Itsukushima (厳島), and Miyajima (宮島) just means "shrine island." For those paying attention to the characters, shima (島) means island. The unvoiced palatal sibilant sh is voiced as an affricate, j, sometimes due to the preceding sounds. It is odd because usually the change is only in the voicing, but here the actual type of sound changes. If you left it as a fricative (sibilant), then you would get the zh sound, like the j in the French je. That sound doesn't exist in Japanese, however. Anyway, this is the torii, which looks like this at high tide. When the tide is out, you can walk out to it, which we did, but I don't have any pictures of. The tide was out when we got there and we had to wait a while, actually, before we got this. There were some Americans who tried to swim out to it, but they got yelled at by some priest or something. There's a boat that takes you through the gate, actually, if you want to. Prepare for a multimedia experience.




I was saying "Amerikajin da" meaning "[I am/They are/etc.] American[s]." I don't know what we were talking about, so I don't know what the topic of the sentence was. Japanese is high-context.



That's the other thing that Miyajima is famous for, obnoxious sacred deer that try to steal your food or anything they think is food. You are not supposed to feed them, unlike the deer in Nara, though I suspect that people do, anyway. That deer ended up eating that map, but we didn't need it anyway.

There are lots of deer. I have no idea who that other dude is; he just happened to be there.

We went into the main building of the shrine (this costs a small fee), and were lucky enough to see somebody's wedding ceremony. I tried to take a couple pictures, but they aren't very good.



Ah, well. We also did omikuji, which is a kind of fortune telling where you shake a box to get a stick out, and the stick has a number on it. Then you take a fortune out of the drawer with the same number. I got kyou, 狂, which is the worst one. That basically never happens at shrines because they want people to do it more, which they are unlikely to do if it says they are going to get sick or lose their job or something.

We also saw this big pagoda. Not much to say about that. After all that walking around, etc., it was time to take a break (I love this about Japan; it is almost always break time). On a hot day, what makes for a good meal?


Tempura soba! The long tempura is anago, conger eel. Soba is buckwheat noodles. I wanted cold noodles, so this hit the spot nicely.

After lunch, it was time to make our way up Mt. Misen. On the way there were stores selling normal touristy stuff, which in Japan usually includes wooden statues. I don't know who buys giant wooden statues, but they usually have big ones like this:


I'm pretty sure the one on the right is Yebisu, who appears on some of my favorite beer.

The first segment of the climb is done via a "ropeway."
Don't look down, Mie!
Living on the mountain are Japanese macaques. There are a bunch of signs saying not to feed them and not to look at them in the eyes. Also, there are lockers to put your stuff in because apparently they are good at stealing things. When we were coming down the mountain, a couple of them came flying down the path towards me, howling. It was crazy. They were fighting, though, and didn't do anything to me.


I think this was about halfway up?


Most of the way up there is this little shrine building. Mie's doing the classic Japanese pose. We were covered in sweat by this point from trying to climb up the mountain. It isn't that steep, but it was so humid that none of the sweat would evaporate until she found a passage behind the building here that acted as a wind tunnel where we stood to cool off. There were French dudes who were climbing the mountain in sandals (what?).


Even further up the mountain, a little passage between rocks.

Not a very good picture, but from the top you can see the Seto inland sea, on a clear day, all the way over to Shikoku.


お疲れ様、美絵ちゃん！We did make it all the way to the top, where there is a little lookout building, from which you can see 360 degrees of inland sea.

On the way back down, we saw a monkey picking bugs off a deer. Mutualism at work.


And Mie's real goal, green tea flavored ice with sweet bean paste.


And my real goal, delicious Kirin stout. We had drinks with oysters, since they are a local specialty. 御馳走様でした！

School Countdown

And that's all she wrote. This is just plain surreal.

Tarantula

I've just started reading Tarantula, a collection of poems by Bob Dylan from his psychedelic period. A wonderful friend sent me it. It is fantastic.

My favorite flowers come in twos and threes
Because it makes it easier on the bees

I was goofing off with a friend's niece and nephew today and that was great. Back to work tomorrow!

Bubble

What is this John and Kate thing? I have no idea actually. From what I can gather it is some sort of tv show about kids or people with kids or something. People keep referencing it on shows that I actually watch and there are news stories or opinion pieces or whatever about it that I don't read but see on news websites. I could just google search, I'm sure, but I actually don't want to know. One of the little known benefits of living overseas is that the effort it takes to stay in contact with the US makes you basically immune to whatever stupid culture stuff is going on there. Also, the effort of trying to figure out Japanese tv, etc., makes you basically immune to the stupid stuff here, too. It's fantastic and I'm going to miss the ease with which one can live in a bubble, protected from all the stupid, here. Actually, nobody tell me what it is because I don't want to know.