Will Sobczak wrote:I have the main, and the ArrayStack class, but now I just need the QueenCover class, and I have no idea how to do this!!!

Then forget

Java and concentrate on

*the problem*.

My suggestion would be to turn off your computer and get out a chess set or, failing that, a pencil and paper, and do it yourself. That should give you solutions for eveything up to n=8, and you may find a

pattern.

You also know some things about the problem already:

1. Any board where n < 4 can be covered with one queen.

2. Any board where n >= 4 can be covered with with M=n-1 queens, by putting a Queen on every square of a diagonal except one corner.

So the challenge is to find a solution that is

*better* than M=n-1 (or to prove that it can't be done).

I've never tried the problem before, but I think I'd probably use a heuristic approach, perhaps:

1. For each square on an empty board, calculate the number of squares threatened by a queen placed in that position.

2. Place a queen in the square that threatens

*most* other squares (or one of them, if there's more than one possibility).

3. Repeat Steps 1 and two, but don't include any squares that have already been threatened or are already occupied, and don't allow any square that is already occupied to be used again.

4. Keep going until the total number of squares threatened or occupied == n * n.

Just one way; and I suspect that the real problem will then be proving that the resulting solution is

*optimal*.

Winston

Edit: In addition, any board n >= 4

*where n is odd* can be covered with with M=n-2 queens, by putting a Queen on every square of its diagonal except

*either* corner, since the centre square covers both long diagonals.