Posts Tagged ‘magic 45-ominoes’

Finally, a Magic Magic 45-omino

January 14th, 2017

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.

A Semimagic Magic 45-omino

March 1st, 2011

Bryce Herdt has found a solution to problem #21:

The shape of the darker region is “magic” because the number of cells in each 3×3 block corresponds to a number in a magic square, while the number of cells in each row, column, and main diagonal is 5. The sum of the numbers in each row and column is 115.

There’s still room for improvement here: note that the diagonals do not add up to the magic sum. (A mostly magic square with this property is called semimagic.)

Problem #21.1 Find a magic magic 45-omino, as above, but with diagonals adding to the magic sum.

It’s interesting that this solution was found by manually tweaking the output of a program that I wrote to solve the problem. I was never able to get the program to find an actual solution, so I had it give up after a certain number of trials and output the best near solution. There may well be a large number of solutions, but the search space is enormous.

It’s pretty simple to get fairly close by picking a random permutation of numbers and repeatedly swapping them around to get sums closer to the magic sum. But getting from this local minimum to a real solution is the hard part. The problem would seem to call for something like simulated annealing, and indeed I found a reference to a magic square finder algorithm using something similar. (It should be noted that if all you want is a magic square of a given size, there are deterministic methods that will get you one very quickly.) I added a hack to my code to make it do a crude version of this, but it doesn’t seem to have helped much. (The near solution that Herdt fixed up was made with the old version of the code.)

Feel free to look at my solver code (in Python). I do wonder if there is some way it can be fixed up to be better at getting from near solutions to real solutions.

Magic Squares and Polyominoes

January 21st, 2011

Lee Sallows recently created a new site, geomagicsquares.com, about geometric magic squares. These differ from standard magic squares in that the numbers are replaced with shapes, and instead of having a magic sum which all of the rows, columns, and main diagonals must add up to, they have a target shape that the shapes in each row, column, and main diagonal must tile. (As in standard magic squares, each entry in the square must differ from all of the others. I really recommend the site highly; the presentation of the geometric magic squares is nearly as beautiful as the underlying mathematics. Many (but not all) of the geometric magic squares there use polyominoes or other polyforms.

Several years ago, I came up with a different way of combining polyominoes and magic squares. My magic 45-ominoes are polyominoes contained in a 3×3 configuration of 3×3 blocks, such that each row, column, and main diagonal has 5 cells within the polyomino, and each 3×3 block has a number of cells corresponding to a number in a magic square.

After reading Sallows’ site, I wanted to try my own hand at a geomagic square, and I came up with a variation that incorporates ideas from my magic 45-ominoes:

The rows and columns in the diagram all contain 5 cells. I wasn’t able to make the main diagonals work out. Maybe you can?

#20: Find a geomagic square of polyominoes that can be presented in a 3×3 grid of 3×3 blocks as above, where all rows, columns, and main diagonals have an equal number of cells that are contained within polyominoes.

By the way, I’m still looking for what I call a Magic Magic 45-omino; that is, a Magic 45-omino where each cell contains a different number between 1 and 45, and each row and column adds up to 115. (Make that problem #21.) Here’s a near solution: