4. Example: The N Queens Problem

The N queens system, an CCM-based system for finding a solution to the N queens problem, is shown in this section. The performance of its trial executions is also shown. The N queens problem is an extension of the eight queens problem. The N queens system is tried because, although the target of our methodology is to develop complex systems, we have to start with a simple system, and this system has several characteristics that will probably lead us to a better understanding of complex systems.

4.1 Reaction rule and local order degree

Figure 4 shows the visual rule and LOD of the N queens system. This system contains only one rule and a definition of the mutual order degree, o(x, y), for queens. This rule swaps the rows of two queens (Queen2 and Queen3 in Figure 4), see Figure 5.[*4.1] Queen1, which can be called a catalyst, remains unchanged by the swapping. The role of the catalyst is explained later. No link is used in this rule. The value of LOD o(x, y) is defined to be higher (i.e., 1) when queens x and y are not diagonally oriented, and lower (i.e., 0) when they are diagonally oriented.[*4.2]

Figure 4. A rule and LOD of the N queens problem

Figure 5. The meaning of the N queens rule

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.

Figure 6. Computation of the IOD in the N queens rule

4.2 Performance

We have developed a computation language, SOOC, and its interpreter.[*4.4] The rules and LODs of several problems have been developed and executed using SOOC. The performance of the N queens system is summarized below.

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.

Figure 7. Average computation time of the N queens system (using an 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).

4.3 Other Examples

Several optimization and constraint satisfaction problems have been solved by CCM-based computation. They include traveling salesperson problems (TSP), integer programming problems, graph coloring problems [Kan 92b], and sorting. The results are summarized in Table 1. This table shows that simple problems can be solved using only one or a few simple rules and only one LOD by CCM.

Table 1. Current Applications of CCM

Go to: Next section, Parent node

Y. Kanada