Soot Tile Explorations

If you've played Pokemon Ruby/Sapphire/Emerald, then you'll remember Route 113, a route that had grass govered in soot. Each time you walked through one of these soot-covered grass tiles, you would collect 1 soot and the soot would disappear from the tile. When I was a kid, I enjoyed walking through the grass patches in a way such that you hit every single tile exactly once.

Looking at this got me wondering if there is a way to tell, ahead of time, whether a patch of grass can be walked through exactly once each time. I can kind of eyeball a patch of grass and get an intuition for whether it should be possible and what kind of strategy could cover it. But is there a way to formalize this? And are there other interesting things we can find along the way?

This page is my journal as I explore this question.

We can start by imagining that the grass tiles are nodes in a graph. In Pokemon Ruby/Sapphire/Emerald, you can only move north, south, east, or west - there is no diagonal movement. We can say that our graph will make it so each tile of grass has a maximum of 4 edges to 4 different nodes, with each node being a tile of grass.

You can view what we're doing as a variant of the traveling salesman problem.

Secret Line

Imagine a successful path through the grass patches, where you visit each tile exactly once. (Let's assume you don't care about whether you have to walk through used tiles to get out of the patch.) It is basically a coiled line. In fact, you could 'unfurl' the grass tiles and make a straight line, with nothing hanging off them. The reverse is also true - if you can take a line of grass tiles and furl them up such that there is no overlap, you know that this grass patch is solvable. On the other hand, if you start with a line of tiles that has little stubs, there isn't a way to furl them to make a solvable path. We can say that all solvable patches are thus isomorphic to a straight line. Will this help us? Hasn't helped me so far, but I thought it was interesting to note.

Subgraphs

I decided to begin investigating by looking at very small graphs. For example, imagine a 2x2 grass patch. We can easily list all the solutions. Noticeably, if you enter a 2x2 graph on the northwestern tile, you will exit either by the northeastern tile or the southwest side. There is no way to exit on the southeastern tile. If you enter a 2x2 grass patch, you cannot exit through the tile diagonal from the one you entered from.

I then looked at 3x3 graphs. These also had many interesting patterns. These are all the successful patterns. I start at the northwest corner, but the only successful paths involve starting at one of the corners, and the solution sare the same for any corner, so if you wanted to see it at another corner, just rotate it so the entry point is at your desired corner.

For example, many of the solutions were similar to another solution I had already done, just rotated and flipped around. For example, ignoring the exit/entry points, #1 and #5 are the same graph, just rotated and flipped. #3 and #7 share a similar relationship. So do #4 and #8. This suggested that the possible solutions could be reduced to some base solution patterns upon which you can apply transformations.

I also looked as 2xN graphs.

Once I had explored these rudimentary graphs, I began playing with them. To create a solvable graph, you must take these solvable subgraphs and join them so there is no overlap and the exit of one is the entry of another. This suggests another property of solvable graphs: they can be decomposed to solvable subgraphs joined by exit/entry points.

This also leads us to another realization: if all that matters to create a solvable subgraph is whether you can line up the exit/entry points, the interior path you can take to get there doesn't really matter. It may be interesting to see the path taken inside for fun, but from a solvability perspective, all that matters is what possible exits are possible when you enter from a certain point. Whether there are 2 or 20 paths to get there doesn't matter. So with our 3x3 grid, entering from the NW allows us to exit through the NE, SE, SW, and CENTER. We can't exit through any of the center-cardinal directions. This is useful to know if we try to divide a block into 3x3 subgraphs. Additionally, the situation where you exit at center is only useful if that is the very final node left to visit, as otherwise you would have to backtrack to exit.

I think that on an intuitive level, when I look at grass patches and try to figure out if it is solvable, I'm trying to do something like that, break it down to solvable subgraphs I've seen before. For example, if you see a big nxn chunk inside a graph, you know you can do a zigzag sweep through it and then you just have to worry about the remaining parts.

I don't know if this is the best option for writing a way to solve this. I can do this easily because using human vision, you can see everything all at once. But you would need to walk through the graph to see what subgraphs it contains.