Originally posted by Jason Robers:
Corey- so far that's the only thing I can come up with. I just don't know how long that would take...
Yeah, I don't know how long that would take, either. You see, when you try to optimize your algorithm is when you really start to get into the realm of AI. Going brute force, I suppose this is just an "algorithm" exercise. However, any chess playing program tries to parse entire chunks out of the decision tree to optimize the moves it does evaluate as evaluating them all simply takes too darn long.
One question I have for you - do you need to find
all solutions, or just
a single solution? If you're after just a single solution, you could try continually placing the queens in random locations on the board until you find a working solution. Eventually,
you should find a combination that works. It might be the first one you try, it might be the ten-thousandth one you try. That's all just the luck of the draw. If you're trying to find every single solution, however, going with random positioning would probably be very wasteful.
In all honesty, if you want to find every solution possible, I think you need to start with a "brute force" method and then go from there.
There are some rules you could enforce to make your searches more efficient. I guess I don't know for sure, but I'm guessing that it would be impossible to cover the entire board if 2 queens we in the same row/column. If that's really true, you could eliminate every single possibility in which two or more queens appear in the same row or column. That's a whole lot of possibilities you can simply "throw out." You never need to evaluate those possibilities.
If you can come up with a list of rules that you know would prevent you from finding a working solution, you can apply those to your algorithm. For example, start with the brute force method but, before evaluating the entire board for coverage, check the position of your queens against your set rules. If they pass those rules, check for coverage. If not, throw this case out and simply move on.
Of course, by going this route, we're adding an extra step to the process. The hope here is two-fold.
1. We want the check against the rules to be relatively fast. If it takes longer to evaluate that the queens meet the rules than to simply evaluate the board for coverage, we've accomplished nothing at all. In fact, we've simply made matters worse.
2. We want to parse out a significantly large number of options from the set of possibilities. The more possibilities our rules parse out, the more efficient the application becomes. A rule such as not allowing two or more queens to be in the same row/column seems like a rule that would parse a lot of possibilites from the set. A rule such as "don't have queens in opposite corners" may be a good rule, but it applies to very few possibilities. Checking against such a rule is probably more trouble than its worth.
I hope some of this is making sense (and is actually what you're after). It's quite possible that I'm making this much more difficult than intended. :roll: