Finally, a Magic Magic 45-omino

January 14th, 2017 by munizao Leave a reply »

In the figure below, the numbers in each row, column, and main diagonal sum to 115:

Quite a long time ago, I came up with the idea of representing the lo shu (3×3 magic square) as a set of squares in a 9×9 grid, partitioned into nine 3×3 cells. The number of squares in each cell would correspond to a number in the lo shu. The most “magic” way to arrange the cells would seem to be to have 5 squares in the set in each row, column, and main diagonal. (This can be done because the lo shu’s magic sum of 15 can be divided among three rows or columns.) Although it doesn’t affect the “magicality” of a figure, I thought it aesthetically desirable for such a figure to be connected (i.e., a single polyomino) and hole-free. There are 12 hole-free magic 45-ominoes, if my code for discovering them is correct.

A figure with the same number of squares in each row, column, and main diagonal makes an ideal canvas for a sparse magic square. But with 45 numbers to place, and 20 constraints to meet, we start to push on the edge of what’s computationally feasible. The solver I wrote (which, I admit, might not have been very good) could not find a solution. Bryce Herdt manually tweaked the output of my solver to make a semimagic solution, that is, one where the rows and columns add to the magic sum, but the diagonals still didn’t work.

When I discovered that the Numberjack constraint engine could easily be used to code solvers for magic figures, I tried it on this problem, but got nowhere. The solver would run for an arbitrarily long period of time without spitting out any solutions. Recently I tried it again, and this time I got solutions. Paradoxically, what made the problem easier to solve was that I added more constraints. I manually placed the numbers 1 through 9 in the 3×3 cells that they correspond to. This seems to have made the search space small enough that the solver would not be able to spend an inordinate amount of time stuck in a barren zone.

Leave a Reply