A Numerical Solution of the Magic Hexagon Using Local
Search and Global Search Methods
Jaewook Shin
Major in Computer Engineering
Graduate School of Engineering
Yonsei University
Supervised by Professor Lee, Yong Surk
Abstract
The magic hexagon is a type of magic square which was created
by Choi, Seok Jung during the Chosun era. This problem has a
great state space and is considered very difficult to solve.
Because the magic hexagon can be viewed as a combinatorial
optimization problem, general method used to solve the
combinatorial optimization problem can also be applied.
In this thesis, various methods are tried to solve the magic
hexagon problem. Among them, K-interchange heuristic mixed with
the steepest descent algorithm produced a solution in 4.2
seconds on the average with a 80486 DX2-66 PC. And 60,000
different solutions are found about every 11 minutes when
backtrack algorithm is used.
These methods can be introduced to real world situations
since they are general algorithms which can be applied to
most combinatorial optimization problems.
More ...
A magic hexagon is a collection of 9 hexagons connected as shown below.
In the below shape, if you connect numbers with edges, you will see 9
hexagons; One at the top, two in the next level, and three in the middle and
so on. The problem is to find an assignment of 30 numbers from 1 to 30 to
each vertex of the shape so that if you sum 6 numbers at the vertices of each hexagon, the
sums for the nine hexagons are all equal. Of course, each number should be
assigned exactly once as in magic square. The below assignment is a solution where
each hexagon has the sum of 93. But the sum value ranges at least from 79 to 108 only
for the ones I found.
