• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Queens domination

 
Greenhorn
Posts: 2
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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!"
 
Ranch Hand
Posts: 1609
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Greenhorn
Posts: 2
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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!!!
 
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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.
 
Don't get me started about those stupid light bulbs.
reply
    Bookmark Topic Watch Topic
  • New Topic