Making Challenging Mazes

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 ...