As we shall see later in the compiler course, backtracking algorithms may be needed for some applications of compiler development. These are algorithms that determine a solution to a problem by proceeding cautiously towards the desired result, making brave guesses as to what to do next, but being prepared to back track to try other possibilities when and if it becomes clear that no further progress is being made.
One of the classic problems to which this technique can be applied was, apparently, first investigated by the famous mathematician C.F. Gauss in about 1850. The physicists and applied mathematicians among you should recognize his name; it is attached to all sorts of theorems and techniques.
The problem is this. Given a chess board, and a large supply of queens, is it possible to arrange the queens on the board so that there are many queens as rows (or columns), and yet so that no queen threatened (or is threatened by) any other queen. Queens in chess are powerful pieces - they can attack horizontally, vertically and diagonally in either direction. Perhaps surprisingly, it is possible to do this, as the diagrams below show. But how would you solve the problem systematically? How would you find all the possible solutions (assuming for the moment that there is more than one solution to be found)? Can you develop computer algorithms for these and similar problems?
1 2 3 4 5 6 7 8 1 2 3 4 5 1 2 3 4
╔═══╤═══╤═══╤═══╤═══╤═══╤═══╤═══╗ ╔═══╤═══╤═══╤═══╤═══╗ ╔═══╤═══╤═══╤═══╗
1 ║ Q │ │ │ │ │ │ │ ║ ║ Q │ │ │ │ ║ ║ │ │ Q │ ║
╟───┼───┼───┼───┼───┼───┼───┼───╢ ╟───┼───┼───┼───┼───╢ ╟───┼───┼───┼───╢
2 ║ │ │ │ │ │ │ Q │ ║ ║ │ │ │ Q │ ║ ║ Q │ │ │ ║
╟───┼───┼───┼───┼───┼───┼───┼───╢ ╟───┼───┼───┼───┼───╢ ╟───┼───┼───┼───╢
3 ║ │ │ │ │ Q │ │ │ ║ ║ │ Q │ │ │ ║ ║ │ │ │ Q ║
╟───┼───┼───┼───┼───┼───┼───┼───╢ ╟───┼───┼───┼───┼───╢ ╟───┼───┼───┼───╢
4 ║ │ │ │ │ │ │ │ Q ║ ║ │ │ │ │ Q ║ ║ │ Q │ │ ║
╟───┼───┼───┼───┼───┼───┼───┼───╢ ╟───┼───┼───┼───┼───╢ ╚═══╧═══╧═══╧═══╝
5 ║ │ Q │ │ │ │ │ │ ║ ║ │ │ Q │ │ ║
╟───┼───┼───┼───┼───┼───┼───┼───╢ ╚═══╧═══╧═══╧═══╧═══╝
6 ║ │ │ │ Q │ │ │ │ ║
╟───┼───┼───┼───┼───┼───┼───┼───╢
7 ║ │ │ │ │ │ Q │ │ ║
╟───┼───┼───┼───┼───┼───┼───┼───╢
8 ║ │ │ Q │ │ │ │ │ ║
╚═══╧═══╧═══╧═══╧═══╧═══╧═══╧═══╝