eight queens problem without backtracking

[rahul adams]

Hello

I am doing problems from "Introduction to Java Programming" by Daniel Liang (10 ed.). There is this problem of eight queens on chess board. Now, this is a chapter on single dimensional arrays and author has not introduced any recursion discussion till this point. Eight queens problem is a special version of N queens problem with N=8. I emailed author and he said that the problem can be solved without using backtracking/recursion. All the approaches I have seen on the net use backtracking. I tried very hard to come up with solution but have not succeeded so far. Can anybody tell me any hints ?

Thanks

[Les Morgan]

You iterate through the entire board placing a Queen as can be done accordingly.  So you begin by checking placement of your queen at (0,0), by iterating through all squares to see if there is another queen that would make (0, 0) illegal. There is not so you place it. Now you check(0, 1)  for validity of your second queen by iterating through all of the board again, (0, 1) fails for you retain your queen count and move on to (0, 2).... until you have completed your task.

[rahul adams]

Thanks Les

So I will need to keep track of the forbidden positions on the board. Thats what I found hard to do. There might be a case where after filling 5 queens, all further positions are blocked. In that I will need to backtrack to the first queen and start all over again. So it seems to me that this problem can not be solved without backtracking. What do you think ?

thanks

[Paul Clapham]

Here's a method which doesn't use backtracking: Put eight queens on the board randomly and see if it's a valid solution; repeat until you get a valid solution.

[Les Morgan]

I do not agree. Using backtracking in recursion is much different than iterative methods.  What you are looking for is an A* iterative method. If you do not get a valid answer and have to throw out your board and start with (01), then that is an iterative method, there is no backtracking used.

[Les Morgan]

Back in the day that I was doing my CS BA, I took a graduate course in AI, we were asked by the instructor for volunteers so he could study problem solving methods in the humans, the 8 Queens problem was one he used to see how we would set it up. My thought was if I place with a knight style of patter, I would have the most success.  It was a novel thought and we didn't have to implement, he wanted to see how we would approach the problem.

With backtracking you are literally reversing through the layers of recursion back to see if you can find a solution from the previous level... In recursion you may go all the way through and hit 7 Queens on the board, then you cannot place the 8th, so you backtrack to when you had seven, if you fail there you back track to when you had 6, and if you fail there you backtrack to where you had 5. At each level backtracked you try alternate placements to see if you can find an over all solution to the problem.

When you do something iteratively there is no back track, you start over, and seek a different start, then continue.  When you have exhausted your options, then you try a different placement algorithm, but the idea is to iteratively go through an A* algorithm--British Museum--and take the first solution; thus, clipping the rest of the attempts, or alternatively, you save that one and continue with your A* iteration.

[rahul adams]

Paul, your approach is nice but may take long time I guess since we are using randomness here. Les, I see your point. Now the difficult part is to figure out how to identify the forbidden positions as we move on with the queens. Any ideas on it ?

[Les Morgan]

I would calculate each position for validity as you test placement, I would also make an 8x8 grid or array to be able to logically reference and use a simple placement counter to see when 8 have been placed.

Remember to reset everything between generations.

[Henry Wong]

In my opinion, this is actually a classic case of a recursive method simplifying an iterative method. To do one queen, you will need two nested loops (assuming one for horizontal and one for vertical). And to do eight queens, you will need 16 nested loops.

So, yes, iterative is possible (to reach all combinations). And yes, you can optimize it down to eight nested loops. And furthermore, yes, with randoms, or some math technique mentioned later, you can get it down to one nested loop.... but... why? Recursion works best here.

Anyway, you can also have a mathematical representation to define the state. Say, each queen needs 6 bits of data, since each queen can be in 64 possible positions. With 8 queens, that is 48 bits of data. So, you can loop through a 48 bit number to find a valid state. With this algorithm, you also need to check to see if any queens are in the same square too, to avoid that invalid case.

Henry

[Ryan McGuire]

I can think of a hokey way to do with no backtracking.  

Use 8 nested loops from 0 to 63 to represent the position of each queen.

int q1, q2, q3, q4, q5, q6, q7, q8;

OUTER_LOOP:
for (q1=0; q1<64; q1++) {
    for (q2=0; q2<64; q2++) {
        if (conflict(q1, q2)) {
            continue;
        }
        for (q3=0; q3<64; q3++) {
            if (conflict(q1, q3) ||
                conflict(q2, q3)) {
                continue;
            }
...
                            for (q8=0; q8<64; q8++) {
                                if (conflict(q1, q8) ||
                                    conflict(q2, q8) ||
                                    conflict(q3, q8) ||
                                    conflict(q4, q8) ||
                                    conflict(q5, q8) ||
                                    conflict(q6, q8) ||
                                    conflict(q7, q8)) {
                                    continue;
                                }
                                // q1 - q8 must be a valid position.
                                break OUTER_LOOP;
                            }
                        }
                    }
                }
            }
        }
    }
}
if (q1+q2+q3+q4+q5+q6+q7+q8 < 512) {
    Print out the answer in some pretty format.
}

Or does using a loop count as backtracking?

[EDIT] Now that I reread some of the previous comments, I think this is a lot like what others had in mind.  Maybe.

[Knute Snortum]

You shouldn't post a complete solution in BJ until the OP has.

[Ryan McGuire]

Knute Snortum wrote:You shouldn't post a complete solution in BJ until the OP has.

I wouldn't call this complete, but point taken.  Unfortunately, the option to edit or delete is no longer available.

[Paul Clapham]

rahul adams wrote:Paul, your approach is nice but may take long time I guess since we are using randomness here.

Your original post didn't mention anything about finding effective or efficient solutions, it only asked about solutions which didn't require recursion or backtracking.

But you may be right, although guesswork is not a good strategy for evaluating the speed of some code. You might find that a well-designed random algorithm is faster than you think.

[Carey Brown]

The solutions here are avoiding recursion, but whether or not it avoids "backtracking" is up for interpretation. Even a many-level nested set of loops implements a form of backtracking. So, with this poetic license in mind I would propose keeping a stack of row/col positions as you test each one and decide if the next push should increment the column by one, or increment the row by one and reset the column back to zero. Of course if you reach the last column for the current row you'd have to start popping the stack to get back to a prior state. This can be done with a single loop that continues as long as the stack size is less than eight.

[rahul adams]

Thanks all.  I think I got sufficient feedback on the ideas for solution. I will think along these lines and try to come up with the solution.