| | |
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 positions of the queens. Importantly, notice that we only have to put our choice of column positions for the queens on the stack. We can determine each queen's coordinates given only the stack. We simply combine the position of an element in the stack (the row) with the value of that element (the column) for each queen. 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 position to place another queen in the next available row.
If we find a valid position in this row, we push this position (i.e., the column number) to the stack and start again on the next row
If we don't find a valid position in this row, we backtrack to the previous row -- that is to say, we pop the column choice for the previous row from the stack and search for a valid position further down the row
Note, when the stack size gets to $n$, we will have placed $n$ queens on the board, and therefore have a solution.
Of course, there is nothing that requires there be only one solution. To find the rest, every time a solution is found, we can pretend it is not a solution, backtrack to the previous row, and proceed to find the next solution.
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 (it also counts solutions found) -- whether it is being used to solve the NQueens problem or others (note, the code below also counts the solutions -- which may or may not be desired for the context at hand):
stackOfChoicesMade = new StackOfChoices(); // (or minimally, have this StackOfChoices accessible and empty)
int numSolutionsFound = 0;
Choice choice = Choice.firstChoice();
while (true) {
if (stackOfChoicesMade.mightHaveSolutionWith(choice)) {
stackOfChoicesMade.push(choice);
choice = Choice.firstChoice();
}
else if (choice.unconsideredChoicesExist()) {
choice = choice.nextChoice();
}
else {
if (stackOfChoicesMade.isEmpty()) // In the following step, you intend to pop to backtrack, but
break; // if you can't (because the stack is empty), you are done!
choice = stackOfChoicesMade.pop().nextChoice(); // If the pop is safe, pick up where you
// left off with your last choice.
// (i.e., choose the next choice after that one)
}
if (solutionFound()) {
reactToSolutionFound();
numSolutionsFound++;
choice = stackOfChoicesMade.pop(); // normally we check to make sure -- but it's safe to pop.. why?
choice = choice.nextChoice(); // keep going to try to find other solutions
}
}
Note: If you actually want to implement the above algorithm, having a method that checks to see if a position is valid given the queens placed so far might be a really good idea. This of course means you will have to check the position against all previous queen positions in previous rows (all of which can be determined from the stack)