View source for Crunching the numbers: Graph theory

{{Article|
type=column |
picture=GraphTheory1.png |
caption=Can you cross each bridge only once? |
weekday=Sunday |
day=7 |
month=8 |
year=2011 |
time=06:08:48 |
discusstype=bmgf |
discusslink=116327 |
sourcetype=column |
sourcename=Danielle Detering |
sourcelink=User:Daniedeter |
user=Danielle Detering |
userlink=User:Daniedeter |
tagline=Enhance your game with the power of math |
blurb=In a city called Königsberg, in a section of the Pregel River, there are two islands. Between the two islands and the mainland, there were seven bridges. There is a historic puzzle relating to these bridges: see if you can find a way to cross each bridge only once. }}
{{CategorizeIn|Columns|8|11}}

In a city called {{wp|Königsberg}}, in a section of the Pregel River, there are two islands. Between the two islands and the mainland, there were seven bridges in a configuration like the image below.

[[Image:GraphTheory1.png]]

There is a historic puzzle relating to these bridges: see if you can find a way to cross each bridge only once. You’re not allowed to swim across the rivers, fly across, or teleport across. You can only use the bridges as a method to get to the islands or the mainlands, and when you start crossing a bridge, you have to cross it completely. No crossing halfway and then turning around.

Have you solved it yet? Neither have I. In fact, it was proven by the famous mathematician {{wp|Leonhard Euler}} to be impossible to solve. Here’s how: Euler called each land mass a node and each bridge an edge, and constructed a graph that probably resembled the image to the left.
[[Image:GraphTheory2.png|thumb|left|Euler's graph]]

He then made the observation that if a landmass was not a place to either start or finish, then there should be an even number of bridges so that half of the bridges would be used to get to the landmass and the other half would be used to leave. Since all four of the nodes had an odd number of edges, that would mean each landmass is an endpoint. As there could only be two endpoints (a place to start and a place to finish), then it was impossible to cross each bridge only once.

Euler’s proof created an entirely new branch of mathematics called graph theory. Whether game designers have realized it or not, many puzzles can easily be represented with graph theory, making them substantially easier to solve. One such type of puzzle often stumped me as a kid: sliding ice puzzles. These brainteasers have shown up in the icy areas of Pokémon since {{bp|Generation II}}, but they aren’t unique to Game Freak’s creation. In Golden Sun, many djinn are obtained by correctly sliding down the right path, and in {{wp|Tales of Symphonia}}, one such puzzle was done in space rather than on ice.
Let’s take a look at a sliding ice puzzle found in the Generation II version of the Ice Path:

[[Image:GraphTheory3.png]]

We begin by making the starting spots the first two nodes:

[[Image:GraphTheory4.png]]

We now map all the possible choices we can make from 1 or 2. Since we start sliding as soon as we touch the ice, the only place we can go from 2 is right, and the only place we can go from 1 is up.

[[Image:GraphTheory5.png]]

When we make our graph, we don’t have to mirror the position of our puzzle. In fact, this may make things worse as the point of graphing out these puzzles is to simplify, and matching the positioning could make our graph very messy.
Now let’s take a look at 4. Besides going back to 2, we can also go up or down. But if we go either of those directions, we can’t immediately go back to 4. We’ll represent this as an arrow on our graph, which is more formally called a directed edge.

[[Image:GraphTheory6.png]]

As we fill out our map, it’s important to keep track of which paths are useful. For example, after mapping a few more nodes, we end up with the following graph.

[[Image:GraphTheory7.png]]

We can see that if we follow the path starting at 1, we’ll just end up following the path starting at 2. Therefore, we know that we can completely ignore that branch of our map. We can also ignore going to 6, 9, and 10 since we can get to 11 faster by going through 5.

[[Image:GraphTheory8.png]]

Finally, a completely graphed out map will look like this.

[[Image:GraphTheory9.png]]

And taking out all the redundant paths, we end up with the most optimal solution to our slippery puzzle.

[[Image:GraphTheory10.png]]

Of course, you don’t have to literally draw everything out when you’re solving these puzzles. A lot of people do this in their head without even realizing it (although, when I try to do it in my head, I tend to get lost in my own thoughts). As with most things in life, a little bit of practice goes a long way. And who knows? If you get good a graph theory, maybe someday you’ll be the one designing puzzles for Pokémon.

{{Crunching}}