If the rule is executed with an appropriate initial state, the system repeats the selection of three queens and reaction of the instance. The initial state must satisfy the following condition: there is only one queen in each row and each column. The easiest layouts of queens that satisfy this condition are for all queens to be put on a diagonal line. If this condition holds, it holds at any time in the system because the reaction preserves the condition. The system stops when a solution to the *N* queens problem is found.[*4.3]

A more detailed semantics of a reaction is illustrated in Figure 6. The instance selections and reaction are repeated while possible. Because there is only one rule, the system interpreter does not have to select a rule. In this rule, the mutual order degree between the queens to be swapped, i.e., Queen2 and Queen3, is not changed. Thus, the system interpreter decides whether to react the instance or not, referring to the other two LODs displayed in the figure. The instance is reacted in this case, because its instance order condition holds. This shows the reason why the catalyst, Queen1, is necessary. The LODs are not changed if the rule contains only the queens to be swapped, and so the system does not work.

Although a solution is not always found in general by this method, because the search is stochastic and not exhaustive, our experiment shows that the problems never fail to be solved, and are solved in polynomial order time in average. The performance is fairly good with no extra device, probably because the problem is easy to solve.

The average number of matches, i.e., the number of executions of LHS of rules, and the average number of reactions until a solution is found have been measured for *N* <= 50 using an S strategy. The initial layouts of queens are random (generated using pseudo-random numbers), and runs that fall into limit cycles are ignored. The results are shown in Figure 7. All values shown in this figure are averages of ten executions. The execution time is approximately proportional to the number of matches. Thus, the order of execution time is estimated to be O(*N*^4.6). The performance using an MR strategy is not shown here, but the trend is almost the same as the S strategy.

If backtracking is used to solve this problem, the order of execution time is exponential, so the CCM-based method is much faster. However, this simple CCM-based method is slower than other more intelligent methods, such as those shown in Yagrom and others [Yag 64, Cha 74, Shi90, Sos 91], which find a solution in O(*N*).

Go to: Next section, Parent node

(C) Copyright 1994 by Yasusi Kanada and IEEE Y. Kanada