| | |
Suppose you are trying to accomplish a task where you must make several choices. Some collections of these choices will result in a failed task, while other collections result in an accomplished task.
If one simply searches through all possible collections of choices looking for which ones are successful (i.e., the "brute force" method), the number of possibilities one needs to examine often grows exponentially with the size of the problem!
As an example of this, consider the N-queens problem:
Place N queens on an N x N chessboard so that no two queens attack each other -- that is to say, no two queens share the same row, column, or diagonal.
In a $4 \times 4$ board, we have to choose positions for 4 identical queens from $16$ different possible squares. This can be done in $${}_{16}C_{4} = \frac{16 \cdot 15 \cdot 14 \cdot 12}{4 \cdot 3 \cdot 2 \cdot 1} = 1820 \textrm{ ways}$$
However, for an $8 \times 8$ board, we have to choose positions for $8$ identical queens from $64$ different squares, which can be done in ${}_{64}C_{8} = 4426165368 \textrm{ ways}$!
We can tighten this up quite dramatically by enforcing one queen in each row through the use of $8$ nested loops as shown below:
for (int i=0; i < 8; i++) {
for (int j=0; j < 8; j++) {
for (int k=0; k < 8; k++) {
for (int l=0; l < 8; l++) {
.
.
for (int p=0; p < 8; p++) {
//check validity of (i,j,k,l,…,p);
}
.
.
}
}
}
}
Using such nested loops, we would only have to look at $4^4=256$ configurations for a $4 \times 4$ board and $8^8$ configurations for an $8 \times 8$ board (note $8^8 = 16777216$) -- but this is still far, far too many!
We need a better way...
One such better way is through the use of a backtracking algorithm. In a backtracking algorithm, one incrementally builds candidates for the solution (or solutions in some cases) for a particular problem by making a sequence of choices (that each have a finite number of options), but abandons partial candidates (backtracks) as soon as it is determined they can not possibly lead to a valid solutions.
Specifically, we can use a stack to this end -- "building" up the candidates by pushing to the stack a sequence of choices made to form a particular candidate for the solution. If we ever see that pushing an option for the next choice to be made couldn't possibly lead to a solution with the previous choices made, we skip that one. If we run out of options for a particular choice (a sure sign that this candidate, as built so far, is not going to work) then we pop the stack and revisit our most recent choice made, opting for another option for that choice. If we ever have to pop all the way back down to our first choice, opting for another option -- but have run out of options to consider for the first choice, we know that no other solutions are possible and can stop the algorithm.
Recall that each queen must be on a different row in the N-Queens problem. Given this, we shall attempt to put queens on the board one row at a time starting with row 0.
We can use a stack to indicate the current state of queen positions. Importantly, notice that we only have to put our choice of column positions for the queens on the stack. To find the position of the queen corresponding to a given stack element, we only need to find the number of elements this element is from the bottom of the stack (this gives us the queens's row) and combine it with the value of the element in question (again, the queen's column).
Two examples of this are shown below:
* * * * | * * Q * 2 (3,2)
* Q * * 1 (2,1) | Q * * * 0 (2,0)
* * * Q 3 (1,3) | * * * Q 3 (1,3)
Q * * * 0 (0,0) | * Q * * 1 (0,1)
stack queen | stack queen
coordinates | coordinates
Starting with a queen in the first row, first column (represented by a stack containing just "$0$"), we search left to right for a valid choice for a column we can use to place another queen in the next available row.
If we find a valid choice for the column, we push this choice to the stack and start again on the next row
If we don't find a valid choice for the column in this row, then our most recent choice is a bad one. As such, we undo that choice (by popping the stack) and search for a different valid column farther down the row.
From there, we just keep doing this over and over (a process which can be implemented either iteratively, or with recursion) until we have choices for all of the rows. Of course, when we have a valid choice for each row, we have found a solution, and should react to it appropriately (e.g., print it, count it, save it, etc.). That said, there is nothing that requires there be only a single solution. Indeed, for the N-Queens problem on a standard $8 \times 8$ chessboard, there are $92$! To find the rest, every time a solution is found, we can pretend it is not a solution, and again backtrack to the previous row, and proceed as before to find the next solution, if it exists.
Ultimately, every position in the first row will be considered. When there are not more valid positions in the first row and we need to backtrack, that's our cue that there are no more solutions to be found. Thus, we may stop searching when we try to pop from the stack, but can't as it is empty.
In general the following code encapsulates the backtracking process (as implemented with recursion) for finding all solutions to a given problem -- whether that is the NQueens problem or something else.
State state;
// For solving the N-Queens problem as described above, the state will
// contain the stack of column choices. For other problems the state
// will likely contain something different.
public void searchFromCurrentState() {
if (state.isSolution()) {
reactToSolution(); // for example, you might want to print it, count it, or store it
return; // stop pursuing this path
}
for (Choice choice : state.nextChoicesToConsider()) {
if (state.isValid(choice)) {
// isValid(choice) should be false if choice is either invalid or represents a choice
// that will ultimately not yield any new solutions.
// For N-Queens, this means we will want isValid(choice) to be false if the choice places
// the next queen in the same column or diagonal as a previous queen, and true otherwise.
// Note, we don't have to worry about the rows, given how we are making our choices -- as the
// "next row" will always be different from the rows where queens have been previously placed.
// As a matter of verbiage, rejecting any further choices along a given search path
// for a solution that all start at some given state is known as "pruning" the search tree.
// Effective pruning can have a profound effect in decreasing the runtime of a given
// backtracking algorithm, and should be carefully considered.
state.makeChoice(choice);
searchFromCurrentState(); // <-- the recursive call!
state.undoChoice(choice); // however the recursion from the previous statement turned out
// (maybe you found a solution, or maybe not), now we try another path
}
}
}