Magic Squares -- a randomized method

Introduction

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.

A method of finding a magic square using CCM

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.

[When the Java applet cannot be seen/run...]

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.

Method of computation

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).

References

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.