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]

## Comments (3)

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. ...

Posted by ali | December 21, 2008 12:56 AM

Posted on December 21, 2008 00:56

Good job, thanks.

Posted by Guru | June 15, 2010 11:12 AM

Posted on June 15, 2010 11:12

Appreciate for it.

Posted by Sergio Aguero | June 15, 2010 11:13 AM

Posted on June 15, 2010 11:13