[Japanese version] | [English version] |

[Temporary Mirror Page (Fast!)] | [Original Page (Newer?!)] |

Magic
squares of degree *N* is a collection of *N* by *N*
columns,
which contain integers from 1 to *N*. The sum of *N* integers
of all the columns, all the rows, or a diagonal must be the same.
A method of finding a magic square using CCM is explained here.

The applet below searches for a magic square. If you used this applet in its initial state, you can track the process by your eye in some extent. (If this applet is too large, you can use this small applet.) If you change the option value, which is ``medium speed (20 rps)'' in its initial state, to ``full speed,'' the computation will be done as quick as possible. (20 rps means that the rule is applied 20 times per second (rps = reductions per second). However, the real rps is less than 20.) You can start the computation again using the ``restart'' button. You probably find a different solution each time because random numbers are used, and the computation time is also different each time.

If you change the option, which is set to ``swapping rule'' initially, then you can change the production rule. The rules are explained in the computation method page, but they are briefly explained here. ``Swapping rule'' exchanges two integers in columns and ``rotation rule'' rotates three integers in three columns.

There are many ``local optima'' in the problem of finding a magic
square. (That means this problem is not easy.) So, we have to use a
method like simulated annealing (SA). A method called *the frustration
accumulation method* (FAM), which is similar to SA but only uses
local information
(reference [1] or [2])
is used in the above applet. If you change the value of
``initial frustration'' or ``frustration factor,''
you can control the volume of frustration accumulation.
If you set the value of ``initial frustration'' to 0, or if you set the
value of ``frustration factor'' to 0, you can suppress the mechanism
of frustration accumulation. Then, the probability of stopping the
computation before finding a solution and the probability of
non-terminating computing becomes higher. If you see a message,
``MOD = 0,'' the solution is found when the computation is terminated.
However, if you see a lower value, the computation has been terminated
without finding any solution.

If you are interested in the method of finding a magic square using CCM, see the computation method page. (Java applets are also used in the method page for explanation ) If you want to know more about the method, see reference [3]. (Unfortunately, there is no English paper on this subject.)

You can find conventional methods of finding magic squares through ``the Magic Square Page.'' However, I could not find an applet that finds a magic square using a conventional method (on August '96).

See the section of references in the home page to see notes.

- [1] Y. Kanada: Methods of Parallel Processing of Constraint Satisfaction Using CCM --- A Model for Emergent Computation, SIG PPAI, Japan Society for Artificial Intelligence, Feb, 1996.
- [2] IEICE SIG on Artificial Intelligence 95-AI95-16
- [3] IPSJ SIG on Symbol Processing 94-SYM-75-5

The source program of the above applet is here. However, this applet is the worst in the sense of object oriented programming for the sake of shortening its loading time. That means that everything is packed into one class.

[Return to Example home page]

Copyright (C) 1996 by Yasusi Kanada I appreciate if you send errata and comments to yasusi @ kanadas.com.

Created: 10/6/1996, Updated: 10/19/2003.