The systematic search with
Backtracking:
Negotiating a 3D maze
Ideally, a result will be obtainable by a straightforward calculation. If that is not possible, it may help to improve an initial approximation, or gradually restrict the number of plausible candidates. Failing that, and should the number of options not grow exponentially with the size of the problem, an exhaustive search may be acceptable. In that case, backtracking, a systematic search process, may help:
- Whenever there are several (legitimate) moves, one is made arbitrarily.
- Later on, if it appears that the algorithm blocks, the last decision made is revisited, and a different option taken.
- The program ends when a solution has been found (and is deemed to be close to the optimal.) If the program backtracks to the first decision made, and there are no more selections left, then there is no solution.
There are several nice programming exercises for backtracking: The problem of eight Queens, for example, requires to place as many on a standard chessboard, with none being in check. The knight problem, will move this piece to all the (remaining) squares on a standard chessboard, in 63 moves exactly. This will take longer, but is also a board exercise.
Another possibility is negotiating a 3D maze: A cubic block of flats has a number of rooms on each side- the program creates a 4x4x4 maze, but the numbers can be increased. Each room has four doors possibly leading to adjacent rooms, as well as two trapdoors, possibly leading to the rooms directly above and below. Some of the doors are locked- and unusable. (In a different version, some of the doors locked, have a key on the one side only, effectively becoming one-way passages.)
Of course, all doors leading out of the building (or to the roof) are locked. It is requested to find a path, if any, from the lower back left room to the top front right one; although, the location of the starting and target room can be varied, too.
If the passage involves more than one hundred steps, the solution is found, but not printed. Should the maze be larger than 26 rooms on each side, it cannot be displayed in a standard 80- column display: Three characters are used for each room horizontally, so that two- digit visit numbers will be clearly discernible in neighbouring rooms. The ‘X’s indicate a solid floor, in rooms not visited. (Output interfaces are not my strong point.) Some implementations will not allow an array to extend over a segment, and then the program will be halted a little before 26 rooms per side.
The choice between recursion and iteration has already been discussed in the fast fill routine section quite extensively. Basically, recursion is favoured if the nesting of processes is not too deep, and the list grows or shrinks unpredictably. The length of the array is only increased or decreased by one in each step, for backtracking, so iteration is clearly preferable.
Of course, the first data structure needed is Boolean, telling whether each passage is free or blocked, and there are six directions, in each room, from which (possibly) to proceed. Strictly speaking, it is only necessary to record the direction taken in each stage, so that the program can backtrack, if need be, and, eventually, to print out the path.
However, it is much more convenient, and faster, to store additional information, instead of scanning the path already traced: Saving the visit number for each room has the following advantages:
- The path is easily prevented from looping back on itself.
- When the program backtracks from some rooms, they are still marked, so they will not form part of future attempts- they are a lost cause.
- The solution is printed out easily.
It will be easier to backtrack if the room location is stored in each step of the program. Lastly, the rooms visited in fruitless searches are marked, so as to display the path more conveniently.
The problem can also be tackled by Lee’s algorithm, too, with advantage: The shortest path is automatically found. Also, some of the additional shortest passages, if any, may be found occasionally. Workspace memory requirements are higher, though. Lee’s algorithm will form the subject of a future section.
| The longer an error takes to spot, the sillier it will probably be. |