[Japanese version] | [English version] |

[Temporary Mirror Page (Fast!)] | [Original Page (Newer?!)] |

The *N*
queens problem is
a constraint
satisfaction problem to place *N* queens on *N* by *N*
``chess board'' and to satisfy a condition that no queen can take
any other queens.
When *N* is eight, i.e., a normal chess board is used,
the problem is known as
the eight queens problem. Most of the constraint satisfaction problems
belong to NP-hard problems, for which no efficient solving methods are
known. The *N* queens problem
is one of NP-hard problems, and
it has been using as an example in AI research or programming.

The applet below searches for a solution of the *N* queens problem
in a way that you can track the process by your eye in some extent.
(If this applet is too large, you can use
this small applet. If it is too
small, you can use this large
applet.)
If you change the option value, which is ``medium speed (20 rps)''
in its initial state, to ``full speed,'' the computation will be
done as quick as possible. (20 rps means that the rule is applied
20 times per second (rps = reductions per second). However,
the real rps becomes less.)
You can start the computation again using the ``restart'' button.
You probably find a different solution each time and the computation
time is also different each time, because random numbers are used.

[When the Java applet cannot be seen/run...]

The value of *N* can be changed. If you use ``full speed'' option
on the applet, you can probably see the solution in a few seconds
when *N* is 20 or less in average.
If you change the option, which is set to ``variable catalyst rule''
initially, then you can change the production rule.
The ``single catalyst swapping rule'' sees relatively small number of
data (i.e., the rule is local), so the number of reactions (the number
of rule applications) becomes larger. On the contrary,
The ``variable catalyst MOVING rule'' sees relatively large number of
data (i.e, the rule is non-local), so the number of reactions becomes
smaller. You can find a more
detailed explanation in reference [1], and it is
also explained briefly in the computation method
page.
If the most local rule, the ``no catalyst swapping rule,'' is used,
the computation does not terminate.
(If this rule is used in combination with the option ``full
speed,'' then it will become difficult to stop the computation,
so this combination is inhibited.)

To find a solution using non-local rule, a method similar to simulated
annealing (SA) is necessary. A method called *the frustration
accumulation method* (FAM), which is similar to SA but only uses
local information
(reference [1] or [2])
is used in the above applet. If you select the option
``frustration OFF,'' then you will sometimes find the applet fails to find a
solution (fails to terminate or terminates without finding a solution)
in high probability. (However, the probability to fail is still low
in the case of the *N* queens problem.)
If a solution has been found when the computation process terminates,
an equation, ``MOD = 1,'' is displayed. If the value is less than 1,
then the process has terminated without finding a solution.

If you choose option ``sort LOD,'' instead of ``N Queens problem LOD,'' you can sort the data. (You will see the meaning of ``sorting'' if you try this.) LOD (Local Order Degree) means the local evaluation function. The rule does not need to be changed. The same rule can be used for different purposes, if you use different local evaluation functions, because the rule is primitive (not problem dependent). However, the ``variable catalyst MOVING rule'' is not good for sorting. You will often see sorting fails when using this rule. Try sorting using the ``single catalyst swapping rule'' or others.

If you are interested in the methods of *N* queens or sorting,
see the method page.
(Java applets are also used in the method page for explanation.
)
If you are interested in constraint satisfaction using CCM, especially
on the method of solving the *N* queens problem, see
reference [3]. If you wanted to know various
sorting methods using CCM, see reference [4].

There are applets that solve the *N* queens problem using
conventional method (based on backtracking). For example,
Timothy
Budd's or
this page.
The conventional method takes time proportional to an exponential
function of *N*, and so it needs huge amount of time when *N*
is large. However, this method is superior in that exaustive search
of solutions can be easily done.

See the section of references in the home page to see notes.

- [1] Y. Kanada: Methods of Parallel Processing of Constraint Satisfaction Using CCM --- A Model for Emergent Computation, SIG PPAI, Japan Society for Artificial Intelligence, Feb, 1996.
- [2] IEICE SIG on Artificial Intelligence 94-AI95-4
- [3] IPSJ SIG on Symbol Processing 93-SYM-68-2
- [4] IPSJ SIG on Symbol Processing 93-SYM-71-5

The source program of the above applet is here. However, this applet is the worst in the sense of object oriented programming for the sake of shortening its loading time. That means that everything is packed into one class.

[Return to Examples Home Page]

Copyright (C) 1996, 1999 by Yasusi Kanada I appreciate if you send errata and comments to yasusi @ kanadas.com.

Created: 9/29/1996, Updated: 4/12/2015.