you will write a program that solves the N-Queens problem by the backtracking method. The pseudocode for the solution is on the last page. Your program should run in standard Java, either as an application or an applet. It should be able to take for input a number for N. We will keep the value for N less than 30 because of the length of time it takes for larger sizes. For the output, it only needs to print the rank (row) that each queen is on. These numbers will be between 0 and N-1.
In this solution, Queen 0 is on rank 1, Queen 1 in on rank 3, Queen 2 is on rank 0, and Queen 3 is on rank 2. My program prints the following for the solution to a 4-Queens problem
Placement of 4 Queens
1, 3, 0, 2
Now, if you have lots of time on your hands and you like a challenge, you can have your program draw an N by N board with the appropriate placement of the N Queens. Otherwise, just listing the ranks of the queens starting with Queen 0 and ending with Queen N-1 is sufficient. You
should be aware, however, that some values of N do not have solutions, and your program should print that no solution is possible in these cases.
Pseudocode for N-Queens problem.
Assume the positions of the queens are represented by an n-tuple (Q0, ..., Qn-1) where 0 <= Qi < N
for each i.
We use a boolean function validPosition defined as follows
boolean validPosition( k )
for i = 0 to k - 1 do
//If two queens are on the same row or same diagonal
if ( Qi = Qk ) OR ( abs( Qi - Qk ) = abs( i - k ) )
return false
return true
placeQueens( N )
Q0 = 0
k = 0 //Start with Q0 on row 0
while ( k < N ) do
while( ( k < N ) AND ( validPosition( k ) is false ) ) do
Qk = Qk + 1 //Advance this queen one row
if( ( k = N - 1 ) AND ( Qk < N ) ) //All queens are validly placed
print solution ( Q0, .. , QN-1 )
STOP
else if ( ( k < N - 1 ) AND ( Qk < N ) )
k = k + 1 // Not done yet; Now try to place the next queen
Qk = 0
else
//The positions of the first k queens cannot possible lead
//to a solution. So, we must backtrack.
k = k - 1
if( k < 0 )
//Opps, we have not found any position for the first queen
//that could lead to a solution. Guess it can't be done!
print "no solution possible"
STOP
else
Qk = Qk + 1 //Advance this queen (the one we backtracked to)
//one more space