### A Method of Solving Constraint Satisfaction Problems using Production Rules and Local Evaluation Functions

Kanada, Y., and Hirokawa, M.: , SIG Notes of Symbol Processing, Information Processing Society of Japan, 93-SYM-68-2, 1993, Published by IPSJ.

[ 日本語のページ ]

[ Paper PDF file (in Japanese) ] [ Paper postscript file (in Japanese) ]

[ OHP postscript file: Slides, Handout ]

[ OHP PDF ファイル: Slides, Handout ]

[ ** N queens problem demo in Java** ]

Abstract:
The authors have proposed the Chemical Casting Model
(CCM), which is a
computation model for self-organizing computation. In this model, "programs"
consist of a few production rules and evaluation functions (or local order
degrees), both of which only refer to local information. A method of
solving certain constraint-satisfaction problems, based on this model, is
presented in this paper. This method enables to solve constraint-satisfaction
problems, such as the *N*-queens problems or map coloring problems, in a
polynomial order time, without using deterministic and procedural constraint
propagation, but using a stochastic method, and by a very simple "program."
This paper also mentions to the characteristics of the computation by on this
method, based on several measurements.

Introduction to this research theme: CCM: Chemical-Computation Model