A backtracking algorithm can be derived by modifying the general tree preorder traversal algorithm. The "p not null" test in the loop body of the preorder traversal algorithm must be replaced by two tests. One to see if p points to an existing node and another "p feasible" test to prune the tree. How this feasibility test is implemented is what determines the amount of pruning that occurs and hence the efficiency of the solution. The process routine called in the loop body must determine if node.p is terminal, and, if so, print the solution. If these were the only changes made, then nothing at all would be printed when no solution exists.
You, as the programmer, do not know whether a solution exists for every n. Therefore, initialize a flag, found, to false, and have process set found to true if it finds a solution. Upon exiting from the loop body, test found, and if it is false print "No solution." The resultant algorithm for a backtracking preorder traversal is as follows:
Backtracking Preorder Tree Traversal
1. Set p to the root of t.
2. Set found to false.
3. Set the stack to empty.
4. While p is not null or the stack is not empty,
if p is not null, then
if p is feasible, then
process(p),
push all successors of node.p onto the stack except next(p),
move down in t by setting p to next(p),
else
backtrack in t by popping the stack and setting p to the popped value,
else
backtrack in t by popping the stack and setting p to the popped value;
if not found then
print no solutions.
The function next(p) is assumed to return a null value if node.p has no successors. If only one solution is to be found and printed, only the test of the while loop must be changed. It should become "(p not null or stack not empty) and (not found)." The process algorithm to be used with the backtracking preorder traversal is as follows:
If node.p is a terminal node, then
1. Print the solution, and
2. Set found to true.
The algorithms developed in this section are quite general. They are applicable to any problem that can be reduced to a backtracking traversal (like the n-queens problem). They should be viewed as general tools for problem solving. We must now specialize them to the n-queens problem so that they are detailed enough to implement as a function. Data structure decisions, specifically the implementation of the current board configuration, must be made along the way.
The tree is not actually stored in memory; it was used as a conceptual aid in formulating the problem abstractly. As a result, the problem has been recognized as one that may be solved by a general tree backtracking procedure. It is not necessary to refer to the tree at all, but we have done so here to place the problem in this more general context, and we continue with this approach.
Suppose p points to a node at depth k. The depth of the node specifies the placement for the kth queen, column k. P itself determines the choice of row. In this way p corresponds to a particular row and col pair and vice versa. A nonnull value for p corresponds to a column and row value <n + 1. Initializing p to the first successor of the root corresponds to setting row to 1 and col to 1.
Next must have row and col as parameters; it simply increases col by 1 and sets row to 1. As the traversal proceeds, row and col vary in a regular way. This can be used to advantage. Instead of pushing all successors of node.p onto the stack, which would involve n - 1 entries, simply push the current value of row. Then the backtracking task can be carried out by adding 1 to the current value of row when this value is less than n. If it equals n, the stack must be popped, row set to the popped value plus 1, and col set to col-1.
To implement the crucial test, "p feasible," we use a function feasible to return the value true when p is feasible and false otherwise. Feasible must have row and col as parameters and must have access to information about the current board configuration. It must determine if placing a queen in the position specified by row and col will allow it to "take" one of the currently placed queens. If a queen may be taken, it must return "false," otherwise "true."
We could use an n ?/FONT> n two-dimensional array board to keep track of the current board configuration. If we did this, feasible would have to traverse through the row, column, and diagonals specified by row and col in order to determine what value to return. This checking must involve all entries in many rows and columns. Since feasible is invoked in the loop body of the backtracking preorder traversal algorithm, it is executed once for every node of the tree that is accessed. Operations that appear in loop bodies should be done efficiently since they have a significant effect on the overall efficiency of the implementation.
To do its job, feasible must know whether or not the row, col, and the diagonals specified by row and col are occupied. If this information can be efficiently extracted and made available, feasible will be more efficient. We now see exactly what information is required and proceed to the details involved in efficiently extracting it.
Consider Figure 7.16. Notice that entries [j, k], [j + 1, k - 1], and [j - 1, k +1] all lie along the d1 diagonal. Notice also that j+ k = (j+ 1) + (k - 1) = (j- 1) + (k + 1). This means that all entries on the diagonal d1, determined by j and k, have the same row + col sum: j + k. The same is true of differences along d2. That is, all entries on the diagonal d2, determined by j and k, have the same row minus col difference: j - k. Suppose we keep information about the current board configuration as follows:
r[j]
Is true if the current board configuration has no queen in the jth row, and is false otherwise.
d1[j + k]
Is true if the current board configuration has no queen along the diagonal d1 with row + col sum j + k, and false otherwise.
d2[j - k]
Is true if the current board configuration has no queen along the diagonal d2 with row - col sum j - k, and false otherwise.
Feasible can now simply return the value of (r[j] and d1 [j + k] and d2[j - k]). The arrays r, d1, and d2 require storage for n, 2(n - 1), and 2(n - 1) entries, respectively, and must be properly initialized, but feasible now takes constant time to execute. Also, when row and col are changed, these changes must be reflected in r, d1, and d2. What we have done amounts to finding a way to store the current board configuration so that the operations performed on it by the algorithm are done efficiently. R, d1, and d2 have indices that range from 1 to n, 2 to 2n, and -(n - 1) to (n - 1), respectively. Since C does not allow such array indices, it is necessary to refer in the program below to corresponding entries in arrays whose indices will range from 0 to n - 1, 0 to 2(n - 1), and 0 to 2(n - 1), respectively.
Finally, we must implement the printing of a solution in process . This can be done by printing the sequence of values stored on the stack. They specify the rows in which queens 1 to n were placed. To do this we will need a stack operation item. It returns a copy of the ith stack entry, which represents the row in which the (i+1)th placed queen (the queen in column i) appears. When i is zero, it returns a copy of the top entry.
The backtracking traversal algorithm that was developed and applied to this problem is a general tool for problem solving. It may be adapted, for example, to solving a maze, finding good game-playing strategies, and translating high-level language programs.
The nonrecursive solution may be written as follows.
Nonrecursive n-queens Program
You may be tempted to try a more analytic approach to this problem so as to eliminate the need for all this searching. Be forewarned that famous mathematicians also attempted to analyze this problem but had difficulty solving it other than by backtracking! Actually, there are no solutions for n = 1, 2, and 3, and at least one solution for all n?/FONT>4. For the curious, the number of solutions for n up to 15 are:
# include <stdio.h>
main()
/* Reads in n and prints all solutions
to the n-queens problem.
*/
{int n;
printf("\n n = ?");scanf("%d",&n);queens(n);
}
#define NLIMIT 20
typedef int rowcheck[NLIMIT];
typedef int diagonalcheck1[2*NLIMIT-1];
typedef int diagonalcheck2[2*NLIMIT-1];
#define SLIMIT 20
typedef int whatever;
typedef struct
{whatever stackarray[SLIMIT?];
int top;
}stack;
setstack(ps)
/* Sets stack s to empty. */
stack *ps;
{(*ps).top = ?;
}
empty(ps)
/* Returns true only if stack s is empty. */
stack *ps;
{return((*ps).top == -1);
}
push(value,ps)
/* Inserts contents of value as
the top entry on stack s.
/*
whatever value;
stack *ps;
{if((*ps).top == (SLIMIT-1))
overflow(ps);
else
{(*ps).top = (*ps).top + 1;
(*ps).stackarray[(*ps).top] = value;
}
}
pop(ps,pvalue)
/* Removes the top entry of stack s
and copies its contents into value.
*/
stack *ps;
whatever *pvalue;
{if(empty(ps))
underflow(ps);
else
{*pvalue = (*ps).stackarray[(*ps).top];
(*ps).top = (*ps).top - 1;
}
}
whatever item(i,ps)
/* Returns a copy of the ith
entry in stack s. When i is
zero it returns a copy of
the top entry.
*/
stack *ps;
{return((*ps).stackarray[(*ps).top-i]);
}
overflow(ps)
/* Prints a message if the stack overflows. */
stack *ps;
{printf("\n stack overflow ");}
underflow(ps)
/* Prints a message if the stack underflows. */
stack *ps;
{printf("\n stack underflow ");}
queens(n)
1 a backtracking preorder traversal
/* Prints all solutions to the n-queens problem */
int n;
{stack s;
#define TRUE 1
#define FALSE 0
int i,row,col,found;
rowcheck r;
3 r, d1, and d2 will contain the board configuration
diagonalcheck1 d1;
diagonalcheck2 d2;
col = 1;
2 col and row determine the next placement attempt
row = 1;
for(i=0;i<=n-1;i++)
r[i] = TRUE;
for(i=0;i<=2*n-2;i++)
d1[i] = TRUE;
for(i=0;i<=2*n-2;i++)
d2[i] = TRUE;
found = FALSE;
setstack(&s);
while(((col < n+1)&&(row < n+1)) || !empty(&s))
if((col < n+1)&&(row < n+1))
if(feasible(row,col,r,d1,d2,n))
{process(row,col,&found,&s,n);
push(row,&s);
r[row-1] = FALSE;
d1[row+col-2] = FALSE;
d2[row-col+n-1] = FALSE;
col = col + 1;
row = 1;
}
else
row = row + 1;
else
{pop(&s,&row);
col = col - 1;
r[row-1] = TRUE
d1[row+col-2] = TRUE;
d2[row-col+n-1] = TRUE;
row = row + 1;
}
if(!found)
printf("\n NO SOLUTIONS");}
feasible(row,col,r,d1,d2,n)
/* Returns true only if the placement of the
next queen in position col,row does not
allow any queen to take another under
the current board configuration given
by r,d1,d2.
*/
int row,col, n;
rowcheck r;
diagonalcheck1 d1;
diagonalcheck2 d2;
{return(r[row-1]&&d1[row+col-2]&&d2[row-col+n-1]);
}
process(row,col,pfound,ps,n)
/* If the partial solution is a complete
solution then it is printed and
found is set to true.
*/
int row,col,*pfound,n;
stack *ps;
{int i;
whatever item();
if(col == n)
{for(i=n-1;i>=1;i--)
printf("\n COL %d ROW is %d----",n-1,item(i-1,ps));
printf("\n COL %d ROW is %d----\n",n,row);
*pfound = TRUE;
}
}
N 4 5 6 7 8 9 10
Solutions 2 10 4 40 92 352 724
N 11 12 13 14 15
Solutions 2,680 14,200 73,712 365,596 2,279,184