8 queens problem

[narke]

One thing interests me,
I tried to solve the 8 queens problem all by myself, without using a known solution.
My algo only achieved to place 7 queens.
Do you consider that this problem is too easy or quite hard?

Solutions in various languages are here: http://rosettacode.org/wiki/N-queens_problem

[iansjack]

Pick the right tool for the problem and it should be trivial. I would pick Prolog.

[narke]

I used Python but I'm interested to know how OSdevers rate the complexity of this problem.
I know that one can tell me that one must use recursion and it becomes trivial but when you must figure it out by yourself it becomes a bit trickier than watching an existing solution and saying "I understood".

[Combuster]

It's a fairly typical constraint satisfaction problem you can solve with textbook algorithms like DFS.

It's also a problem you can optimise by looking at the problem in particular: you don't need to try all 64 places for each queen, (or the subset that remains available at that point), but only a subset of eight for any particular queen as there is exactly one on each row.

[bwat]

I used Python but I'm interested to know how OSdevers rate the complexity of this problem.
I know that one can tell me that one must use recursion and it becomes trivial

It is trivial, hence the simplicity of the Prolog "generate and test" type of solution, i.e., find a permutation of N queens (generalised from 8 to N queens) on a chess board [generate], now test to see if none attack each other, upon failure backtrack to find a new permutation. Eventually all permutations will have been attempted. Imperative/functional programmers will use loops/recursion for a simple solution instead of backtracking.

Obviously this takes time and after a while the programmer starts to think about heuristics to reduce the search space [see Combuster's answer].

but when you must figure it out by yourself it becomes a bit trickier than watching an existing solution and saying "I understood".

Problems like this are the bread and butter of the Prolog programmer and are used as homework exercises at universities around the world. It only seems tricky when you haven't done a few of them. Give it a proper try and don't feel ashamed if it takes a loooong time to solve. The next problem of this type you attempt will see the answer come more quickly. See http://dtai.cs.kuleuven.be/ppcbook/ for a free book chock full of these types of problems [you don't need to solve them with Prolog].

[hometue]

If I remember this well it was covered in competitive programming. (the book title is competitive programming). If I am not wrong we use...uh...brute force (aka backtracking), but it can be optimized to prevent using every possibilities.

@combustor: how do you use DFS? I don't see any way...

[Combuster]

You need to place 8 queens. You can view that as a tree where the root is an empty board and every step away from the root adds a single queen (in an available position). The application of DFS easily follows from there.

[hometue]

Hm...it seems fine but as a competitive programmer, I wonder performance wise which would be better (I know usually DFS would be better but you will never know). Also looking at it I can see a slight possible problem where the programmer totally forgets about the root. Btw, I am wondering based on that logic would it be BFS or DFS, since we are going a step from the root at one time BFS sounds like a good solution too.

[Combuster]

Breadth-first only works if the solution is close to the starting position. In the typical case and this case in particular it's a bad idea because you need to find (and keep in memory) all of the 7-queen solutions before you are even allowed by the algorithm to find the 8-queen solutions.

If you need all solutions, DFS finds everything in the same time as BFS, with less memory use. If you need one solution, BFS is a gross horror.

[AndrewAPrice]

I would probably do a brute force algorithm, but rather than working out all ~4 billion permutations, you could do an early termination (mark all cells queen 1 can see as invalid, only iterate queen 2 over valid cells, mark all queen 1 & 2 see as invalid), also you can cut the permutations down significantly by only placing higher queens in front of lower queens (to avoid repeating old permutations).