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.

I wanted to explore what conditions meant that you could walk through each tile exactly once and what conditions meant that you couldn't. I had a sort of intuition for this when looking at a patch of grass, but I had never written it down. I decided to embark on a little journey - exploring grass patches to find out which ones you can walk through exactly once. This page is a record of that advenure.

Explanation

We can imagine 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. By imagining it as a graph, we know that what we are looking for is called a "Hamilton Path" - visiting every node exactly once. I'm going to refer to a patch where you can visit every tile exactly once (where you can create a Hamilton Path) as "solvable", and ones where you cannot as "unsolvable." (There is a lot of literature on Hamilton Paths and what makes them solvable or not. I decided to ignore all of it and find things out on my own. It's more fun that way!)

I'm also going to add some game-specific conditions here. In the games, you can't just spawn in the middle of a grass patch randomly. There may be objects or walls preventing you from starting at a certain grass patch, or which prevent you from jumping directly to those patches. This means when I'm looking at grass patches, I want to make it so we only consider paths that you can actually do in the game. If the game only lets you enter a grass patch from one tile, then I also want to assume we can only find a path from that one tile.

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 solutions are 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.

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 ports.

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.

Knowing this is pretty useful - we can look at a graph and imagine trying to tile it with the puzzle pieces we have. Not all shapes are going to be equally easy to tile. Additionally, some tiles are really hard to unite with other tiles.

The routes

Knowing this, let's actually look at the routes and take a crack at solving them. I sat down and went through all the routes in Emerald and tried to find a solution for them. (I ignored some very large ones like the ones on Cycling Road, and I also ignored areas like Petalburg Woods. Routes only!) Trying this out by hand showed me some interesting patterns about what made a route solvable or not. I also made a tool to confirm that a given patch did or did not have any solutions to make sure I wasn't missing anything myself - if you see a table with a bunch of filled in tiles, that's the tool! With that cleared up, let's go route by route and see how it goes.

Route 101

3/4 = 75%

Route 102

3/6 = 50%

Route 103

3/3 = 100%

Route 104

South

3/3 = 100%

North

0/1 = 0%

Total = 3/4 = 75%

Route 115

0/1 = 0%

Route 116

Incomplete

We know 2 of 3 are unsolvable

Route 117

We know 2 of solvable

The third one needs rechecking for hidden tiles

Route 110

Not touching the cycling path ;)

0/1 = 0%

Route 112

North

One is unsolvable

Other has hidden tiles, probably unsolvable

South

0/1

Route 113

One is solvable, other three do not appear to be but further research is required

Route 114

0/2

Route 118

2 are solvable

Bottom two need rechecking

Route 121

5/9 solvable

Route 123

Need rechecking, multiple hidden tiles

Patterns in Solvability

Diagonals

Imagine a perfectly good diagonal path. Now add one. You have now created a condition where it is impossible to solve it because you can never visit both tiles. All this because of the addition of one extra tile.

The T shape

Related to the t-shape is the ‘one left over’ problem. Many paths are almost solvable… except for one node.

This is the problem at the root of the T shape: a perfectly good line is spoiled by adding an extra node.

The center path here is immediately unsolvable because of this t-shape. We have two entry nodes but the only way to fulfil both is to immediately go from one to the other, and the rest of the graph is unfulfillable.

>2 1-degree Entries

Let us try solving some patches to see what problems we run into. When we start a patch, it is useful to note the possible entries.

This one from route 114 is quite illustrative. The player can only enter through the bottom two tiles. Let’s say we want to get all the tiles on the rigrht hand before we cover the left. If we try to do a serpentine pattern, we will find that the fact we have an odd number of rows means that our path will be tossed to the right - not the correct solution!

What if we try to hug the outline instead? This creates a problem because one patch of grass on the right hand side is left with 1-degree. This is a problem because as we noted earlier, you must enter or exit through a one-degree patch. But we did not enter through that patch of grass. This means we must end there. But we cannot end there because there is another one degree tile at the bottom. This means fulfilling both is mutually exclusive. The outline path won’t work. (as an aside, this is why outlining is rarely a good strategy, and also why diagonals are so tricky - to fill a diagonal requires some degree of outlining. Partial outlining may work for some grids but hugging the entire perimeter rarely works. You simply don’t end up with the freedom necessary to fill in the interior.)

If we go back to our earlier observation - that solvable graphs must be made of subgraphs that are also solvable - we see part of the problem with outlining. When you try to hug the perimeter of a diagonal, you are attempting to tile a graph using a solvable diagonal path at its outline. However this is a very inflexible shape, having entries only at the edges. And it is difficult to find pivot shapes that let you turn around to continue hugging the perimeter of the unfilled interior shape. Diagonals are not good tiling tools. And you’ll see in the solved graphs that do have diagonals, that I never outline them; I instead nest squares and rectangles to avoid precisely that situation.

It may also be interesting to examine the unsolvable graphs to see how many tiles are left over. Many of the unsolvable graphs are one tile away from being solved! Meanwhile, some have a fair amount of leftover tiles.

There are configurations that we know would cause unsolvable paths that we don’t see in this game, likely because they would make for ugly-looking patches of grass. For example, we could have two triangular shaped patches connected by a single patch of grass. The forced movement through that middle tile prevents finishing both patches. But how ugly would that be! The game designers clearly wanted natural looking patches of grass, which means grabbing that paint tool and just making blocks of grass. By accident, they ended up making many solvable graphs.

Fun fact - in Pokemon R/B/Y, the smallest unit you can use to tile the world is 4x4 player-sized tiles. The only grass tiles, to my knowledge, are fully filled 4x4. This means that every patch of grass is made by tiling together these 4x4 squares… R/B/Y is, indeed, solvable. 🙂