Python and the Legend of Zelda

Using brute force to solve a classic grid-based puzzle

Spoiler warning for retro gamers — this article contains late-game details from Legend of Zelda: Oracle of Ages (Game Boy Color).

The Context

In the northeast corner of present-day Lynna City, just before reaching the great Maku Tree, lies the entrance to Hero’s Cave, an underground pathway which becomes increasingly accessible as the game progresses.

As of this writing, I’ve yet to reach the furthest depths of the cave, where a treasure of some kind surely awaits (and hopefully not just another Gasha Seed). So, while I can’t speak for the cave as a hole (get it?), I can confirm that it is filled to the brim with interesting puzzles, which all seem to require a bit more ingenuity than usual to solve.

Being no stranger to the Legend of Zelda series (I even wore a rose gold Triforce lapel pin and bright green Zelda socks with white Hylian Crests on them at my wedding), I was able to quite easily solve the first handful of puzzles nearest the cave’s entrance. This trend continued until I encountered a certain grid-based puzzle which is the focus of this article.

The Puzzle

Fans of the series will surely recognize this type of puzzle, but for those who aren’t familiar, here’s how it works.

A zoomed out view of the entire puzzle, normally not visible all at once due to the limited screen resolution of the Game Boy Color.

Link, hero of Hyrule and notorious rupee thief, enters the room via the dirt path in the corridor along the right wall, initiating the puzzle by stepping foot upon the blue tile in the rightmost column of the center row. This tile immediately changes color, from blue to red, as will each additional tile Link crosses.

The goal of puzzles like this one is generally to guide Link along an uninterrupted path which includes all blue tiles in the room. However, the path must not cross the same tile more than once, move diagonally, or include the yellow tile near the center of the room (where, if we’re lucky, our prize will eventually appear).

This puzzle’s difficulty arises primarily from the placement of the four stone statues, which cannot be moved. We’ll soon discover that their placement is as clever as it is annoyingly off-center.

My first somewhat respectable attempt looked a bit like the image below, with only a single blue tile remaining. This is going to be a walk in the park… or so I thought.

Nearly solved in just a few tries, this puzzle is surely a breeze, right?

This was one of many attempts which resulted in only a single blue tile remaining.

Before long, I’d become quite adept at almost solving the puzzle, to the point of being able to position the remaining blue tile anywhere I’d like on the grid, but I couldn’t manage to actually eliminate it. Invariably, a time would come where the path must fork, making the unchosen path inaccessible for the remainder of the attempt.

Consider the example shown below.

So close, yet so far.

After failing to recognize just what it was about this puzzle that made it so tricky, I decided that brute force was the next best option. And what better way to apply brute force than programmatically

¹

!

And with that, I fired up my unregistered copy of Sublime Text 3 and got to work.

The Code

First things first, the puzzle itself must be represented somehow. It felt natural to represent the puzzle grid using a list, where each element represents a row in the grid. Each row element is another list where each element represents the state of a column in that row of the grid.

default_board = [
    [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ],
    [ 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1 ],
    [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ],
    [ 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1 ],
    [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0 ],
    [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ],
    [ 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1 ],
    [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ],
    [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ],
]

I chose to represent the state of each tile in the puzzle as either a 0 or a 1, where 1s represent tiles which are yet to be included in the solution. This will make it easy to tell if an attempted solution has covered the entire board, but we’ll get to that later.

In the board’s default state, shown above, the placement of the 0s align with the statue locations, the yellow space near the center of the grid, and also the first tile Link walks across upon entering the room. These are all spaces which must not be included in the path.

Next, it was clear that Link’s starting position on the board should be stored somehow, and for readability purposes, I created two variables to store Link’s initial coordinates in the grid.

start_x = 12
start_y = 4

With the puzzle layout and initial coordinates out of the way, I needed some way to represent each attempt, as there would soon be a lot of them. I began with a simple class called Attempt which has the basic properties needed for each instance to keep track of its own progress.

class Attempt:
    x = y = 0
    path = []
    board = []

Properties x and y represent Link’s current position as the attempt progresses. The path property will store each move along the way (e.g. “up”, “left”, etc.). Finally, the board property stores its own modified version of the default board, which will be used to verify that a potential solution has crossed all of the tiles in the puzzle.

Several important operations are also encapsulated in the Attempt class’s methods.

The first of these methods is one called available_directions, which helps Link “look” in all 4 directions, returning a list of Strings representing each direction where a blue tile is immediately found.

def available_directions(self):
    directions = []
    if self.can_move_up():
        directions.append("up")
    if self.can_move_down():
        directions.append("down")
    if self.can_move_left():
        directions.append("left")
    if self.can_move_right():
        directions.append("right")
    return directions

The available_directions method relies on direction-specific methods, such as can_move_up, which handle checking first that the next tile in the given direction isn’t out-of-bounds, and then that it contains a tile which has yet to be included in the solution path

²

.

def can_move_up(self):
    if self.y == 0: return False
    return bool(self.board[self.y-1][self.x])

The next method in the Attempt class is move, which updates the state of the instance each time it progresses.

First, the move method looks at Link’s next direction and appropriately updates the properties which track his current position during the solution attempt

³

.

def move(self, direction):
    if direction == "up":
        self.y -= 1
    elif direction == "down":
        self.y += 1
    elif direction == "left":
        self.x -= 1
    elif direction == "right":
        self.x += 1
    ...

Next, the move method appends the direction String to the list property which stores the solution path itself.

def move(self, direction):
    ...
    self.path.append(direction)

Finally, the move method updates the property which tracks the state of the grid, setting the tile at Link’s new position to 0. This prevents Link from visiting this tile again, and will be used later to verify that all tiles have been visited during this solution attempt.

def move(self, direction):
    ...
    self.board[self.y][self.x] = 0

The last method within the Attempt class is one called solved. This method returns a boolean value indicating whether or not the state of this instance currently contains a valid solution to the puzzle.

def solved(self):
    for row in range(len(self.board)):
        for column in range(len(self.board[row])):
            if self.board[row][column]:
                return False
    return True

The first for loop iterates over each row of the puzzle grid. As each row is inspected, a second for loop iterates over each column of that row. Using this combination of loops, each of the 117 tiles on the puzzle can be evaluated. A Boolean value of False is returned if any tile contains a positive truth value (which would be a 1, in this case). If no tiles are found to have a positive truth value, the method simply returns a Boolean value of True, indicating that the Attempt instance contains a valid puzzle solution.

To bring all this together, I used a recursive function which I call process, because naming things is hard.

The process function carries out 3 important tasks, and 1 additional task (the importance of which is questionable).

First, the process function checks to see if a positive truth value was provided for the direction argument, which defaults to an empty String. If so, the Attempt instance provided in the attempt argument is told to move in the given direction.

def process(attempt, direction = ''):
    if direction:
        attempt.move(direction)
    ...

Next, the Attempt instance is checked to see if it contains a valid solution to the puzzle. If so, that solution is printed so we can follow the path ourselves in-game

⁴

.

def process(attempt, direction = ''):
    ...
    if attempt.solved():
        print(attempt.path)

Once the Attempt instance is checked for a solution, a for loop is used to iterate over all directions from Link’s current position which still contain blue tiles. Each available direction is paired with a copy of the current Attempt instance (using deepcopy), both of which are passed to a recursive call to process. This effectively creates distinct representations of each solution attempt as new paths are discovered.

def process(attempt, direction = ''):
    ...
    for direction in attempt.available_directions():
        new_attempt = deepcopy(attempt)
        process(new_attempt, direction)

For example, imagine that an Attempt instance’s path is currently [“up”, “right”], and the available_directions method returns [“right”, “down”]. In this situation, two new Attempt instances will be created. After each instance is updated in the subsequent process invocation, the two new instances will contain path values of [“up”, “right”, “right”] and [“up”, “right”, “down”], respectively.

Finally, an attempt is made to limit the memory usage of the script by deleting the Attempt instance which was passed to process, since it is no longer needed at this point

⁵

.

def process(attempt, direction = ''):
    ...
    del attempt

All that’s left is to get the process started, which happens in a simple main function which sets up an initial Attempt instance and makes the first call to the recursive process function.

def main():
    attempt = Attempt(start_x, start_y, [], default_board)
    process(attempt)

The Result

So, how well does the script work? Well, when it comes to actually finding a solution, it doesn’t.

As far as I can tell, the script executes correctly, performing around 15,000 moves per second on my first generation M1 Mac mini.

Adding additional print statements (the ultimate method of debugging) reveals nothing I find unexpected. The generated paths seem quite sane, e.g. no “up” moves immediately followed by “down” moves, etc.

No runtime errors are produced.

Yet, despite all of this, after allowing the script to execute for about 7 hours, no solutions were reported. Even more surprising is that it was still running after all that time. Some quick maths suggest that around 350 million unique moves would’ve been processed in that amount of time.

I’ve undoubtedly made some kind of mistake in the script, but there’s a bigger issue here.

The Twist

If you recall, I mentioned earlier that the puzzles of Hero’s Cave require an extra bit of clever thinking to solve. Well, as it turns out, this puzzle is no exception.

It just so happens that there are no valid solutions to the puzzle which can be entered simply by following the rules described in this article. At the very least, one blue tile will always remain inaccessible.

Anyone familiar with the Legend of Zelda series knows that in-game progression generally hinges on the abilities Link acquires throughout his journey. These new abilities are often granted through the discovery and subsequent use of items, such as bombs and seeds, and tools, such as the Power Glove and Hookshot.

When it comes to this puzzle, one tool in particular happens to be the missing Link (sorry). That tool is the Cane of Somaria.

The Cane of Somaria, as depicted in Oracle of Ages.

The Cane of Somaria is a tool which allows Link to create a single block which can then be pushed as needed, and even climbed upon in certain platforming areas.

So what does it have to do with this puzzle? Well, it just so happens that the block created by the Cane of Somaria is red. It’s also the same size as the tiles in this grid puzzle. Are you thinking what I’m thinking?

Using the Cane of Somaria to complete the puzzle.

That’s right! Using the Cane of Somaria, we can complete the puzzle by simply walking over to the remaining blue tile, wherever it happens to be, and covering it with a red block.

I’ll be honest. At first, I was a little disappointed that there wasn’t what I would call a legitimate solution to the puzzle. But it wasn’t long before I began to appreciate the puzzle for what it is. It’s clever, and fits the theme of Hero’s Cave quite well, but more than that, I’m impressed by the fact that it’s only very nearly possible. There are countless paths that result in a single remaining blue tile, and exactly zero which cover them all.

Question for you, the reader: How is such a puzzle designed in the first place?

While I imagine some fancy bit of maths was involved, I don’t possess the formal education to speculate about the details.

Personally, I would design such a puzzle by first designing a script much like the one in this article and relying upon it to verify all possible solutions for all possible combinations of statue placements and other variables, including a few different room (grid) sizes. In fact, that’s precisely what I did in 2019 while developing a game prototype called Fennec, which was inspired by one of my all-time favorite games, The Witness.

This puzzle definitely gave me flashbacks to playing The Witness for the first time, which doesn’t happen often! Hopefully you enjoyed reading about my convoluted attempts to solve it as much as I enjoyed making them.

The Complete Script

For the sake of completeness, here is the script in its entirety, including my original comments.

#!/usr/bin/env python3

import sys
import signal

from copy import deepcopy

# Catch ^C.
def handle_sigint(s, f):
    print('Stopping script...')
    sys.exit(0)
signal.signal(signal.SIGINT, handle_sigint)

# Starting coordinates.
start_x = 12
start_y = 4

# Default board state.
default_board = [
    [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ],
    [ 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1 ],
    [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ],
    [ 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1 ],
    [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0 ],
    [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ],
    [ 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1 ],
    [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ],
    [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ],
]

# Store game board state and associated path for each attempt.
class Attempt:

    # Current coordinates.
    x = y = 0

    # Path used to reach the associated game board state.
    path = []

    # Game board state.
    board = []

    # Constructor.
    def __init__(self, x, y, path, board):
        self.x = x
        self.y = y
        self.path = path
        self.board = board

    # Get a list of directions which can currently be accessed.
    def available_directions(self):

        # Start with an empty list.
        directions = []

        # Check all four directions every time.
        if self.can_move_up():
            directions.append("up")
        if self.can_move_down():
            directions.append("down")
        if self.can_move_left():
            directions.append("left")
        if self.can_move_right():
            directions.append("right")

        # Return the list of moveable directions.
        return directions

    # Check for non-visited cell in the up direction.
    def can_move_up(self):

        # Don't move off the board.
        if self.y == 0: return False

        # Check one space up.
        return bool(self.board[self.y-1][self.x])

    # Check for non-visited cell in the down direction.
    def can_move_down(self):

        # Don't move off the board.
        if self.y == 8: return False

        # Check one space down.
        return bool(self.board[self.y+1][self.x])

    # Check for non-visited cell to the left.
    def can_move_left(self):

        # Don't move off the board.
        if self.x == 0: return False

        # Check one space to the left.
        return bool(self.board[self.y][self.x-1])

    # Check for non-visited cell to the right.
    def can_move_right(self):

        # Don't move off the board.
        if self.x == 12: return False

        # Check one space to the right.
        return bool(self.board[self.y][self.x+1])

    # Move in the given direction.
    def move(self, direction):

        # Check the direction and update the current position.
        if direction == "up":
            self.y -= 1
        elif direction == "down":
            self.y += 1
        elif direction == "left":
            self.x -= 1
        elif direction == "right":
            self.x += 1

        # Update the path with the current direction.
        self.path.append(direction)

        # Mark the current position as visited in
        # the game board.
        self.board[self.y][self.x] = 0

    # Check if the game board is solved.
    def solved(self):

        # Check every row.
        for row in range(len(self.board)):

            # Check every column.
            for column in range(len(self.board[row])):

                # Return _not_ solved if any available
                # spaces are found.
                if self.board[row][column]: return False

        # If no available spaces were found, this must
        # be a solved attempt.
        return True

# Initial execution point of the script.
def main():

    # Create an initial attempt to represent where
    # we begin in the puzzle.
    attempt = Attempt(start_x, start_y, [], default_board)

    # Begin processing the initial Attempt instance.
    process(attempt)

# Continue the given attempt by moving in the given direction.
def process(attempt, direction = ''):

    # Check if a direction was given.
    if direction:

        # Update the attempt by moving in the given direction.
        attempt.move(direction)

    # Check if this attempt is a solution.
    if attempt.solved():

        # Print solution.
        print(attempt.path)

    # Iterate over each available direction (there will
    # be none if the attempt is solved).
    for direction in attempt.available_directions():

        # Make a new Attempt instance, continuing where
        # the previous attempt left off.
        new_attempt = deepcopy(attempt)

        # Call this process function again for the new attempt.
        process(new_attempt, direction)

    # Remove the previous attempt from memory.
    del attempt

# Execute main function.
if __name__== "__main__":
    main()

1. I will admit that Python is neither my favorite language, nor a language I’ve all that much experience with, but nevertheless, it felt like the right tool for the job.

2. While I’m confident this code could be compacted and perhaps made more efficient, I’m happy with its readability and decided against investing time in prematurely optimizing or potentially over-engineering this part of the script.

3. A match statement could be used instead of a series of conditions which evaluate the same variable, however the system where I wrote this script had Python 3.8.x installed, and I believe the match statement was added in Python 3.10.

4. No return statement is used after checking for a valid solution because a solved Attempt instance would have no remaining tiles for Link to visit, as described by the statements that follow.

5. Perhaps the attempt variable would fall out of scope on its own by this time, or maybe the statement is reached later than expected due to occurring after the recursive function invocation. Probably this could be performed sooner with a little refactoring, but the script seemed to perform well enough, so I didn’t worry too much about it.