Program solves the n-queens problem

Reference no: EM13763108

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

Reference no: EM13763108

Questions Cloud

The heat-treat atmosphere : List potential issues, difficulties, or limitations with your solution.

Write an analytical essay on short fiction : Write an Analytical Essay on Short Fiction.

Reaction to the terms capitalism and socialism : What is your emotional reaction to the terms capitalism and socialism? Explain why you feel the way you do.

Write a working definition of term at-risk in your own words : Write a working definition of the term at-risk in your own words. Review the Week One Instructor Guidance for what constitutes a working definition.

Program solves the n-queens problem : 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.

Common pattern or stages involved in corporate violence : Identify and discuss the most common pattern or stages involved in corporate violence.

Subtraction from the book balance : Classify the following items as (a) an addition to the bank balance, (b) a subtraction from the bank balance, (c) an addition to the book balance, or (d) a subtraction from the book balance:

Create a new animal that flys with a jetpack : Create a new animal that flys with a jetpack. This will require a new fly behavior and a new class. This new animal eats kale.

Return on stockholders equity : What is its return on stockholders' equity?

User Account

All Pages