Kanada's Research Topics

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]