12

There's actually 2 parts to question;

  • How to determine how hard your own maze is (knowing the solution)

  • How to determine how hard another's maze is (without knowing the solution)

What are some general rules and guidelines you can use to figure out how difficult a maze is?

warspyking
  • 14,500
  • 10
  • 78
  • 144
  • Is this a normal maze, so to speak? (i.e. only walls, want to get from one point to another) – Sp3000 Dec 04 '14 at 19:41
  • For point 2, if you don't know the solution after a few minutes of trying to determine how hard it is, I'd say that alone says something about the difficulty. – Set Big O Dec 04 '14 at 20:13
  • 1
    To expand on Sp3000's point: a maze with unusual rules, like one-way paths or walls you can pass through under certain conditions, will be much harder than a conventional maze. (In my mind, they're also more fun.) – Kevin Dec 04 '14 at 20:31
  • 2
    For related reading on maze difficulty (and other maze-related topics), check out Think Labyrinth. – Set Big O Dec 04 '14 at 20:37
  • Define "hard". Do we mean "hard for a person" (which can be accomplished by printing the maze really really small, or orienting it strangely) or "hard for a computer" (which likely has provable mathematical properties)? – Chris Hayes Dec 04 '14 at 22:39

3 Answers3

10

I would say that there is no good clear cut answer to this question. The best way to get an idea of how difficult the maze is is to have people try the maze and see how long it takes to be completed. Some factors I would consider, however, are:

Number of Forks leading into Dead Ends or Loops
The more forks you have the more locations you have to get off of the correct path.

Number of Forks along the correct path
If you only have to cross one fork on the ideal path then you only have to get lucky once. The forks work best if they are evenly distributed among the different possible paths.

Length of incorrect paths
A short, linear dead end is only a short distraction. Increasing the complexity of incorrect paths can make them even more of a nuisance.

Path of the ideal solution
If you start on the left and pretty much only ever have to work your way right in a straight line, then the maze will be really pretty easy. For harder mazes the solution should at some points get close to the end, while at some points wind further and further away from the end.

Size of the maze
The bigger the maze the more room you have to work with and the more space you have for longer false paths, dead ends, forks etc.

Shape of the maze
It is my opinion that circular mazes tend to be a little more challenging because the circular paths are a little harder to keep track of than straight paths. Others, however, may have different preferences.

Warlord 099
  • 1,784
  • 1
  • 11
  • 13
  • With regards to the path, I always heavily included loops in my mazes, to prevent "always turn left" or "always turn right" from working. – Michael Dec 04 '14 at 20:27
  • @Michael That was the main reason I said Dead Ends/Forks. Initially I was thinking dead ends, but the fork is what adds the complexity. – Warlord 099 Dec 04 '14 at 20:32
  • Nice answer, I'll wait for a few more before deciding to accept. – warspyking Dec 04 '14 at 20:36
  • @Michael Including loops is only a deterrent if the start and finish are on opposite "sides" of the loop. If both are inside the loop, or both are outside, then the "always turn left/right" strategy will still work. – camerondm9 Dec 05 '14 at 00:26
2

For a more rigorous mathematical analysis, see this paper from 2001. It proposes an objective measure of the 'difficulty' of a maze, based on branching and complexity.

user26274
  • 21
  • 1
2

The best (most accurate and thorough) way to rate how difficult a maze is to perform a controlled study. Unfortunately, this requires a lot of time and people, the more the better. Put each person in a room by themself and time how long it takes them to complete the maze. The longer it takes, the harder the maze is. Make sure you find people who are interested in solving mazes. For better results, perform some kind of baseline test with which to weight the results. For instance, give each person what you consider an easy maze, and see how long each person takes to solve it. Then do the same with what you consider a hard maze. Those who solve the "hard" maze faster should have longer times weighted more, because they have shown they are good at solving hard mazes. Conversely those who solve the "easy" maze faster should have shorter times weight more, because they have shown that they are good at solving easy mazes. For better results, consult a statistician regarding the specifics about the tests you want to run.

This answers the question of how to determine how difficult mazes are that you know the solution to. Once you have got enough data points you can define various maze metrics and and they objectively score each maze based on these metrics. As another answer suggests, metrics might include the size and shape of the maze, and various topological conditions. Run correlations between each metric and the relative score obtained from the first step. Once you have these numbers you can then take mazes which you don't know the solution to, measure the metrics for those mazes, and apply the previously determined correlations in order to predict the difficulty levels. If you have the time and money, you can refine your model over time by running additional studies against these predictions, determine how well they predict the results, tweak your metrics, and update your models accordingly.

Michael
  • 1,637
  • 1
  • 11
  • 15
  • Maybe not the most useful answer in the context of the question asked, but definitely the most correct and sincere answer. +1 from me and I would accept it. – BmyGuest Dec 05 '14 at 19:33