Queens domination

[Will Sobczak]

Using stacks, we have to make a program that makes us put in an NxN board, then it will return the minimum number of queens needed to be able to threaten every single square on said NxN board. I'm pretty sure he doesn't want us to use discrete mathematics, so I simply can't use permutation to find the solution. The only trouble I'm having with this is that I have no idea how to even start it. What would be a good algorithm to do this? I imagine that back-tracking would suffice, because we are not allowed to use recursion.

This is not a class assignment, and the teacher threw it at us and it is purely optional. I think it would make a good base for future programs if I run into the same type of problem, or something similar, in the future. Something I can look back on and be like "Oh! That could work!"

[Akhilesh Trivedi]

Will Sobczak wrote: I imagine that back-tracking would suffice, because we are not allowed to use recursion.

Isn't back-tracking recursive? I don't know but you make me think.

[Will Sobczak]

Akhilesh Trivedi wrote:

Will Sobczak wrote: I imagine that back-tracking would suffice, because we are not allowed to use recursion.

Isn't back-tracking recursive? I don't know but you make me think.

See, I thought so too, but the teacher said it wasn't. I don't know exactly what he meant, but any method will do, and I'll try to spruce it up best I can. I just need to get started on it. I have no idea how to work it.
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!!!

[Winston Gutkowski]

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.