Cheese Bytes
Cheese with Holes (Emmental) - Developing
Cheese with Holes (Emmental) - Developing
Useful note with basic structure, but still has holes to fill.
Click the cheese icon to learn more

How to Escape With the Most Gold

Author: guiferviz Created: Last Modified:

You enter a gold mine with one goal: to become filthy rich. But there’s a catch. Every step you take collects gold and collapses the tunnel behind you. There’s no going back. Luckily, there’s another way out. So which route leaves you the richest by the time you escape?

Give it a try in the interactive demo below. Just click on the game and move with the arrow keys.

The Challenge

One might think the main challenge in a maze is to find the shortest path and get out as quickly as possible. But in our case, things are a bit different. We do not want to escape fast, we want to escape rich.

Finding just any path is easy. Finding the shortest one is also easy. But finding the longest one? That is a completely different challenge.

The main reason this problem is so difficult is that, in principle, we need to consider every possible path to make sure we are not missing one that yields more gold. And the number of possible paths grows very quickly with the size of the map.

We often underestimate the power of combinatorics. For example, this simple map already has 90 different paths. Yes, 90, all completely different from each other. Which one is the best? It turns out that one of them yields 87 units of gold. Have you found that path?

If not, I encourage you to try the game again above. Below these lines you will find a gallery with all possible paths, ordered from worst (shortest) to best (longest).

If we are able to find all paths, then finding the one that gives us the most gold is simply a matter of picking the longest one. In this Cheese Byte, we will first look at how to find all possible paths, and then how to optimize the process so we do not waste time exploring paths we already know are not good.

Map Representation

Before we start searching for paths, we need to move from a visual representation to something a computer can actually work with.

In our case, the mine can be naturally represented as a grid, where each cell is either a wall or an open space. To simplify boundary checks, we’ll assume that the entire border of the grid is always made up of walls. This way, we never need to check whether we’ve stepped outside the grid — any move from a non-wall cell is guaranteed to land on another valid cell.

For simplicity, we will assume that every walkable cell contains the same amount of gold. The ideas in this article can be easily extended to the more general case where each cell contains a different amount. In that version of the problem, the goal is no longer to find the longest path, but the one that maximizes the total amount of gold collected.

In Python, we can represent the mine as a list of strings. Each string corresponds to a row in the grid, and all rows must have the same length. The character # represents a wall, while . represents an open path. We also need to specify the starting and ending positions, which we can do with the characters S and E respectively.

Feel free to modify the map as you like, either by editing the code or using the interactive editor. Changes in one representation (code or visual) will be automatically reflected in the other.

Before moving on, it is useful to promote the start and exit positions to named constants. We will also define a Cell type alias so the rest of the article can talk about positions in a compact way.

The visual below computes START and END by executing the Python code on the left against the current map.

Play Your Own Map

Before we dive into the algorithms, I encourage you to try the game again with the map you have just created. Can you find the best path? How many paths do you think there are? Do you feel like you have a good strategy to find the best path?

# Finding All Paths

Finding Neighbors

The first building block of any path-finding algorithm is the ability to find the neighbors of a given cell. A neighbor is any adjacent cell (up, down, left, or right) that is not a wall.

Click any open cell on the map to see its neighbors highlighted. You can also edit the function on the left to experiment. If you really want to challenge yourself, try to implement the function without looking at the solution. Just remove the function implementation leaving the name as it is.

The small numbers drawn on the highlighted cells show the order in which neighbors(...) returns them. That order is not an intrinsic property of the map, but it does matter for algorithms such as DFS, because DFS will normally explore neighbors in exactly that order.

Useful experiments:

  • What happens if you replace the grid[nr][nc] != '#' condition with grid[nr][nc] == '.'? Does it work in the same way? Why or why not?
  • Change the order of MOVES. How does that affect the numbering in the visual, and later the order in which DFS explores the mine?
  • Return a list instead of yielding one neighbor at a time. Does it change the result, or only the style of the code?

A First DFS

Now that we can enumerate neighbors, a natural next step is depth-first search. The idea is simple: visit a cell, add it to the current path, recursively try all valid neighbors, and backtrack when a branch gets stuck.

The visual below adds a small show_state(...) call at the key moments of the search so we can replay it step by step. That helper is only there to tell the visual what state to paint; the DFS logic itself stays the same.

Ideas to explore in the DFS code:

  • What happens if you move the if current == end check before path.append(current)?
  • What happens if you don’t call path.pop()?
  • What changes if you call show_state(...) only when entering a cell, but not when backtracking? What if you do the opposite and call it only when backtracking?

DFS with Backtracking

The first DFS stops as soon as it finds one route to the exit. To maximize the gold, we need to keep exploring and undo each choice when we return from a branch. That is exactly what backtracking does.

This version returns the best path found below each recursive call. At the end, it paints only the final best path so the replay clearly separates exploration from the final answer.

Optimizations

WIP :(

MINE_MAP = [
    "#######################",
    "#...#.........#.......#",
    "###.#.#.#######.###.#.#",
    "#.#.#S#.#.....#...#.#.#",
    "#.#.#.###.###.###.#.###",
    "#...#...#...#.#...#...#",
    "#.###.#.###.#.#.#####.#",
    "#...#.#...#.#.....#...#",
    "###.#.#.###.#####.#.###",
    "#.#.#.#.#.........#...#",
    "#.#.#.#.#.#####.E.###.#",
    "#...#.........#.#.....#",
    "#.#########.#.#.#.###.#",
    "#.#.....#...#.#.#.....#",
    "#.#.###.#.###.###.#.###",
    "#...#.............#...#",
    "#######################",
]

This map is very interesting because we can logically deduce the best path without having to explore all 116 possible routes. Computer takes around 10k steps to find the best path, but we, as a humans can also find it just by using some logic.

© 2026 Cheese 🧀 Bytes