)
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].
| [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.
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.
Created: 9/29/1996, Updated: 4/12/2015.