|
10阶平方幻方研究的故事
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 to
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 has exatly 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 throught 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 are 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 lies on one diagonal, and b and c on the other, then c
and d must be on 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 is 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
|
