CSC 171 LAB #7
FALL 2001
GOAL:
1.
Become
familiar with arrays
2.
Become
familiar with the use of recursion
3.
Learn
a little about graphics functions.
4.
Identify
yourself as an elitist intellectual with your knowledge of a classic, but
entirely pointless, chess puzzle – certain to impress your friends at parties.
TASKS:
·
Implement
an Applet that solves the famous “8-queens” chess puzzle problem.
BACKGROUND:
A puzzler that has continued to
fascinate chess buffs for generations is the Eight Queens problem. Simply
stated: Is it possible to place eight queens on an empty chessboard so that no
queen is “attacking” any other, i.e. no two queens are in the same row, in the
same column, or along the same diagonal? As you recall from your kindergarten
chess club – a chess/checker board can be conceptualized as a square
tessellated into 64 equal-sized regular quadragons (as depicted below). When a
queen is placed on the square, the queen “attacks” all squares on the same rank
(row), all squares on the same file (column), and all diagonal squares. So in
the diagram below, the queen attacks as squares labeled “1”, while all squares
labeled “0” are considered to be “free”.
|
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
|
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
|
1 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
|
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
|
1 |
1 |
Q |
1 |
1 |
1 |
1 |
1 |
|
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
|
1 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
|
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
So,
the trick is to come up with an algorithm that places 8 queens on the board so
that no queen attacks any other queen. You might want to try doing this “by
hand” for fun, but it’s even more fun to program a computer to find the
solution. The solution is cool because it can be used to illustrate arrays,
recursion, and graphics – besides being able to impress your friends.
STEPS:
1.
You
can use swing or the vanilla awt – your choice.
2.
This
lab walks you through a step by step design of the program solution. However,
you should first use a paper and pencil and some discussion time (10-15 min)
with a friend and think of how you would design the solution-finder. You need
not implement your solution, but going through the design exercise first will
give you an appreciation for the solution you implement. It allows you to
develop your own problem solving skills. Don’t blow this off – you will get an
enormously larger benefit from this lab if you try to tackle it yourself, first.
So, before you go on talk to another person and try to sketch a solution. Try
to picture what your code would look like – what data elements do you need? How
will you represent the different states of the solution? Try to analyse your
own methodology when you solved the problem “by hand”. What methods do you need
to implement this solution in your program?
3.
This
lab presents only one solution to the problem – you are required to implemnt
this solution. However, if you feel that you have an alternate solution you may
implement it for extra-credit. It will count as an extra lab, but it has to be
a different algorithm.
4.
So,
on to the solution. You need to write an applet. It makes sense to set up the
board in the init() method, then call the solution method at the end of the
init method and display the solution in the paint() method.
5.
It’s
fairly obvious that you can use a two dimensional array to represent the board.
We need to be able to place queens on the board and remove queens from the
board. We also need to keep track of which squares are under attack. One way to
do this is with the following representational scheme. An 8x8 array of integers
can represent the board. A “0” value indicates a “free” square. A “-1”
indicates a square with a queen on it. A positive integer > 0 indicates how
many queens are currently attacking the square. Declare the array as an
instance variable, allocate it in the init() method.
6.
Graphics
– you need to display the array on the applet in a 2D arrangement. Most
graphics systems use the upper-left corner as the origin. X values increase as
you move to the right. Y values increase as you move “down” on the screen.
1.
It’s
fairly easy to step through a 2D array using two nested “for” loops
2.
To
write on an applet graphics area, we typically use the ‘drawString” method,
which takes 3 parameters: a String, an integer x location, and an integer y
location. Example g.drawstring(“hello”,200,150) will write the string “hello”
on the applet graphics area at location (200,150). [Note “g” is the Graphics
object passed to the paint method by the system. “public void paint(Graphics
g) { . . . }
3.
When
writing to the screen, we use pixel coordinates. It’s visually pleasing to
start the board at some space over and down in order to space to the data away
from the applet edge. (the “offset”)
4.
We
need to space the location of the Strings (the “increment”)
5.
So,
if we are using nested for loops, controlled by integers i and j, it is typical
to use an instruction inside the loops like : g.drawstring(Integer.toString(board[i][j]),(x_offset
+ (i * x_increment)),(y_offset + (j * y_increment));
6.
Write
your paint method to display the contents of your board in this manner. Note,
you want to use the conditional operator (?:) – see page 156 of D&D to
write a “Q” instead of an “-1”. This will enable you to use a display like the
one above.
7.
We
could just solve the problem with one big method, but sometimes it helps to
break the solution up into it’s component parts. First, write a method that
places a queen on the board. Naturally, this method should take an x & y
location. It should check to make sure the location is un-attacked (i.e. equal
to zero). It should put a “-1” in the location, indicating the queen in that
location. It should then increment all the squares attacked by that location by
+1. Compile and test this routine by placing some queens on the board via calls
to your method in the init() method.
8.
Now,
write the method that removes queens – it should look just like the place queen
message, except that it decrements the attacked squares and sets the selected
location to “empty”. Test your method by placing and removing a few queens.
9.
When
you have “placequeen(x,y)” and “removequeen(x,y)” tested the solution itself
becomes a good deal easier.
10.
There
is a fairly straightforward recursive solution to the 8-queens based on the
observation that one and only one queen must be placed in each row. This
suggests that the solution method be called with the parameter of the column to
place a queen into. This method should return true if a solution is found –
false if a solution is not found. We call solution(0) from the init() method
and the recursion handles the rest.
11.
The pseudocode for the recursion
1.
Loop
down the current column -
1.
if
you find an empty square
a.
place
a queen in the square
b.
If
the current column is the last column, then you have found a solution – so,
return “true”.
c.
Call
the recursive solution for the next column
i.
If
the solver returns “false” then remove the queen you just placed in (a) – else
return true (a solution was found)
2.
If
the loop finishes without ever returning (no solution found) return “false”
12.
Code
and test the recursive solution. Check your results “by hand”.
1.
Ask
yourself the question “How would this look if I used iteration instead of
recursion?”
13.
You
can experiment with variants on your solution by placing a queen at an
arbitrary spot in the first row and then invoking solution(1). Some interesting
questions to ask is “how many possible solutions are there?” and “how many
unique solutions are there?”, and “how many unique solutions are there if you
do not count solutions that are board rotations of each other?”.
14.
You
are technically done with the solution aspect of the lab, but in a flash of
honesty, you might admit that the graphics look pretty lame. It turns out that
you can draw rectangle on the graphics object with the
g.fillRect(x,y,width,height) method. You can set the drawing color with the
g.setColor(new Color(R,G,B)); method – where R,G,and B are ints between 0 and
255 representing the amount of red, green, and blue. Use this information to
modify your paint method so as to draw a checkerboard on the applet and write
your solution onto the board. It’s not the highest tech graphics, but it’s a
start.
15.
In
the end, your applet should look something like this: The Eight Queens solution applet
16.
If
you want to code a variant solution – iterative or with a radically different
data representation – you may do so in addition to, not instead of this
lab - for an extra-credit lab. Your extra credit lab must contain a one
page write up explaining how your approach differs from the one in this lab. No
extra time will be given for the extra credit lab.
17.
When
you get the paper ready call your lab TA over and demo the program for her/him.
Give the paper to your TA. This completes the hand in process. The deadline is
one week – no late assignments accepted.
18.
The
demo must run from your troi account – not the local machine.