International Symposium on Nonlinear Theory and its Applications
Xi’an, PRC, October 7–11, 2002

An Approach to N-Queens Problem Using Chaos Neural Network- Challenge to Finding All Solutions of N-Queens Problem Isao Tanaka†, Yoshifumi Nishio†, and Mikio Hasegawa‡†Dept. of Electrical and Electronic Eng.,
Tokushima University
2-1 Minami-Josanjima, Tokushima, Japan
Email: {isao130, nishio}@ee.toushima-u.ac.jp

Abstract‡Wireless Communications Division
Communications Research Laboratory
3-4 Hikarino-Oka, Yokosuka, Japan
Email: mikio@crl.go.jp

that the method to change the weights connecting thefiring neurons can successfully find many different solutions of the N-Queen problem.

In this study, we investigate three different update methods of the chaos neural network in order to approach tofinding all solutions of the N-Queens problem.
By computer simulations for various sizes of the N- 2. N-Queens problem and chaos neural network
Queens problem, we confirm that the method to change
In the N-Queens problem, N chess queens must be
the weights connecting the firing neurons can successplaced on a squere chessboard composed of N rows andfully restrain the regeneration of the once-appearedN columns, in such a way that they do not attack eachsolutions.
other. In other words, the arrangement of the queens
must satisfy the constraint that any two different queens
1. Introduction
are placed in different rows, columns and diagonals [2].
One of the possible arrangements for N = 5 is shown in
Combinatorial optimization problems can be solved
Fig. 1. The number of the possible arrangements bewith the Hopfield neural network [1]. If we choose concomes larger exponentially as N increases. The numbernection weights between neurons appropriately accordfor N ≤ 15 is listed in Table 1.
ing to given problems, we can obtain a good solution
by the energy minimization principle. However, the network state is often trapped into a local minimum anddo not reach the global minimum. In order to avoid
this critical problem, chaos neural networks have been
applied to various optimization problems successfully.
On the other hand, finding all solutions of nonlinear
systems is a very important problem appearing in various fields of natural science. The N-Queens problem
is a long-known combinatorial problem having a huge
number of the solutions. Several researchers have also
proposed the methods to solve the N-Queens problem
by using the Hopfield neural networks [2][3]. However,the Hopfield neural network can find only one solution
among numerous possible solutions.
In this study, we try to find many possible solutionsof the N-Queens problem by using neural network. The
chaos neural network could find several solutions because
Figure 1: N-Queens problem
of its chaotic dynamical motion. However, the network
state visits the once-appeared solution quite often. We
investigate three different update methods of the chaos
In order to find different solutions, as many as possineural network in order to restrain the regeneration of
the once-appeared-solutions. By computer simulations ble, we apply the chaos neural network to the N-Queens
for various sizes of the N-Queens problem, we confirm problem.

-255-

3.1. Method 1

Table 1: Number of solutions of N-Queens problem.
N45
6789101112131415

In the Method 1, the weights connecting the firing
neurons are reduced to restain the regeneration of thefiring pattern after every updating. Namely, we choose
one of the firing neurons. A constant value “∆W ” is subtracted from the connecting weights from this neuron tothe other firing neurons. Moreover, in order to maintainthe activity of the network, “∆W (N −1)/{N (N −1)+1}”
is added to the rest of the weights. This procedure is applied to the all firing neurons.

# of Solutions
210440
92
352
724
2680
14200
73712
3655962279184

3.2. Method 2

The equation of the chaos neural network is given asxi,j (t + 1) =kxi,j (t) +N XNX

ωi,j,k,l f (xk,l (t))

3.3. Method 3

k=1 l=1−αf (xi,j (t)) − θi,j (1 − k)(1)where f (x) is a sigmoid functionf (x) =1¡ ¢1 + exp − yεIn the Method 2, the threshold of the firing neurons
are reduced to restain the regeneration of the firing pattern after every updating. A constant value “∆θ” issubtracted from the thresholds of the all firing neurons.
Moreover, in order to maintain the activity of the network, “∆θ/(N − 1)” is added to the non-firing neurons.

The Method 3 adds another term to the definition of
the weights connecting the neurons. The weights arere-calculated after every updating according to Eq. (5).

(2)ωi,j,k,land k is time attenuation constant and α controls nonlinearity.
The weights connecting neurons are defined to findsolutions of the N-Queens problem as=−δi,k (1 − δj,l ) − δj,l (1 − δi,k )−δ|i−k|,|j−l| (1 − δi,k δj,l )sX−D(Si,j,m Sk,l,m )(1 − δi,k δj,l ) (5)m=1where s is the number of the solutions before the updating and Si,j,m is the constants memorizing the positions(3) of the firing neurons for the m-th solution, namely, Si,j,m
is 1 if the m-th solution has a queen at the postion (i, j),where δr,s is the two-dimentional Kronecker delta, which
otherwise zero. The term 1 − δi,k δj,l is introduced to neis defined as
glect the connection of neurons to themselves.
½
1, if r = s
δr,s =(4)0, if r 6= s.
4. Simulated results
ωi,j,k,l=−δi,k (1 − δj,l ) − δj,l (1 − δi,k )−δ|i−k|,|j−l| (1 − δi,k δj,l )Also, we use the method suggested by Sato et al. (1.1
Computer simulations of N-Queens problem are perin [4]) to decide firing of neurons.
formed for the cases of N =10 and 15. The number of theupdate of the network state is fixed as 10,000 and thistrial is iterated 10 times for different initial conditions.
3. Three Proposed Methods
The average of the number of the obtained solutions isThe chaos neural network can find several solutions as evaluated. The simulated results using the three proit is because of its chaotic dynamical motion. However, posed methods are compared with the results obtained
the network state visits the once-appeared solution quite from the normal chaos neural network.
often. We propose three different update methods of theThe parameter α is varied from 1.0 to 4.0. Moreover,chaos neural network in order to restrain the regenera- k and θi,j are fixed as k = 0.8 and θi,j = 0.1. Wetion of the once-appeared-solutions.
carried out computer simulations for various values of-256-

the parameters of the three methods ∆W , ∆θ and D.
The following results are the best we obtained.
Figure 2 shows the simulated results for N = 10.
Next, the simulated results for N = 15 are shown inFig. 3.
From these figures, we can say that the proposed threemethods can find more solutions than the ordinary chaos
neural networks, especially for the case of N =15.

:Method1
150

Queen’s kinds

In this study, we have tried to find many possible solutions of the N-Queens problem by using the chaos neuralnetwork. We investigated three different update methods of the chaos neural network in order to restrain theregeneration of the once-appeared-solutions. By computer simulations for various sizes of the N-Queens problem, we confirm that the method to change the weights
connecting the firing neurons can successfully find manydifferent solutions of the N-Queen problem.
However, the number of the found solutions is far awayfrom the number of the all solutions. Finding new methods better than the three methods is our important future research.

:Normal10050011.5

22.5
alpha33.5

4(a) Method 1. 4W = 0.002.
200:Normal:Method2
150

Queen’s kinds

5. Conclusions

200100References
50[1] J. J. Hopfield, “Neurons with Graded Response Have
Collective Computational Properties like Those ofTwo-State Neurons,” Proc. Natl. Acad. Sci. USA,
vol. 81, pp. 3088-3092, 1984.

01

1.5

2

2.5
alpha

3

3.5

4(b) Method 2. 4θ = 0.0004.

[2] J. Manddziuk, “Solving the N-Queens Problem
with Binary Hopfield-Type Network,” Biol. Cybern.,
vol. 72, pp. 439-445, 1995.

200:Normal:Method3[3] T. Nakaguchi, K. Jin’no and M. Tanaka, “Hysteresis Neural Networks for N-Queens Problems,” IEICE
Trans. Fundamentals, vol. E82-A, no. 9, pp. 18511859, 1999.
[4] K. Sato, T. Ikeguchi, M. Hasegawa and K. Aihara,“An Optimization Method for Quadratic Assignment
Problems by Chaotic Dynamics and its Characterization by Lyapunov Dimensions,” IEICE Tech. Rep.,
vol. NLP64-13, pp. 13-20, 2001 (in Japanese).

Queen’s kinds

150

100

50

01

1.5

2

2.5
alpha33.5(c) Method 3. D = 0.0004.
Figure 2: Simulated results for N =10.

-257-4

200:Normal:Method1

Queen’s kinds

150

100

50

01

1.522.5
alpha3

3.5

4(a) Method 1. 4W = 0.002.
200:Normal:Method2

Queen’s kinds

150

100

50

01

1.522.5
alpha

3

3.5

4(b) Method 2. 4θ = 0.0004.
200:Normal

Method3

Queen’s kinds

150

100

50

01

1.5

2

2.5
alpha

3

3.5

4(c) Method 3. D = 0.0004.
Figure 3: Simulated results for N =15.

-258-