Algorithmic problem solving is a very useful skill to develop. Once such source you can learn and practice these skills is [1]. Allow me to illustrate with an example with puzzle #29, p. 39 from [1]:
Magic Squares
A magic square of order 3 is a 3×3 table filled with nine distinct integers from 1 – 9 so that the sum of the numbers in each row, column, and corner-to-corner diagonals is the same. Find all the magic squares of order 3.
According to the tutorial on p. 4 of [1], solving this problem is not difficult if we can prove that the common sum must be 15 and that 5 must be placed at the center square. We should start with these two hints and see where that knowledge takes us.
1. What should be the common sum? We have nine distinct integers: 1, 2, 3, …, 9, of which, each sum is a combination of three of those distinct integers. The sum of the digits 1 to 9, i.e. 1 + 2 + 3 + … + 9 = 45. Since we are only using three of the digits to form our sum for each row, column, and the diagonals, we divide 45 by 3: 45/3 = 15. Hence the common sum of any of the three squares — rows, columns, and diagonals — must be 15 because the total sum of all nine digits in the magic square will be 45.
2. Which integer should occupy the center square to get an optimal sum of 15 using the remaining integers?
Start with 9: if 9 occupied the center square, then an 8 will have to occupy any one of the eight remaining boxes. The sum of 8 + 9 = 17 and 17 > 15 so that won’t work. The same problem occurs if 8 occupies the center square because a 9 must occupy one of the remaining boxes adjacent to the 8.
Let x, y, and z be any one of the distinct integers in the set of consecutive integers 1 through 9. We need x + y + z = 15. Observe that x+y = 15 – z, x+z = 15 – y, and y+z = 15 – x. Since addition is commutative, x+y = y+x, x+z = z+x, and y+z = z+y. Hence, x+y < 15, x+z < 15, and y+z < 15. Since 9 cannot occupy the center, that means 9 will occupy any of the remaining squares, which means x+9 < 15* for all integers in the set of consecutive integers from 1 to 8. The first such integer to satisfy this condition is 5, i.e. 5+9 = 14 < 15. Hence, 5 must occupy the center square.
Given our new constraint, we know that 1+5+9 = 15:
What about the diagonals? Say we had the arrangement on the left. Take the rows containing the 1: x+y+1 = 15. The only remaining digits to satisfy the equation have to be 6 and 8, i.e. 6+8+1 = 15. Note that the 6 or the 8 would wind up in the same row as the 9. In either case, 8+9 = 17 > 15 and 6+9 = 15 leaving the remaining square unfillable. Given the symmetric nature of squares, we can reason that none of the diagonal 1,5,9 combinations will work. Given our further constraint, this reduces the possible partially filled squares to one of the four above, which I have labeled (a), (b), (c), and (d).
In the case of (a): for the row containing the 1, our only options are the digits 6 and 8 to make the 15. These can be placed in either combination:
The remaining digits can then be uniquely positioned to create our magic square.
For case (b), given the symmetric properties of squares, we can obtain our solutions by swapping the top and bottom rows from our solutions to case (a):
Case (c) can be constructed in a similar fashion to case (a):
And again using the symmetry of squres, we can take the case (c) solutions by swapping the first and third columns to obtain a solution for case (d):
for a total of 8 magic squares of order 3!
Q.E.D
What I learned by solving the magic square puzzle:
To exhaustively search all possible 3×3 tables by placing a 1 in one of the possible nine locations, a 2 in any of the possible eight locations remaining, a 3 in any of the possible 7 locations left, and so on, means the total possible combinations would be:
9! = 9x8x7x…x1 = 362,880
ways to arrange the 9 numbers in a 3×3 table. That is an undaunting task to generate all 362,880 tables checking if the result of our arrangements yields a magic square. Considering that we just learned there are only 8 such squares of order 3, that is a lot of wasted work.
In order to improve our exhaustive search, we tried constraining our problem to help reduce the search space. One such discovery was the invariant of the common sum of 15. This invariant was helpful in allowing us to smartly construct magic squares that fit the constraint.
We further reduced our search space by discovering another invariant: that 5 must always occupy the center square. Given these two invariant properties, we were able to quickly and smartly reason all the possible magic squares of order 3 without having to waste our time constructing and examining the 362,872 squares that did not fit the constraints.
Bottom line: Invariants are incredibly useful in problem solving and programming. Finding an invariant can reduce intractable exhaustive search problems and ensure that our solutions are correct. The recognition of invariants is an important problem solving skill. Possibly the most important.
* Note that 9 could be x, y, or z but the results from any of the inequality relationships will be the same. Therefore, we will show the x+9 < 15 relationship but our “proof” will hold with any of the three inequality relationships.
References
[1] Algorithmic Puzzles, Anany Levitin, Maria Levitin, Oxford University Press, Inc., New York, NY, 2011
Eric Hokanson 