Stochastic Search Algorithm for Constraint Satisfaction Problem
Sipang Dirakkhunakon, Yoothana Suansook · 2008
In this paper we have formulated the stochastic search algorithm to solve classic constraint satisfaction problem (CSP) in mathematics 'N-queen problem'. This problem is a CSP that objects or states have to satisfy a number of constraints or criteria which have to place queens on the chessboard so that no queens attack each other. This problem is use as a benchmark to test search algorithms because the problem is difficult to search and there are many possible solutions. The stochastic search algorithm that we use is adapted the idea from condense matter physics called simulated annealing. The algorithm is widely use for solve many combinatorial optimization i.e., traveling salesman problem, wiring connection in electronics device, graph coloring. The experiment results show that acceptance ratio is converge to some constant.