Linear algorithm for solution n-Queens Completion problem
  A linear algorithm is described for solving the n-Queens Completion problem
for an arbitrary composition of k queens, consistently distributed on a
chessboard of size n x n. Two important rules are used in the algorithm: a) the
rule of sequential risk elimination for the entire system as a whole; b) the
rule of formation of minimal damage in the given selection conditions. For any
composition of k queens (1<= k<n), a solution is provided, or a decision is
made that this composition can't be completed. The probability of an error in
making such a decision does not exceed 0.0001, and its value decreases, with
increasing n. It is established that the average time, required for the queen
to be placed on one row, decreases with increasing value of n. A description is
given of two random selection models and the results of their comparative
analysis. A model for organizing the Back Tracking procedure is proposed based
on the separation of the solution matrix into two basic levels. Regression
formulas are given for the dependence of basic levels on the value of n. It was
found that for n=(7-100000) the number of solutions in which the Back Tracking
procedure has never been used exceeds 35%. Moreover, for n=(320-22500), the
number of such cases exceeds 50 %. A quick algorithm for verifying the
correctness of n-Queens problem solution or arbitrary composition of k queens
is given.
