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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
The $n$-queens completion problem
An $n$-queens configuration is a placement of $n$ mutually non-attacking queens on an $n\times n$ chessboard. The $n$-queens completion problem, introduced by Nauck in 1850, is to decide whether a given partial configura…
An Adaptive Genetic Algorithm for Solving N-Queens Problem
In this paper a Metaheuristic approach for solving the N-Queens Problem is introduced to find the best possible solution in a reasonable amount of time. Genetic Algorithm is used with a novel fitness function as the Meta…
Solving N-Queen Problem using Las Vegas Algorithm with State Pruning
The N-Queens problem, placing all N queens in a N x N chessboard where none attack the other, is a classic problem for constraint satisfaction algorithms. While complete methods like backtracking guarantee a solution, th…
Application of the Brain Drain Optimization Algorithm to the N-Queens Problem
This paper introduces the application of the Brain Drain Optimization algorithm -- a swarm-based metaheuristic inspired by the emigration of intellectual elites -- to the N-Queens problem. The N-Queens problem, a classic…
Combinatorial OptimizationDecision MakingA Non-Recursive Space-Efficient Blind Approach to Find All Possible Solutions to the N-Queens Problem
N-Queen’s problem is the problem of placing N number of chess queens on an NxN chessboard such that none of them attack each other. A chess queen can move horizontally, vertically, and diagonally. So, the neighbours of…
AllN-Queens Problem - All Possible Solutions