m-queens
                              --------
The famous n-queens problem is actually a simplifcation of the much more
important m-queens problem, which is originally attributed to Adardhir I the
founder of the Sassanid Empire. His mother Rodhagh challenged him to cover
his empire with the minimum number of castles so that no place was not pro-
tected by cavalry within 1 week riding. Adardhir simplifed this problem into
the m-queens problem, based on the game of chess, which was becoming popular
at the time, under the name shatranj. His son Shapur I is attributed with the
first optimal solution on a standard 8x8 chessboard. The m-queens problem,
generalizing Adardhir's problem, is to cover an n x n chess board with as few
queens as possible so that no queen can take another and no more queens can
be placed on the board without being taken.

For example given n = 5 a solution might be
q = [2, 0, 5, 3, 1]; representing the solution

     . Q . . .
     . . . . .
     . . . . Q
     . . Q . .
     Q . . . .

where 0 means no queen on that row. Note that above a 5th queen cannot be
placed on the board witjout being under attack.

and a minimal solution might be
q = [5,2,0,3,0]; representing the solution

     . . . . Q
     . Q . . .
     . . . . .
     . . Q . .
     . . . . .

That is, above we see that by placing 3 queens on the 5x5
board the queens do not attack each other and all other vacant
positions are under attack. The above solution is minimal

The problem then is given an n x n chess board put the minimum number
of non-attacking queens on the board such that each vacant position 
is attacked by at least one queen


Patrick Prosser