Again, I wish I knew a bit more about coding than I actually do. Jason brought home a math brain teaser the other day that he and his grandmother got stumped on:

Arrange the numbers from 1 to 16 in a four by four square so that each row and each column and the two main diagonals add up to 34.

(note: as I type this, I have the brainflash to feed that quote into Google. I think I just found the answer there – would’ve saved me a few hours today. I’m not going to be able to sleep if I don’t figure this out for myself, though.) I spent some time with Excel this afternoon, setting up a grid that showed the row, column, and diagonal sums and then started arranging the numbers. I’ve managed to fit everything but the diagonals, and I’m getting a feel for the rules of movement to switch numbers around without breaking what I’ve got so far.

Part of me wants to make this a linear programming problem, set up a matrix of coefficients, and solve it. That was one of the coolest things I learned in my Materials & Energy Balance class, the first course in chemical engineering. By setting this up as a system of equations, if you have enough (non-redundant) equations to satisfy the degree of freedom, there is a matrix manipulation algorithm that will nicely resolve all the equations into the solution. I’ve been trying, but I can’t come up with enough equations. I have sixteen variables (one for each grid square), so I need sixteen equations, but I can’t pick them out to get a solvable matrix.

I moved on a little while ago to think about a computational brute-force. Let the computer churn overnight on all the 20,922,789,888,000 variations on this square and check them while I blissfully sleep. My problem with that, and the reason I wish I had more of a computer science background, is that I’m not sure how to represent the matrix in a sensible form. The ugly way would be a nest of sixteen for i = 1 to 16: loops, with checks at each level of the nest to ensure that no number was used twice. This would be hideous to write and, I suspect, extremely inefficient.

Rather than represent this as a matrix, what it really looks like is a sorting problem. Instead of a matrix, treat the grid as a sixteen-element array. Let the first row be positions 1 through 4, the next row positions 5 through 8, and so on. Based on what I tried with the linear programming above, I can write a function to evaluate the matrix by adding up the values at certain positions and make sure they add up to 34. Problem is, I don’t know nearly enough about sorting algorithms to readily apply them here. Essentially, a sorting function would be able to evaluate two items in the list and see if they are in the proper place (the first is “higher” than the second) or if they should be swapped around (the second is “higher” than the first) and swap them. Unfortunately, in the evaluation function for this problem, I don’t know how to determine which is a better fit and which is not, so which elements should I swap?

See, this is what keeps me up at 1:17 in the morning. Welcome to my world.

UPDATE: Answer is in the comments. Thanks, Dad!