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 program below searches for a magic square. If you used this program in its initial state, you can track the process by your eye in some extent. 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 program. 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 programs 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 program 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