Queens on a Chessboard

摘要

Can you place N queens on an NxN chessboard such that none of them will threaten the others? It is easy find such a placement for an 8x8 board. It is also simple to develop a recursive, backtracking program to produce such a placement for any N (N>3). However, the recursive execution may be very costly. Can you offer an efficient, systematic way for generating such a placement for any N? The new challenge in this issue is to develop an O(N) algorithm for this task. This is a rather well known task, together with its extension of counting the number of different legal placements for a given N. Yet, the reader is encouraged to try it by herself, as the solution process combines the recognition of rather simple, but not immediate, mathematical patterns with the utilization of appropriate design heuristics.