Magic Squares and Algorithms for Finance

In my recent post Equation Solving for Kids, I introduced magic squares and reported the number of magic squares of the order 4 to be 880. The first computer program I wrote for calculating this number was in interpretted Basic on a Sharp MZ80A (with 32 kByte memory) in the early 1980s, and it took about 3 days to calculate them. On contemporary hardware, compiled versions need less than1 second.

Magic squares of order 5
The magic sum of the order 5 squares is 65, and there are 12 equations to be satisfied (5 rows, 5 columns, 2 diagonals). One of these equations is redundant, so there are 14 free entries. If you set , e.g., the entries marked by "x", you can calculate the remaining entries explicitly.

All these "x"-es must be integers between 1 and 25, and they must be different. How many possibilities are there? There are Binomial (25, 14) pssibilities to choose 14 numbers out of 25. As position plays a role, this has to be multiplied by Factorial(14). Thus, we obtain 388588515194880000 possibilities to set the "x" entries. Solving the system for the empty cells, does not necessarily yield a magic square which additionally has to satisfy that all 25 entries are different and lie between 1 and 25. Obviously, if you iterate the "x"-es in 14 nested loops, you should calculate dependent entries as soon as possible and jump out of the loop if the magic conditions cannot be satisfied any more.
Implementing such an algorithm, you can find out that the number of magic squares of order 5 is 2202441792.

Reordering Rows and Columns
When you know that the following square is magic,

you can interchange rows 1 and 2 and rows 4 and 4, respectively, and the interchange columns 1 and 2 and columns 4 and 5, to obtain

which is again magic. Similarly, you could also interchange row 2 and 4, and columns 2 and 4.

Following these ideas, you can rearrange (by rotations, reflections and rows/colums interchanging) any magic square of order 5 in such a way that the smallest off-center diagonal element will be located in position (1,1) (8 possibilities), that a15 < a51 (by possible reflection, 2 possibilities) and that a22 < a44 (2 possibilities). 
This reduces the effort to be taken by a factor 32. Additional computing time can be saved by taking into account that the square (26 - aij) is also magic. Be careful with double-counting when a33=13.

Not knowing the work of Richard Schroeppel (1973), I calculated the number of order 5 squares in the early 1990s on a MicroVax 3500 (see below, with 8MB of memory). My Fortran code took about 8 hours of CPU time.

Lessons learned for algorithm development
The above ideas to reduce the number of candidates have several similarities in Monte Carlo simulation for finance applications: From my point of view, interchanging rows and columns is related to antithetic variables in Monte Carlo simulation.
Exiting loops as soon as possible (magic squares) is somehow related to rejecting paths of Monte Carlo simulation in risk management, e.g., when you kno in advance that the path considered will not end in extreme percentiles.

Next week: The other way round: Monte Carlo simulation and magic squares.