N Queens Project
New faster algorithm to find a solution for more than 1.000.000 queens in less than 1 second
1000 queens in 1000x1000 board .......................... 00:00:00.003 Download
5000 queens in 5000x5000 board .......................... 00:00:00.003 Download
10000 queens in 10000x10000 board ....................... 00:00:00.004 Download
1000000 queens in 1000000x1000000 board ................. 00:00:00.037
100000000 queens in 100000000x100000000 board ........... 00:00:01.235
All from 4 to 1000 Download
C#
Using simple console application with C#. You can implement it in another language, its only to explain the algorithm.
BACKTRACKING
Backtracking is a general algorithm for finding all (or some) solutions to some computational problems.
- Donald E. Knuth (1968). The Art of Computer Programming. Addison-Wesley.
- Gurari, Eitan (1999). "CIS 680: DATA STRUCTURES: Chapter 19: Backtracking Algorithms". Archived from the original on 17 March 2007.
MIN-CONFLICT
In computer science, the min conflicts algorithm is a search algorithm or heuristic method to solve constraint satisfaction problems (CSP).
HEURISTIC FILLING HOLES
New hollow filling techniques to improve backtracking and MinConflict. It is necessary to determine if is useful without any other tecnique, only heuristic
PROJECT
This is not the final algorithm. Everyone can send his own modifications or algorithm to find the fastest.
BY MAIL
You can send your modifications and results and it will include in this project with your name.
RESULTS
The results need to be save in a TXT file with 0 and 1 to be checked for everyone.
STANDARD
In the future the project could have a protocol to call the different algorithms and get results to check which is the fastest.
ARTICLES
-
Minimizing conflicts: a heuristic repair method for constraint satisfaction and scheduling problems
The paper describes a simple heuristic approach to solving large-scale constraint satisfaction and scheduling problems. In this approach one starts with an inconsistent assignment for a set of variables and searches through the space of possible repairs. The search can be guided by a value-ordering heuristic, the min-conflicts heuristic, that attempts to minimize the number of constraint violations after each step. The heuristic can be used with a variety of different search strategies.
More -
Complexity of n-Queens Completion
The n-Queens problem is to place n chess queens on an n by n chessboard so that no two queens are on the same row, column or diagonal. The n-Queens Completion problem is a variant, dating to 1850, in which some queens are already placed and the solver is asked to place the rest, if possible. We show that n-Queens Completion is both NP-Complete and #P-Complete. A corollary is that any non-attacking arrangement of queens can be included as a part of a solution to a larger n-Queens problem. We introduce generators of random instances for n-Queens Completion and the closely related Blocked n-Queens and Excluded Diagonals Problem. We describe three solvers for these problems, and empirically analyse the hardness of randomly generated instances. For Blocked n-Queens and the Excluded Diagonals Problem, we show the existence of a phase transition associated with hard instances as has been seen in other NP-Complete problems, but a natural generator for n-Queens Completion did not generate consistently hard instances. The significance of this work is that the n-Queens problem has been very widely used as a benchmark in Artificial Intelligence, but conclusions on it are often disputable because of the simple complexity of the decision problem. Our results give alternative benchmarks which are hard theoretically and empirically, but for which solving techniques designed for n-Queens need minimal or no change.
More -
A polynomial time algorithm for the N-Queens problem
The n-queens problem is a classical combinatorial problem in the artificial intelligence (AI) area. Since the problem has a simple and regular structure, it has been widely used as a testbed to develop and benchmark new AI search problem-solving strategies. Recently, this problem has found practical applications in VLSI testing and traffic control. Due to its inherent complexity, currently even very efficient AI search algorithms developed so far can only find a solution for the n-queens problem with n up to about 100. In this paper we present a new, probabilistic local search algorithm which is based on a gradient-based heuristic. This efficient algorithm is capable of finding a solution for extremely large size n-queens problems. We give the execution statistics for this algorithm with n up to 500,000..
More -
Explicit solutions to the N-queens problem for all N
The n-queens problem is often used as a benchmark problem for AI research and in combinatorial optimization. An example is the recent article [1] in this magazine that presented a polynomial time algorithm for finding a solution. Several CPU-hours were spent finding solutions for some n up to 500,000..
More
-
Swarm intelligence for permutation optimization: a case study of n-queens problem
This paper introduces a modified particle swarm optimizer which deals with permutation problems. Particles are defined as permutations of a group of unique values. Velocity updates are redefined based on the similarity of two particles. Particles change their permutations with a random rate defined by their velocities. A mutation factor is introduced to prevent the current pBest from becoming stuck at local minima. Preliminary study on the n-queens problem shows that the modified PSO is promising in solving constraint satisfaction problems.
More -
N QUEENS PROBLEM
This paper gives eight Kinds of methods for constructing for solutionsof the n Queens problem;and discusses the transformation group G on theset W of Solutions of the n Queens problem;and studies the existence ofthe symmetric solution and the strong symmetric solution of the n Queensproblem and methods for constructing them;by the group G gives a formulafor the partition of W.Finally,we find all solutions of the n Queens problemif n≤13..
More -
The n-queens problem: a new approach
Let D be a digraph, possibly with loops. A queen labeling of D is a bijective function l:V(G)⟶{1,2,…,|V(G)|} such that, for every pair of arcs in E(D), namely (u,v) and (u′,v′) we have (i) l(u)+l(v)≠l(u′)+l(v′) and (ii) l(v)−l(u)≠l(v′)−l(u′). Similarly, if the two conditions are satisfied modulo n=|V(G)|, we define a modular queen labeling. There is a bijection between (modular) queen labelings of 1-regular digraphs and the solutions of the (modular) n-queens problem. The ⊗h-product was introduced in 2008 as a generalization of the Kronecker product and since then, many relations among labelings have been established using the ⊗h-product and some particular families of graphs. In this paper, we study some families of 1-regular digraphs that admit (modular) queen labelings and present a new construction concerning to the (modular) n-queens problem in terms of the ⊗h-product, which in some sense complements a previous result due to P\'olya..
More -
A Solution to the N-Queens Problem Using Biogeography-Based Optimization
Biogeography-based Optimization (BBO) is a global optimization algorithm based on population, governed by mathematics of biogeography, and dealing with geographical distribution of biological organisms. The BBO algorithm was used in the present study to provide a solution for the N-queens problem. The performance of the proposed algorithm has been evaluated in terms of the quality of the obtained results, cost function, and execution time. Furthermore, the results of this algorithm were compared against those of genetic and particle swarm algorithms.
More
-
Comparison of Heuristic Algorithms for the N-Queen Problem
This paper addresses the way in which heuristic algorithms can be used to solve the n-queen problem. Metaheuristics for algorithm simulated annealing, tabu search and genetic algorithm are shown, test results are demonstrated and upper bound complexity is determined. The efficiencies of algorithms are compared and their achievements are measured. Due to the reduction of the fitness function complexity to O(1) problem…
More