Story of the first 10th-order bimagic square
Text written by Fredrik Jansson, in February 2004.

I got many of these ideas from Christian Boyer's www.multimagie.com web site, and Walter Trump's story of the 12th-order trimagic square. Thank you!

I first listed all bimagic series of order 10, and wrote them in a file. I found 24,643,236 series. This is also the number which was reported on the multimagic series page of www.multimagie.com.

A series is represented by a 128 bit number, where bit n is set if the series contains the number n. The 10 rows of a magic square can not have any number in common, this is quickly checked with the boolean AND function. A set of 10 independent rows are searched for by backtracking. When 10 independent rows are found, the program tries to find a set of 10 columns, such that every column has exactly one number common with every row, and no column has any number in common with an other column. This is done by first searching for all series that have exactly one bit in common with every chosen row, and then trying to construct a set of 10 independent columns from these. This too is done by a backtracking search. A quick test to see if two numbers have more than one bit in common is: a AND (a-1) is zero if a has at most one bit set, because subtracting 1 changes the least-significant set bit to 0, but leaves every other set bit unchanged.

If a set of 10 independent columns is found, an at least semi-bimagic square can be constructed from the chosen rows and columns. A diagonal must have one number in common with every row, and one number in common with every column. The series in the list of possible columns already have one number in common with every row, so the program searches through these to find all that have one number in common with every chosen column. The two diagonals must have no numbers in common in an even-order square, so every pair of possible diagonals is tested. If they have no bits in common, these could possibly be the diagonals in our square.

There is one additional requirement that almost made me loose hope about finding the square: if row 1 contains the numbers a and b, column 1 contains a and c, column 2 contains b and d,  a and d lie on one diagonal, and b and c on the other, then c and d must be in the same row.

So when we have chosen the first element on diagonal 1, there is only one row that contains this element, so this must be the first row. There is also only one column that contains this element, so this must be the first column. The first row has exactly one element in common with the second diagonal, this element must be the last element in the first row. This also fixes the position of the column containing that element, it will be the last column. The last column has one element in common with the first diagonal, this element must be in the lower right corner d. The first column has one element in common with the second diagonal, this must be in the lower left corner c. If elements c and d are on different rows, nothing can be done besides using an other pair of diagonals.

The same check must also be done for the second and second-to-last elements of the diagonals, and so on.

I think the key ideas in my program are to use bit-strings to represent the series, and not to consider the order of the rows and columns, or the order of the elements in the rows and columns. This makes the search space considerably smaller.

When the program found the solution, it just printed the rows, columns and diagonals used, and I assembled the square by hand.

The program was written in C. I had plans to optimize the most timecritical part (searching for a set of 10 columns with no bits in common) with assembler-language, possibly using SSE-instructions that can do calculations on a 128-bit number at once, but the solution was found before I got that done. This project took about a week to program, and the square was found in less than 24h of computing on my Athlon 2800.

Fredrik Jansson, Turku, January 2004.

Return to the home page http://www.multimagie.com