This week's giveaway is in the EJB and other Java EE Technologies forum. We're giving away four copies of EJB 3 in Action and have Debu Panda, Reza Rahman, Ryan Cuprak, and Michael Remijan on-line! See this thread for details.

Before I start, I have to say that last time I came here for help, I received LOTS of useful information that helped me solve my recursion problems and earn a great grade on my group project. This time I'm back with another recursion problem that is a spin-off of the non-attacking queens problem.

You all might be familiar with the non-attacking queens in which you use recursion to place N queens on an NxN board. The trick is the queens can't be attacking each other. Well, my problem is similiar yet different. In the project specs, it says the number of queens I will have in my solution is 5. Also, I will be using a fixed 8 x 8 board. I have to use recursion to place my 5 queens so that ALL the spaces are covered. By this, it means that between the 5 queens, each space on the board is either occupied or can be attacked. The project specs also say that there are 728 total solutions, which include rotating the board, and that equals out to 182 solutions per side.

Here's what I have so far: I will use a double-scripted array of ints to represent the board and queens. The board starts off as all 0's, each queen is a 2, and any space that can be attacked gets set to a 1. In the end, if the whole board doesn't have a 0 in it, then I print the coordinates of each queen and reset for the next solution. The representation details are ok; it's just the implementation that I'm having trouble with. Is there an algorithm that I should use to place queens?

Any help/contribution on this topic is greatly appreciated.

Hmmm...this seems more like an AI problem than a recursion problem. What class is this for?

A simple brute force answer would be to start with all 5 queens in a corner. Check for coverage. Move queen 5 to the next space. Check for coverage. Move queen 5 to the next space. Check for coverage. Repeat.

When queen 5 makes it to the end of the board, move queen 4 one space. Put queen 5 back next to queen 4. Check for coverage. Move queen 5 to the next space. Check for coverage.

Continue, continue, continue...

This is obviously a very "brute force" type of a solution. It should, however, get you all solutions, eventually, because you'll have tested every possible combination, programatically. If your goal is not to come up with every solution, but rather a single solution, you could probably devise some sophisticated heuristic to help you out (such as never put two queens adjacent to one another).

Obviously, there are a lot of possibilities to test but, if you can eliminate some of those right off the bat, you can shrink your test size (possibly very dramatically).

This sounds to me like a basic undergraduate level computer science assignment.

If it is, then you will probably have a lab class that goes along with the lecture portion.

In the lab class the instructor (probably a grad student) will give you algorithms and insight on how to design your application. He will probably be your best source of information. We will be a good source of information when you get stuck in some of the coding.

Jason Robers
Greenhorn

Joined: Nov 07, 2004
Posts: 6

posted

0

Jeff- yes and no: this is an undergrad assignment but there's no lab with it; it was just thrown out there as a project that we need to do ourselves. There really isn't a "set" algorithm I was looking for, just wondering if there is one that I can use.

Corey- so far that's the only thing I can come up with. I just don't know how long that would take...

Corey McGlone
Ranch Hand

Joined: Dec 20, 2001
Posts: 3271

posted

0

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:

jefff willis
Ranch Hand

Joined: Sep 29, 2004
Posts: 113

posted

0

It's not a complicated problem. Every one who has studied Computer Science in college has had to solve this problem.

Here is a link that may provide you with more information.

Originally posted by jefff willis: It's not a complicated problem. Every one who has studied Computer Science in college has had to solve this problem.

Not everyone has. :roll: Tower of Hanoi? Sure. Play freecell? Sure. Recognize palindromes? Yup. 5 Queens? Not so much.

By the way, my previous assumption was flat wrong. I built a simple program that randomly tries different combinations until it finds a working solution. The procedure took 30 milliseconds and found this solution (0,0 is the top left corner, 7,7 is the bottom right corner):

7, 0 1, 4 2, 4 0, 1 6, 4

This is a working solution and has 3 queens in the same row.

Same here: I never had to do this problem, but I've some of the ones you mentioned as others, including a program that will play checkers. The professor even tried to hook them up together so each of our programs would play each other but never got it completed. Ah well.

As Corey recommended, I'd start with the brute force approach simply because that's probably what this assignment is trying to teach you to use. The only change I'd make to your initial idea would be how you model the board.

With each step, you are picking up one queen and placing it into the "next" square, again and again until you reach the last square. You then pick up the previous queen, move it to the next square, and bring back the last queen to the square "next to" the one you just placed. This is all as Corey explained, and better than I just did I might add.

My point is that your two operations are "pick up a queen" and "place a queen." If you alter your model, you can simplify your update of the board for those operations.

As it is, at each step you have recalculate all five queens' effects on the board. Instead, start the board as all zeros as you have, and then when you place a queen, add 1 to each square in her row and column. You can add one or two for the square for the queen to your preference, just be consistent across the board. To pick up a queen, simply subtract 1 from each square in her row and column.

Now you don't have to recalculate the board each step. You basically have a pair of "do" and "undo" operations that you can apply while moving queens. This will also speed up your brute-force approach.

Jason Robers
Greenhorn

Joined: Nov 07, 2004
Posts: 6

posted

0

Great- I really appreciate all the help, it's starting to turn the wheels in my head. A question popped up though: how do I keep from getting multiple entries of the same solution? For example, using Corey's output, let's say queen #1 is at (7,0), queen #2 is at (1,4), etc. What stops me from printing the solution queen #1 at (1,4), queen #2 at (7,0), and all the rest the same?

Corey McGlone
Ranch Hand

Joined: Dec 20, 2001
Posts: 3271

posted

0

Originally posted by Jason Robers: how do I keep from getting multiple entries of the same solution?

There are a couple options I can think of.

1. Make sure that you test each configuration only once. If you can ensure that each configuration is tested only one time, you never have the risk of creating duplicate solutions.

2. Create something like a "Solution" class and implement the equals() and hashcode() methods. Then, each time you find a configuration that works, create a Solution instance from the configuration and try to add that Solution instance to a Set. Because the Set won't allow duplicate values, as long as your equals method is functioning, the Set will only take unique Solutions. When you're done, the solutions set should contain 1 instance of each solution.

The most thorough solution would be to use both but, if you implement either one thoroughly, the other becomes unnecessary. If you can make sure that you test each configuration just once, you can bypass a lot of extra processing. If you go with the second approach, each time you want to add a Solution to the Set, you're going to have to test every Solution already in the Set to ensure that this new one is unique.

Anyway, those are my thoughts on it.

David Harkness
Ranch Hand

Joined: Aug 07, 2003
Posts: 1646

posted

0

Originally posted by Jason Robers: how do I keep from getting multiple entries of the same solution?

Corey's method will work. Just for kicks, here's a hint that will allow you to implement the Solution very compactly and teach you about bit operations in Java:

There are 64 positions on an 8x8 board

Each position is either empty or has a queen (two states)

A bit is either clear or set (two states)

In Java, a long integer is 64 bits

I leave it to you to investigate bit fiddling if you go this route. As a starter, you'll need to look up the bitwise AND and OR operators (& and |) and the bitwise shifting operstors (<< and >> and their unsigned equivalents (or is it signed? I look it up when I need them).

However, reread Corey's description of the algorithm (or mine; I just reworded his). Using it, you won't create the type of duplicate solution as you suggest (where two queens are flipped). You will produce equivalent rotations, however. I can clarify if you don't see why, but first try to see why what I said is true. [No guarantees that I'm not entirely mistaken, though. ]