How would you look for a path through the labyrinth?
The idea described here is probably already known to you: you leave a trail behind (crumbs, stones, thread ends ...) and progress as far as you can. When you reach a place from which you can not go further progress, you go backward with a trail to the nearest place from which you can go to an unexplored and continue along that path. Do this like this until you find the exit, or until you investigate every path (which would mean that the output does not exist).
This is basically a depth-first search - DFS.
Search is called depth-first, because at first you are progressing, you go deeper into the labyrinth as far as you can, and
you come back only if you can not go deeper. Apart from searching in depth, we could, for example, first, to mark all the places we can reach in one step, then the one we can reach to arrive in two steps and so on. This search is called breadth first search - BFS), about it will be said in one of my future posts.
Let us discuss one more question about the described DFS algorithm: whether the trace return should be remove or leave this trace? If we remove the trace, it might happen that we visit the same fields many times from different directions. If we were to leave the trail and after the return, it would be more complicated show the path from the starting point to the current position and is different from the labyrinth parts we went and returned to them. As both decisions have good and bad sides, in general, it is best to use two types of trace, one when we are progressing, and the other when we are returning. So we always have a clear mark the path from the starting point to the current position (which in the case of the exit to the exit becomes the solution), and also a guarantee that we will visit every labyrinth field at most once.
Let the labyrinth be represented by a matrix a. The Seek function that we are looking for through the labyrinth has it coordinates of the current field as arguments. We assume that the labyrinth itself and its dimensions are rowCnt and colCnt available function. The function returns a value that indicates whether the path was found. Algorithm of searching the path could be written like this:
Seek(i, j)
if (i < 1) or (j < 1) or (i > rowCnt) or (j > colCnt)
return false;
if (a[i][j] = kExit)
PrintMatrix();
return true;
if (a[i][j] != kPass)
return false;
a[i][j] = kSearching;
bool found = Seek(i-1, j) or Seek(i, j-1) or Seek(i+1, j) or Seek(i, j+1);
a[i][j] = kSearched;
return found;
Worst case scenario is O(n). In recursive implementation, which is simpler, this memory is used implicitly for a recursive call stack. In non-recursive implementation would be necessary to remember a number of fields that were visited, and through which search still lasts (fields marked with the kSearching value in the recursive algorithm above).
The described search for a path in the maze is just one, perhaps the best known example of an algorithm search in depth. However, depth searching can be used whenever a sequence of strokes is needed from the starting position (positions, states) to the final or one of the final ones. Examples of such tasks are Lloyd's puzzle of 15 numbers and the problem of eight queens.
In the case of Lloyd's puzzle, the starting position is selected in a random way, the final position is the one on which the numbers are sorted by size (as shown in the picture), and the move is performed as follows the empty field replaces the place with one adjacent to it field. Unfortunately, the number of positions in this problem (the game) is so large that a complete search for the space of all positions can take a very long time. That we do not have to pass the whole thing
search space, it is desirable in some intelligent way to choose next move. There is a series of enhancements to depth searching and this puzzle is a great example of how the search can be speed up by pointing and limiting.
The problem of the eight queens consists in the following: it is necessary to set eight queens on the chessboard so that they do not attack each other, that is, no two queens are in the same order, the same column or on the same diagonal of the board. Starting position is an empty board, the move is to add a queens on the board respecting non-aggression restrictions, and the final position is any position with eight queens at tabs, so queens do not attack. In order to simplify the search, we notice that these eight queens, they must be in different columns of the board. That's why we can always add the queen to the i-th column. Adding is done by trying each column field in a row and checking whether the queen with that one fields are being attacked by some of the queen who has been set up earlier. If we attack, we are returning and trying the next field, and if it does not attack, we continue the search by moving to the next queen and the next column. When we succeed we are eight steps in depth, then there are eight queens on the board and we have come up with one solution which we are showing. The search stops after the first solution is found, but the algorithm is very easy
edit that after a solution is found, it continues to search for the remaining solutions.
In the subsequent algorithm, the set of poses contains the positions of the queen by the column, the loop by and tries all the position of the queen at the current depth (in the current column), and the loop by j checks if the newly-installed queen attacks with some of the pre-set queens.
Search(depth)
if (depth == 8)
OutputSolution;
return true;
++depth;
Lojdova slagalica (15 puzzle)
for i = 1 to 8
pos[depth] = i;
valid = true;
for j = 1 to depth-1
if (pos[j] == pos[depth] or
j + pos[j] == depth + pos[depth] or
j - pos[j] == depth - pos[depth])
valid = false;
if (valid && Search(depth))
return true;
return false;
Interestingly, before the emergence of computers, genius and resistance to the size of Gauss(one of the the greatest mathematicians of all time) were needed to fully solve this problem (find all 92 solutions). Today, this, as we see, is an ordinary school task to which the solution can come to anyone who can programming.
Sources:
I'm studying computer science. The lectures of my professors and the literature that we used at the courses helped me to write this post.