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.