What is the N-Queens-Puzzle?

Followingthis Wiki link to the 8-Queens-Puzzle one quickly understands the simple puzzle imposed. Summarizing, the objective is to place theN-Queens on a(NxN) board, so that no queen is attacked by another - vertically, horizontally or diagonally (just like chess).
(One) Solution:

Not a solution:

Simple to understand, yetexponentially hard to solve.

Problem-Formulation

We nowunderstand our problem - great - but the question here is:
How will we solve it? - What is thebest approach formost plays?

1. Will we try foreach queenevery not occupied position and verify its validity? - in other words, brute force our way to the solution.
2. Will we place a queen and immediately cross outall the positions it attacks and try to place the next one onall the valid positions left?
3. Do we even need to considerall thevalid positions left?
4. For the first queen, the board is empty - where do we try to place the very first one sinceall positions are valid?Everywhere?

The list goeson and on. As I'm trying to expose here, there are many different andvalid ways to formulate the problem and find a solution.
But some are better than others.Way better.
Obviously the first approach always comes down tobrute-force. But this is where ourunderstanding and perspective of the problem comes into play. By brute-forcing the various possible positions to place a queen we are mistakenly trying solution paths that - if we give it a little thought - are,from the very first step,unsolvable.

Just to give you a little taste

Bear with me in this line of thought:
Given the way a queen attacks the various positions on a board,does it make any sense to place another on thesame row? or thesame column? or even,the same diagonal?No, the answer is no, it does not make sense, because we know immediately that this positions are invalid once we place a queen - we need not even think of this possibilities.
Even more, since we now know there is no point in placing a queen on the same row, column or diagonal as another, we know exactly where to place the veryfirst queen. No, we do not haveN * N (readsN times N) possibilities for the first queen, actually, we only haveN, on the very first column. And the same goes for the next queen - meaning, there is no point in trying to place a queen somewhere else than theleftmost free column, since every column will have exactly one and only one queen.
This perspective (or, formally, problem-formulation) will immensely reduce the possible solution path's to take - therefore, will be much faster and efficient

Conclusions

The way we tackle a problem, starting with how well we understand it, will greatly affect the outcome of our solving. This is actually tangible with some AI resources:
How well does an algorithm preform given a certain problem-formulation?
How much time, tried possibilities and different solution path's will it expand to reach a solution?
I have implemented (here) in python all of the above problem-formulations and some more, so that anyone can try and verify it by themselves.
I purposely implemented them with ablind-search, the least efficient way to find a solution for a problem we know so well - to show how well it will preform compared with poor/better problem-formulations.

Regards

I hope you enjoyed the post and actually give mycomparator tool a try to see it in action by yourself! Please give mefeedback or implement new ideas of problem-formulations!
See you next time,
Diogo from Portugal