<![CDATA[Greedy Queens Problem]]>In the famous Queens Problem, you need to put n chess queens on an n x n chessboard so no two queens attack each other. It has been proven that a solution exists for all n except n=2,3.

One of the methods (albeit an ineffective one) to solve it is by greedy algorithm, which does a depth-first search. In this case, a queen is placed on the first row, on the first column. The next queen is placed on the second row, starting from the first column. As it attacks a previous queen, it is moved to the second column, and again to the third column. Now as they don’t attack, a third queen is placed from the leftmost column rightward, and so on. When a queen cannot be placed, the previous queen is removed and placed to the next column. This guarantees a solution, as it checks every possible board as long as no conflict has been made.

For example, with n=4:
First queen tries a1.
Second queen tries a2. Conflict with a1.
Second queen tries b2. Conflict with a1.
Second queen tries c2.
Third queen tries a3,b3,c3,d3 in order but conflicts each time. Second queen is retracted.
Second queen tries d2.
Third queen tries a3, conflict with a1.
Third queen tries b3.
Fourth queen tries a4,b4,c4,d4, all conflict. Third queen is retracted.
Third queen tries c3,d3, all conflict. Third queen is retracted. Second queen is retracted (cannot go further).
First queen tries b1.

This algorithm is run until the solution b1,d2,a3,c4 is found (the first solution found). In total, there are 26 queen tries.

For n=5, it can be verified that it takes 15 queen tries to arrive at a1,c2,e3,b4,d5.

Can you compute the number of queen tries for a given n effectively? In other words, is this problem in P? (Naively executing the algorithm gives a possible n^n steps, so it’s not polynomial. You need a better way.)

Extra Problem

A revised version of the algorithm doesn’t put a queen when it makes a conflict. So, for the n=4 example above, we have:

First queen on a1.
Second queen can’t go on a2,b2. Second queen on c2.
Third queen can’t go anywhere, second queen is retracted and go on d2.
Third queen on b3.
Fourth queen can’t go anywhere. Third queen retracted. Second queen retracted. First queen on b1.
And so on.

It takes 8 queen tries now. For n=5, it takes 5 queen tries, or in other words the exact number required.

Can you compute this number effectively too?

]]>