Could you do my lab

CS 345, Spring 2015 page 1 Lab 2

CS 345: Spring 2015 Lab 2 Due 5/27/2015

For this lab, 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. For example, the 4-Queens problem that was demonstrated in class

had a solution that looked like the following.

Q

Q

Q

Q

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.

To Turn In

Turn in a copy of your source code by e-mail in an archive file named XXXL2.zip, where XXX

represents your initials. This file can be either a zip file or a jar file. Be sure that your program

files contain a header with your name on it and the name of your archive file. In addition, you

need to turn in a hard copy of the program.

This lab is worth 40 points.

5 points: The archive file contains only source files, is emailed on time, and your name is in

a comment in the header.

5 points: A hard copy of your source files is handed in, and the name of the archive file is

contained in a comment in the header.

5 points: The source files have appropriate documentation (comments) and use a consistent

and readable programming style.

5 points: The source files compile and run under JDK 1.5 or higher.

Rank 3

2

1

0

CS 345, Spring 2015 page 2 Lab 2

5 points: The program has usable interface. It can be a GUI or non GUI interface.

10 points: The program correctly prints the placements of the queens using a backtracking

algorithm.

5 points: The program correctly identifies when a solution is not possible.

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