G12FCO -- Formal Computation

Problem Class 3 -- Backtracking/Feasibility -- solutions

Problem 1: -- Mazes.

There are lots of ways, and in modules on graph theory and similar topics you may well find out more than you ever thought you wished to know about solving mazes! Here is one way. We colour-code the roads and villages. White villages are not-yet-visited, black ones have been or are being explored. White roads are unexplored, yellow [brick] roads are the current route, and black roads have been explored and found useless.

Step 1: Paint all roads and villages white.
Step 2: Call mazesolve (START); if this returns FALSE, there is no route; if it returns TRUE, the route is marked out in yellow.

Here mazesolve is given by:

mazesolve (CURRENT)
   if CURRENT = FINISH then return TRUE endif
   if CURRENT is painted black then return FALSE endif
   paint CURRENT black
   for each road out of CURRENT do
      if road is white
         then paint road yellow
              NEXT = other end of this road
              if mazesolve (NEXT) then return TRUE endif
              paint road black
      endif
   endfor
   return FALSE

Painting the villages isn't actually necessary -- it suffices never to search a road twice -- but it saves us from including [unwanted] loops in the yellow path. As usual in backtracking algorithms, the typical invocation of the principal procedure simply does local explorations; all the hard work is done by the recursion.

Also as usual, you have to trust the recursion. If you believe that it works, then it is easy to see that it works -- we are simply exploring every possible way out of the current village and using the recursion to find whether we can get from here to FINISH. If you don't believe that it works, then it's just about impossible to explain or to analyse. If you find yourself in this position, I suggest [strongly!] that you try it with some friends:

Draw a graph on a large piece of paper [such as a newspaper]. Four or five villages will be quite enough. One person stands on each village. Paint the roads as indicated, and `invoke' the person standing on START. He or she then follows the above pseudo-code, `invoking' neighbours as instructed. When you invoke someone, you must wait for them to `return'. Even with so few villages, you'll find that you can see what happens if there are loops or blind alleys that you `happen' to explore first. Good luck! [This could probably make a good party game for mathematicians, somehow, depending on how close the neighbours are. G12FCO home page. Previous discussion. Next discussion. Problem class.
Copyright © Dr A. N. Walker, 1996, 2016.