Looking for her for million times
…
(The process to solve the 16th trimagic
square)
Chen Qinwu
It was by chance that I had
several talks with Chen Mutian who is a retired professor of our department. From
the talks I knew that he had been working at the solution to magic square. In
the beginning, I felt such a magic was unimaginable considering its infinitesimal
possibility. (Exactly speaking, even if there are 1012 trimagic
squares in the world, the possibility of existence is still below 10-495
because of 256!=8.6x10507 )
Then Prof. Chen told me that he
spent about one year solving 11th order bimagic square. But a German
solved 12th order trimagic square three years ago. I asked him what use it was to spend so much energy and time solving
it. He said that he derived much pleasure from it, but many experts were
finding the significance of its application, the improvement of algorithms, the
parallel processing, the scheduling of the economy decision-making, etc. I was doubtful
about it. He told me that he was searching for the answer to 16th trimagic
square. Owing to the large amount of the calculation, the program often had to
be executed for several days, and we should select certain strategy to reduce
the amount of the calculation. Recently he divided the program into some
sections, and came to the campus to do a check and make some adjustments from
six miles away every afternoon. Then I thought the calculational speed would be
obviously improved, if I transplanted the program to a complete 32bits environment
in the computer of my laboratory with a CPU of Pentium 4 2.0G Hz. As expected, the
speed was about twenty times more than the original after we succeeded in
transplanting the program. This made us very excited.
In our subsequent contacts, Prof. Chen introduced some effective methods
he used to solve magic square. Gradually, I came to have some understanding of
the problem. He used a matrix of 16 rows which had been arranged to meet the
requirement to make row to row adjustments, so the amount of calculations of a
row is 1616≈1.8x1019 .
Even though the fastest super computer in the world was used to seek the
solution, several years were needed. So we had to look for some algorithms to decrease
the amount of calculations so that ordinary computers could seek the solution of
the problem in limited time.
We used the numbers between 0 and 255 so that the computer could handle easily. After
analyzing the construction of the matrix and the characteristics of the
problem, I thought there was a most probable way that we could meet the
requirement. If I make the sum of two numbers in the same row amount to 255,
the amount of calculations will decrease to 168≈4.3x109, Which can be solved by the computer in my laboratory in a short
time. For the combination
of complementary numbers whose sum is 255 has been occupied by columns,
if I can make the higher seven bits of the two numbers (binary) reverse and the
lowest bit similar (i.e. Num2 = Num1 XOR 0xFE), where the sum of two even
numbers is 254 and the sum of two odd numbers is 256, it can meet the
above-mentioned requirement and can be transformed by the given matrix above.
I told Prof. Chen the method, and he said I might as well have a
try. Of course, because the above-mentioned transformation needed some
programs, it was very complicated. So I wrote a program and asked Prof. Chen to
execute, I thought there would be a result in two or three days. But Prof. Chen
realized the complexity of the problem. He said it was not so easy. Many people
have made a sustained effort and spent a lot of time looking for it, but so far
there has been no answer. He encouraged me to have a try.
I went on undeterred by the difficulties ahead. Before such difficulties, I never lost
my confidence. On the contrary, the more difficult the problem was, the more
courage I had. I inputted the program to the computer and debugged, I found the
problem was much more complex than I had expected. After some days’ modifying
and debugging, there was an initial result. Although there was no solution fulfilling
the requirement of all sixteen rows, thousands of rows met the requirement.
After modifying again and again, there were eight rows meeting the requirement
simultaneously. So I continued writing programs, I separated the number combination of the remaining eight rows to search independently. Because the
amount of the calculation had added up to 816≈2.6x1014
, it had not even finished in several days and no another new row meeting
the requirement appeared.
I thought it deeply over and over，and programmed to test. I found if I
constructed the matrix independently and when the two numbers (whose sum was
255) were combined complementarily, many matrixes of 16 rows meeting the
requirement would come out. The program did not even end after running several
hours to output millions of matrixes. When the two numbers (i.e. the sum of two
even numbers is 254 and the sum of two odd numbers is 256) were combined complementarily,
the program could find many matrixes which had 12 rows meeting the requirement simultaneously
in a short time. Hence, I separated each two numbers of the remaining 4 rows of
the matrixes above-mentioned, and readjusted the program to search. However,
because there were numerous combinations of permutation, the program ran for
several days and could not find the solution meeting the requirement of all 16
rows.
I pondered hard about the restrictive
conditions of the program. Then I found when the above
rows were adjusted, the algorithm fetching numbers in the same column could be
improved to fetch numbers in the same column or in the adjoining columns. More
matrixes meeting the requirement of all 12 rows simultaneously came out. Owing
to the increasing amount of calculation, several computers worked together for
some days, but the program was still running. Though there were a lot of
matrixes meeting the requirement of all 12 rows simultaneously, which added up
to some hundred thousand, there was no one meeting the requirement more than 12
rows simultaneously.
The breakthrough happened when Prof. Chen analyzed my results and
made some very important discoveries. In the course of my communicating with
Prof. Chen, he took my results which I obtained to analyze. When he knew I
obtained the solution which could meet the requirement of 12 rows
simultaneously and the sum, the sum of square of the remaining 4 rows could
meet the requirement, he thought the result was significant and it had
approached the advanced level of research of 16th magic square in the world.
During the seven-day Labor Day vacation, Prof. Chen
and I kept on researching without interruption. This time Prof. Chen took the
data to analyze and the next day he entered the campus to prove his vital
discovery, and he told me his discovery: If 8 pairs of combination numbers meet
the requirement, they must be 4 pairs of even numbers and 4 pairs of odd numbers,
and the sum, square sum, cubic sum of the 4 pairs of even and odd number
combination are constant values. (The sum is 1016 or 1024, the sum of square is
172720 or 174760, and the sum of cubic is 33032192 or 33553408)
I was deep in thought again. If Prof. Chen’s discovery was right,
the amount of calculation would decrease considerably. The next day, I
programmed to prove that the discovery was right. And I also discovered another
important formula: If the sum, the sum of square and the sum of cubic of the 4 pairs of even
number combination are constant values mentioned above, add 1 to every even
number and it will be transformed to 4 pairs of odd number combination, whose
sum, square sum and cubic sum meet the constant mentioned above. In this way,
the amount of programming to construct the magic square could be decreased to a
half. Then I readjusted the program again, and soon I gained a matrix that had
14 rows meeting the requirement simultaneously, there were only two rows left
to the final result.
Isn’t there a whole solution to the problem containing
all characteristics? Though it was Labor Day vacation, I was weighed down with
researching trimagic square. I continued studying 20th, 24th, 28th, 32nd
trimagic square. The 24th had 22 rows meeting the requirement simultaneously,
and such results showed by the computer were innumerable as the hair on an ox,
we could find millions of matrixes like that with computer, but the whole
solution to the 24th had not been found yet. The 32nd had 32 rows meeting the
requirement for some time, but when the columns were adjusted, because of its
huge calculation, the result still could not be found.
I was not reconciled to the fact! I considered 16th
trimagic square over again. Because the calculation was huge, I made the
algorithm search the result only in the same column or in the adjoining columns.
However, because we could execute the program quickly now, we could surely make
out an algorithm to search the whole matrix to prove the existence of its
solution.
That afternoon, I rewrote the program. In spite of its complexity, I
kept on thinking hard. As I had not had a good rest, I felt so tired that my
head ached seriously. But I was still considering the problem while I was
taking a rest. Finally the program was executed successfully, and the result
came out soon. Then I checked the result.
I look for her for million times. When all at once I turn my head, I
find her there where lantern light is dimly shed. (An ancient Chinese poem
written by Xin Qiji )
After adjusting the 16 rows, it’s as easy as winking to adjust
16 columns and the diagonals. However, as I didn’t take a rest at
In the evening, after a rest of several hours, I felt a little
better, and I went on arranging the 16 columns of the matrix. The following morning,
when I told Prof. Chen the exciting news, he was so happy that he couldn’t
helps jumping. He came to the campus in the morning against his own rule, and
we immediately wrote a program to search the diagonals.
Those who work hard will be rewarded！A month of painstaking work had not been done for nothing. After working
day and night and surmounting so many difficulties, we got a perfect result at
last. 16th trimagic square many people search for you even in their dreams,
when you come to us quietly, you look as beautiful as beautiful can be!
Learning the news that 16th trimagic square came out, Gao
Zhiyuan, Li Kangqiang, chairmen of Chinese Magic
Square Pursuers Association , and a French friend sent
me letters of congratulation.
Here are some of them:
Dear Mr. Chen Qinwu:
Learning of your success in searching for the 16th-trimagic
square, I feel very happy! The solution of 16th trimagic square is
an important achievement. Many pursuers have studied for years, and we have been
longing for the result even in our dreams. Now you and Prof. Chen Mutain succeeded in working out the solution to the 16th
trimagic with computer through your efforts and operation. What inspiring news!
You have won honor for us Chinese. I congratulate you on behalf of the Chinese
Magic Pursuers Association.
We hope you to publish this result as soon as possible. Of course,
we hope it can be certificated internationally. We have a French friend, who is
collecting the results of magic square all over the world. I believe your
success can boost our own morale.
Gao Zhiyuan, Yan’an
Dear Mr.
Chen Qinwu：
Hello！
16th trimagic square is really a stronghold hard to
capture. Seven years have elapsed, since 1997. Many magic square expert have
made painstaking efforts in it，and you have succeeded. You have won honor for us Chinese，I, myself, on behalf of friends of Chinese
Magic Pursuers Association, congratulate you and your partner sincerely, and
hope you to achieve more successes. I wish the result can be certificated
internationally.
Now Mr. Wang Zhonghang is taking charge of
the accounts of our association, I hope we can cash the premium set for this.
Of course, you have studied magic square not for this little premium, but we
must keep our promises.
We have received and saved all the mails you sent. We will publish
them in our publication.
Li Kangqiang,
Chairman of
Dear
friends,
I
have checked your square, and
yes it is a trimagic square. Congratulations!
Your square has been added in the update done
today of www.multimagie.com/indexengl.htm
Click
on News of May
I
understand, with your email addresses, that you are working at the
Are
you students or teachers? Could you explain how you have constructed your
square?
Best regards from
Christian Boyer.
Translated by Prof. Zhuang Hecheng
Chen Junwei
Zhang Quan