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.