Linear algorithm for solution n-Queens Completion problem
This provides an efficient solution for a classic combinatorial puzzle, with potential applications in constraint satisfaction and algorithm design, though it appears incremental as it builds on existing backtracking methods.
The paper tackles the n-Queens Completion problem by developing a linear algorithm that determines if a given placement of k queens on an n x n board can be completed to a full solution, with an error probability not exceeding 0.0001 that decreases as n increases. It reports that for n from 7 to 100,000, over 35% of solutions avoid using backtracking, and for n from 320 to 22,500, this exceeds 50%.
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.