So... the eight queens problem, can you help set me up on the right path

I was thinking of attempting this, but I would need a bit of help by which I mean quite a lot.

first of all I need the logic... this requires recursion, I understand factorial recursion but this is much more complicated. I'm going to wright down how I think the problem might be solved and you guys please look it over and correct me.

I guess I would need a base case, I think it would be if (queens == 0)... so the method "place" would take in the number of queens

now, if queens does not equal 0 then find a free position

check 1,1

it's free, place queen

call method again (queen-1)

check 1,1, check 1,2 check 1,3 check 1,4 etc

check 2,1, check 2,2

it's free, place queen

I do this until I meet a condition where there are no free places... what now? it has to backtrack to the previous queen and replace it. but how do I communicate this to my program? if queen 8 is not placed then the method will return to its previous call and stop there?

with fibonacci the lowest level returns 1 or 0, something to work with. so my method would have to return a variable to specify no more places to its caller method? you see this is when my head hurts and I dont know what I'm doing anymore...

do while loop, if varible no more places == true then move queen 7 to the next spot and call queen 8?

you guys are gonna have to help me now... and remember I'm an idiot, so simple words are nice

Re: So... the eight queens problem, can you help set me up on the right path

Quote:

Originally Posted by

**EscSequenceAlpha** check 1,1

it's free, place queen

call method again (queen-1)

check 1,1, check 1,2 check 1,3 check 1,4 etc

check 2,1, check 2,2

One way to make the algorithm more efficient: once you have placed n queens you can skip n rows/columns when trying to find where to place the next queen.