# Queens domination

Will Sobczak

Greenhorn

Posts: 2

posted 4 years ago

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!"

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

Ranch Hand

Posts: 1599

posted 4 years ago

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

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.

Keep Smiling Always — My life is smoother when running silent. -paul

[FAQs] [Certification Guides] [The Linux Documentation Project]

Will Sobczak

Greenhorn

Posts: 2

posted 4 years ago

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!!!

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!!!

posted 4 years ago

Then forget Java and concentrate on

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

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

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

Winston

Edit: In addition, any board n >= 4

- 1

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.

"Leadership is nature's way of removing morons from the productive flow" - Dogbert

Articles by Winston can be found here