# Sparse and Magic Squares

April 20th, 2021 by munizao

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:

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.