2,132
edits
Crunching the numbers: Graph theory (view source)
Revision as of 04:08, 4 September 2011
, 4 September 2011adding nav template
(Created page with "{{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=none...") |
(adding nav template) |
||
| (2 intermediate revisions by one other user not shown) | |||
| Line 8: | Line 8: | ||
year=2011 | | year=2011 | | ||
time=06:08:48 | | time=06:08:48 | | ||
discusstype= | discusstype=bmgf | | ||
discusslink= | | discusslink=116327 | | ||
sourcetype=column | | sourcetype=column | | ||
sourcename=Danielle Detering | | sourcename=Danielle Detering | | ||
| Line 30: | Line 30: | ||
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. | 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 | 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: | Let’s take a look at a sliding ice puzzle found in the Generation II version of the Ice Path: | ||
| Line 65: | Line 65: | ||
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. | 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}} | |||