# Making Challenging Mazes

Understand how to make more challenging mazes using the longest path algorithm.

## We'll cover the following

## Exploring solution length

There are lots of ways to make a maze more challenging, but many of them are highly subjective and difficult to quantify. One of the considerations to keep in mind while designing challenging mazes is the solution length. Let us see how Dijkstra’s algorithm again manages to make it successful.

In general, the longer the path, the more difficult the maze. Ideally, then, if we want a more challenging maze, we want to identify the longest path through it. We then put the entrance of our maze at one end of the path and drop the goal at the other end, and we’ve raised the difficulty level. Easy as that.

A general solution to the *longest path* problem—one that works for any arbitrary graph or grid—is what mathematicians call an **NP-hard **problem. Fortunately, we can narrow our requirements a bit. If we’re only looking to find the longest path through a perfect maze, there happen to be a few different ways to tackle it, and Dijkstra’s is one of them.

It might seem counterintuitive that an algorithm we just used to find a *shortest* path can also be used to find a *longest* path, but remember: Dijkstra’s has conveniently labeled each cell with a distance value. All we have to do is look for the largest one in the maze. That will tell us the longest path from our starting point to that cell.

We have to be careful, though. This is not necessarily going to be *the* longest path in the maze. If our starting cell happens to be somewhere in the middle of the actual longest path, then the longest path from that cell will be shorter than the real one. The trick is to run the algorithm twice. The first time, we find the most distant cell from some arbitrary starting point. The second time, we turn it around and use that most distant cell as the starting point, letting Dijkstra’s tell us the most distant cell from there. We’re basically asking Dijkstra’s to tell us the most distant point relative to the most distant point.

To make this real, we need to introduce a new method to our `Distances`

class, to tell us which cell is furthest from the root and just how far away it is. We'll add the `max`

method to the `Distances`

class in the `distances.rb`

file, just after the `path_to`

method. The updated code for the `Distances`

class is given below with the `max`

method highlighted.

### The updated `Distances`

class

Get hands-on with 1200+ tech skills courses.