Solving the Magic Square Problem Using Modern Heuristic Methods

Ms_sf_2This problem is to solve the Magic Square Problem (constrained and unconstrained versions), a combinatorial optimization problem, using modern heuristic methods.

Magic squares have been a source of fascination since ancient times, over 4,000 years. A magic square is a square matrix of size n, containing each of the numbers 1 to n2 exactly once, in which each column, each row, and both diagonals add up to the same magic number.

It is possible to impose many different constraints on a standard magic square problem. Here the constrained version stipulates that the solution matrix must have a pre-defined contiguous sub-matrix.

Here is the binary code, and here is the readme file. As the 2nd runner-up, this program solved the constrained version of 400 x 400 magic square within a minute in the 2011 International Optimisation Competition.

  • X. Xie, “Meta-LS Solver for Magic Square Competition,” International Optimization Competition, 2011. [PDF] [Code] [Bibtex]
    @TechReport{xie2011tr00,
    Title = {Meta-LS Solver for Magic Square Competition},
    Author = {Xiao-Feng Xie},
    Code={http://www.wiomax.com/team/xie/project/magic/MagicSquare.jar},
    PDF={http://www.wiomax.com/team/xie/project/magic/IOC_readme.pdf},
    Institution={International Optimization Competition},
    Year = {2011}
    }

Posted on: Dec 20, 2011

Category : News Software


Leave a Reply