The Magic Square as a Benchmark

We found the magic square a simple problem with a very rich combinatorics : for a magic square of order n, there are n²! manners to fill tbe nxn matrix with integers between 1 and n², without repetitions, but only very few of them are magic squares (Ball, 1963).

For order 4 there are exactly 7040 magic squares. So we use the magic square as a benchmark to compare mathematical programming, namely mixed integer programming (MIP), with Genetic Algorithms (GAs), that we will show are much more powerful to solve these kind of discrete combinatorial explosive problems. Finally we developed an artificial intelligence randomized minimax algorithm that imitates a human solving the magic square and we showed that in most cases its performance, in terms of number of changes of pairs of numbers, is better than the performance of the GA algorithm.