Posts Tagged ‘magic 45-ominoes’

Sparse and Magic Squares

April 20th, 2021

A while back, I had the insight that the 3×3 magic square could be transformed into a sparse square, or a set of cells within a square in a grid where every row and column contains the same number of cells. The converse transformation of turning a sparse square into a magic figure is not original to me, but applying it to the sparse square from the first transformation gave a pleasing result. And then I stopped there.

Or I almost did:

Right, so if I had set the 1 where the 34 is, and the 6 where the 26 is before running the solver, (and likewise the 4 and 9) that would have been more elegant.

This is a figure I came up with before my blogging hiatus that never made it into a post. The rows, columns, main diagonals, and 3×3 blocks all sum to 115. This could be seen as a version of my doubly transformed magic square on a slightly degenerate 3×3 magic square whose entries are all 5’s.

But it was hard to see where to go from there. The next size up, the 4×4 square, was unsuitable. Its magic sum is 34, and since we’d be using a 4×4 block, we wouldn’t be able to evenly split the squares from each row and column into four lines. And 5×5 seemed big enough to be a mess to work with. So I was done.

But it turns out we can do something nice with the 4×4 after all. Suppose we number the squares starting with 0 instead of 1. We still can’t use 4×4 blocks, but since the highest value is now 15, 3×5 blocks look like a possibility. And indeed, our magic sum is now 30, of which 3 and 5 are both factors, so it works:

There was an interesting bug in the code I used to produce this. I was looking for figures that are single, hole free polyrects. One way to help filter these out from other solutions is to check for 2×2 blocks with checkered corners. If one is present, you must have either a hole or more than one polyrect. But by accident the constraint I added was more broad; it applied to any 2×2 block with two dark and two light rects. I was not able to get a single polyrect solution with this constraint, but I did find something at least as interesting. Notice that every 3×5 block is the same, after swapping dark and light, as the complimentary block with the number that you get by subtracting from 15. This was not an explicit constraint in my code, so it’s interesting that this property managed to emerge. I still haven’t found a single hole-free polyrect solution without the buggy constraint, but I’m confident they are out there. My solver code is just too inefficient to find them in a reasonable amount of time.

Once I was back on the trail of magic sparse squares, I came back to the magic partition square I discussed in a previous post. (There are four ways to partition the numbers from 1 to 8 into two subsets of four numbers that sum to 18. Each of the 8 subsets is present as a row or column in the square.) Since this figure uses smaller blocks, my solver had no trouble with it.

My work on magic sparse squares is ongoing, and I hope to have more to share with you soon. I’ve put my solver code up on GitHub. I know I’ve had a long hiatus without coming up with new material, but I expect to have a few more blog posts in the coming months, and I hope you’ll enjoy the shiny objects that I find and share.

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: