narke wrote:
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].
narke wrote:
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].