[ Top page ]

« Purpose of this blog | Main | Fusion of digital and analog »

The N queens problem

     Q   
 Q       
       Q 
   Q     

It is time consuming to solve the N queens problem (See the description below), as same as other constraint-satisfaction problems. Therefore, many methods are deviced to solve it faster. In my research, I often used this problem as an example too.

The first time I used this in Logic/Symbolic Vector Processing. By using a logic programming language such as Prolog, you can program exaustive search using backtracking. The objective of this research was to convert such programs to high-speed programs for supercomputers. However, the acceleration ratio of even a successfully converted program was constant, so the program still needs exponential computation time.

The second time I used this problem in CCM (Chemical-Computation Model). In CCM, randomness was inherently introduced, and we did not aim perfect computation (or complete method). In such a stochastic computation, it does not need exponential computation time. By using CCM, you can find a solution by a personal computer much faster than by a supercomputer using a backtracking method. You can try such computation by using the N Queens Problem and Sorting page, which contains CCM-based Java program of the N queens problem. You can try various methods by changing options on this page, but I will describe the detail of this issue in another opportunity. (But the above page contains most of such information.) To develop stochastic solving methods, neural networks and genetic algorithms can also be used. The method using CCM has similar nature to such methods.

Apart from Kanada's research, the N queens problem is also used in N. Wirth's book titled "Algorithms and Data Structures".  R. W. Floyd's paper titled "Nondeterministic Algorithms" (Journal of the ACM, Vol. 14, No. 4 (1967), pp. 636-644) also used this problem. This paper was explained by Kanada in the 2003-February issue of "Information Processing" (Vol. 44, No. 2, p. 198). As I wrote in this explanation, the problem was also used as an example of quantum computation.

Explanation of the N queens problem

The eight queens problem is the problem to get layouts of eight queens on a chess board without taking each other. An extension of this problem to N-by-N board is the N queens problem. Problems to get a solution that satisfies given conditions, such as the N queens problem, are called constraint satisfaction problems (CSPs). Many CSPs belongs to a class of difficult problems, called NP (Non-Polynomical), which can only be solved by enumerating solutions. The N queens problem is one of them. The reason why this class is called non-polynomial is that problems in this class cannot be solved in time represented by N's polynomial expression (i.e., it takes exponential time to solve them).

[Related page: The N Queens Page]

Keywords: N queens problem, Eight-queens problem, Vectorization of symbol-processing, CCM, Chemical Casting Model, Chemical Computation Model, Neural network, Genetic algorithm, Randomized computation, Stochastic computation

Comments (3)

ali:

Hi
I need the code for n-queens problem by using genetic's algorithm search technique with the source code written in using java language. ...

Guru:

Good job, thanks.

Appreciate for it.

Post a comment

About

This page contains a single entry from the blog posted on October 18, 2006 9:31 PM.

Many more can be found on the main index page or by looking through the archives.

Creative Commons License
This weblog is licensed under a Creative Commons License.
Powered by
Movable Type 3.36