General Solutions to a Subclass of the 3x3 Semi-Magic Square Problem

(don’t be intimated by the math. it’s fun math. and you don’t need anything more than a grade school education to follow along.)

This morning, my partner (who works at a school) provided me with a math challenge. Can you fill up a 3 by 3 grid with the number 1 through 9, where all columns and rows add up to the same number?

It might be fun to give it a try yourself. Can you come up with a solution? What did you learn in the process?

These squares (called “magic squares”) are a common problem issued by teachers in grade school to provide students with practice in arithmetic. Since I have successfully passed sixth grade mathematics, I decided to challenge myself by not only coming up with a solution, but coming up with an algorithm to generate all valid solutions to the 3x3 semi-magic square problem. This is a very well-studied problem so I’m sure this is not new mathematics, but I wanted to at least solve it myself without reference to any papers.

My partner presented me with the following solution:

Where, upon further calculation, we can verify that each row and column sum to exactly 15.

My partner made the further comment: “doesn’t have to add to 15 i just did it that way”.

Our first order of business it to show whether or not this is true; whether the row and column sum (“magic number”) is always 15. This will provide us with a helpful invariant we can use in our algorithm. In fact, I will show that we can prove an even stronger claim: the sum of all rows and columns is always 90 (equivalently, the average sum of a row or column is 15, since there are exactly 6).

Lemma 1. The sum of all rows and columns in any 3x3 square filled with the numbers 1-9 is always 90.

Proof. Notice that each of the numbers 1 through 9 is counted twice: once in a row, and once in a column. Therefore, the sum of all columns and rows must be exactly double the sum of the numbers 1 through 9. The sum of 1 through 9 is the ninth triangular number calculated as \(T_9 = (9 + 1) \cdot \frac{9}{2} = 45\); therefore, the sum of columns and rows must be twice this, or equal to 90.

■

Example. Take the following randomly-generated square.

The rows sum to 18, 16, and 11. The columns sum to 19, 20, and 6. Add these together and you’ll get 90.

Bonus alternative proof to Lemma 1. Write down the numbers 1-9 in a 3x3 grid. Sum the columns and rows and you’ll get 90. Because each possible 3x3 square is a permutation of every other 3x3 square formed by swapping elements, the sum of 90 must remain constant. This is satisfactory, but we need to be convinced of the fact that every square can be reached from every other square by swapping elements pairwise. This is straightforward: we can always make swaps as long as at least two elements are dissimilar between two squares. This is always the case, because squares cannot only differ by one element due to uniqueness of the elements (1-9), and square that differ by zero elements are trivially the same.

If you do not understand this argument, then sit on it for a while, and if you still don’t understand, you can safely ignore it. This is a good rule for life.

Lemma 2. The sum of a row or column of any solution must be 15 (i.e. the “magic number” is 15).

Proof. This follows directly from the fact that if any square filled with 1-9 must have rows and columns summing to 90 (Lemma 1), and the fact there are 6 rows + columns. Therefore if we impose the requirement that each row and column must be equal, they must all be 90/6=15.

■

Now, we have a very powerful fact: the sum of every row and column in a solution must always be 15.

This is still not the same as providing an algorithm for generating a solution, but it’s helpful. I can see a few ways forward. Two of which are valid but are boring and uninstructive. And a third solution which is actually quite wonderful and exciting.

Solution 1. Brute-force. There are 9!=362880 possible squares, which is not too large of a space to search, and we can write a computer program to check which ones are valid solutions. Boring af.

Solution 2. Write down the following square:

Now, we can write the following systems of equations: \(a+b+c=d+e+f=g+h+i=a+d+g=b+e+h=c+f+i=15\). Furthermore, we add the constraint that \(\{a, ..., i\}\) must be a permutation of \(\{1, ..., 9\}\). Plug it into a constraint solver and we get solutions. Still boring af and we learn nothing.

Solution 3. The main event.

I initially tried some sort of algorithm where you randomly generate a square, then pairwise-swap elements until you reach a solution. I think this is possible if the algorithm is constructed carefully. However, I gave up on this approach when I had an epiphany for something totally different, and quite beautiful.

So, we know that our magic number is 15. Notice anything about it? Well, how about the fact that it’s an odd number? Surely, you say, this cannot have any relevance. Yet this will turn out to be a crucial fact.

Let’s also list out the numbers 1 through 9 and examine their “parity” (i.e., their even-ness or odd-ness). There are five odd numbers (1, 3, 5, 7, 9) and four even numbers (2, 4, 6, 8).

Notice that each row and column in the 3x3 square is a sum formed from three addends, and that they must sum to 15 by Lemma 2. So how to we construct an odd number from summing three numbers? There are only two possible ways: all three numbers must be odd, or there must be two even numbers and one odd number (any other combination sums to an even number). As an exercise to the reader, see if you can prove this fact following from the mathematical definitions of “even” and “odd”.

The above gives us:

Lemma 3. In any solution, a given row or column must have exactly zero or two even numbers. (!!!!!!!!)

Surprisingly, this constraint is enough to create our algorithm.

Algorithm. How to generate a 3x3 semi-magic square from the numbers 1-9.

Step 1. Arbitrarily pick an even number (2, 4, 6, 8) and place it into the 3x3 square. It will look something like this:

Step 2. We have three more even numbers to insert. Because we know from Lemma 3 that if there is an even number in a row or column, there must be exactly one more even number in that row or column, we must insert one even number into that row or column. This looks something like

And again we apply Lemma 3 which forces us to insert the last even number (6) in a fixed location:

Step 3. We use simple algebra to complete the remainder of the square.

We can easily solve \(a = 15 - 6 - 2 = 7\) and similarly for \(b\), \(c\), and \(e\). Once we have those, it is easy to solve for \(d\).

Now, we have a semi-magic square: every row and column sums to 15 (we haven’t checked the diagonals, and they don’t have to work out).

Okay, we have an algorithm, but how do we know if placing even numbers in this way always produces a valid solution, without leading to a contradiction? How do we know if our solution is exhautive? Indeed, we will show that not all placements of even numbers into an inscribed rectangle lead to a valid solution, and demonstrate which ones are valid.

Lemma 4. Starting from any valid square, swapping two rows, swapping two columns, or transposing the square (flipping the square along a diagonal) gives another valid square.

Proof. Swapping two rows leaves the contents of every column unchanged, so the column sums are unchanged, and the row sums are the same numbers in a different order. The same goes for swapping two columns. Transposing just exchanges the roles of rows and columns. In every case, the six sums are still all 15.

■

By Lemma 3, the four even numbers must sit at the corners of a “rectangle”: two rows by two columns. Using Lemma 4, we can swap that rectangle into the top-left corner, and swap the 2 into the very top-left cell. That leaves 3! = 6 ways to place 4, 6, and 8 around it. Transposing pairs these up, so we only need to look at three representatives (the other three are their transposes):

Only type (A) is valid (to verify this, try completing all of the squares yourself and finding a contradiction in B and C). Therefore, the configuration

is the only valid configuration for the even numbers in a solution, up to swapping rows, swapping columns, and transposing.

This is a lot of words to say that to construct a solution, you start by placing the 2, 4, 6, and 8 as in configuration (A). Fill in the rest of the values. Then, you can swap rows, swap columns, and transpose solutions in order to get different configurations.

There are 3! = 6 permutations for rows, 6 permutations for columns, and 2 choices for transposition (transpose or not), leading to a grand total of \(6 \cdot 6 \cdot 2 = 72\) possible variations that can be generated from configuration (A), which covers all possible solutions.

I’ve added an interactive demo below for you to try out. Can you create your own magic square using the algorithm we’ve discussed?