If you have an nxn chessboard, is it possible to lay out n queens on the board so that no queens can be attacked by another queen? (That means that no two queens can be in the same row, column or diagonal.)
You are to write a function with an integer parameter n to determine whether or not there is a solution to the problem, and to print the solution if there is one. (There may be solutions for chessboards of a certain size, and no solution for chessboards of a different size.)
Your function should make (and print out) a sequence of choices such as, "Put a queen in row 1, column 1." Each time a choice is made, you will have to check whether it conflicts with any previous choices. The choices are to be stored on a stack. If the current choice does not conflict with any of the previous choices, then the current choice should be pushed onto the stack.
The following is a pseudo-code description of the algorithm: I revised the pseudo code!
Make the first choice to put a queen in row 1, column 1.
This is now the current choice.
finished = false
// DO NOT Push this first choice on the stack.
while (not finished) { // note change!
Check whether the current choice conflicts with the previous choices.
if (there is a conflict){
if the column of the current choice is < n,
increment the column of the current choice.
else { //can't increment column of current choice
Pop the top choice off the stack.
If the column position of the popped choice is < n,
increase the column position of that choice by one
and make it the current choice.
If the column position is already n,
keep popping until either the stack is empty or you were able
to change the column postion of a previous choice.
If the stack becomes empty and you can't find any
positions to change, set finished to true (there is no solution)
}
else { // no conflict
if row of current choice is n,
we are done and we have a solution. Set finish to true.
else {
push current choice onto the stack.
row number of next choice will be the row number of
the choice that was just pushed plus 1.
column number of the next choice will be 1.
These new values are now the current choice.
}
}
}
Note that when you need to check for conflict with previous positions, you
will have to search through the entire stack, not just check the top element.
Remember that you do not have access to the data in the entire stack...
the only way to search through what is in the stack under the top is to
temporarily remove data from the stack, look at the data, and then replace
it on the stack (in the correct order!)
Here is a sketch of how you can search for a conflict: This is not guaranteed to be correct - it's just an outline to help you organize your thoughts!
Suppose the stack is called s.
problem = false;
while (!problem && !s.isempty()){
Pop top position off stack.
Push that value on a temp stack.
If top position conflicts with current position
(same column or on diagonal, problem=true)
}
while (temp stack is not empty){
Pop temp stack
Push back onto s
}
return the value of problem - problem=true means
you found a conflict.