Given: an NxN chessboard, each square described by a pair of coordinates (row,column) where row and column are numbers between 1 and N. A queen in chess can take a piece that is on the same row, column or diagonal. N queens can safely be placed on the board if no pair of queens occupies the same row, column or diagonal.
Write a program to determine the positions in which N queens may be placed on the board.
The input to the program is the number N. The output is a list of N positions. Each queen can be designated by a row number from 1 to N, since they must each be on different rows.
The following pseudocode describes an algorithm you may use. Assume that each queen is placed in a different column, starting with column=1
Initialize: push position row=1 (queen 1), column=1 on the stack
// the stack holds positions of choices taken
success = false;
while (!success && !stack.empty())
{
Check if current position on stack top is same row, column or diagonal as any previous choice (everything else on the stack). If so, there is a CONFLICT
if( CONFLICT)
Pop stack until either it is empty or the column of stack.top() is other than N. If !stack.empty(), increase the column number of stack_top() by 1.
else if( !CONFLICT && stack.size()==N ) success = TRUE;
else
push position row = stack.size()+1 and column = 1 on the stack. (that is, try to place the next queen).
}
(Algorithm from Main & Savitch, 'Data Structures and Other Objects Using C++', Addison Wesley 2001.
As always, estimate the order of the algorithm you implement in terms of N.