#The hardest maze in the world salved free#

If we use the random variant, it’s randomly trying things out until you hit something which works. It’s trying every possible solution until you hit on one which works. What do our maze-solving algorithms look like in a more general problem-solving context?īrute-force search is, well, brute-force search. Basically any problem whose solution is a sequence of steps (or can be made a sequence of steps). It turns out all sorts of things can be cast as path search problems: puzzles, planning, and of course navigation.

In AI, path search is used to think about solving problems in general. … the best-first solution in this case is almost identical to DFS. That’s what happens if we apply best-first to the Pinocchio maze: If the solution path wiggles around a lot, especially on a large scale, then heuristic search won’t help much. If we use straight-line distance from the goal as an heuristic, then heuristic search is going to work well if-and-only-if the solution path is relatively straight. Here’s an example where best-first works very well:īy aggressively exploring the path closest to the goal, Pluto reaches his bone without having to explore most of the maze.īut heuristic search comes with a catch: it’s only as good as the heuristic. Distance from the goal serves as an heuristic to steer the search. But rather than brute-force searching all the paths, best-first focuses on paths which are closest to the goal “as the bird flies”. Like breadth-first search, best-first explores multiple paths in parallel. The best-known of these is A*, but we’ll use the more-human-intuitive “greedy best-first” search. If we’re not sure which way to go, we take the direction which points more toward the goal.įormalizing this approach leads to heuristic search algorithms. Just trying out paths at random will usually solve a maze about as quickly as DFS or BFS (as long as you keep track of what you’ve already tried).Ī human solving a maze usually tries to work their way closer to the end. They don’t really do anything clever, they just crawl through the whole maze until they stumble on a solution. There’s lots more to say about these two algorithms, but main point is what they have in common: these are brute-force methods. It’s “breadth-first”: it explores all paths at once, keeping the search as wide as possible. It’s like a plant: every time BFS hits an intersection, it splits and goes both ways. In this snapshot, we’ve hit three dead ends, and we have four separate “branches” still exploring the maze. We go as far as we can down one path (“depth-first”) and if we hit a dead end, we turn around, back up, and try another path.īreadth-first search, on the other hand, tries all paths in parallel: Then we turn around and go back, find another right turn, and hit another dead end.

So, in the Pinoccchio maze, we start out by turning right and running until we hit a wall (the first “x”). Here’s DFS, applied to the Pinocchio maze above:īasically, the DFS rule is “always take the right-most path which you haven’t already explored”.

The very first path search algorithms students typically learn are depth-first search (DFS) and breadth-first search (BFS). In algorithms classes, this problem is called “path search”. You have a maze, with a start point and an end point, and you are searching for a path through it.

#The hardest maze in the world salved free#

I’ll assume no technical background at all, so if you’ve seen some of this stuff before, feel free to skim it. Then we’ll move on to the interesting part: two techniques which often work better for everyday problem solving, and lend some interesting insights when applied to mazes. Next, we’ll talk about how these algorithms can fall short for everyday problem solving. We’ll start off with some traditional path-search algorithms (DFS, BFS, heuristic). It turns out that they can all be applied to mazes, so I’ll use some disney-themed mazes to illustrate each approach. I want to talk about a few different approaches to general problem solving (for humans).