A Toy Algorithm

Toys beguile and entertain through their resemblance to some real thing. They’re play-things, yet playing with them is instructive–both for the sheer act of play and for the truths they reveal about larger, not-toy concepts.

Suppose you’ve been asked to play with a 3 x 3 grid. For your first trick, assign the numbers one through nine to it such that each number appears only once.

No problem, right?

   C1 C2 C3
R1 [1][2][3]
R2 [4][5][6]
R3 [7][8][9]

Next, with the same set of numbers, suppose that the value N of the top left corner R1C1 is provided, and that you’re now tasked with organizing the remaining digits so that all rows, columns, and diagonals all add up to the same value–call it x.

   C1 C2 C3  x
R1 [N][?][?] x
R2 [?][?][?] x
R3 [?][?][?] x
    x  x  x  x

One way to approach this is with brute force: lay the remaining digits down more or less at random, then check to see whether the sums of rows, columns, and diagonals all match up. The process repeats itself until a valid solution is found.

Here’s how it might look in a programming language like JavaScript.

function permute(N) {
  const digits = without([1, 2, 3, 4, 5, 6, 7, 8, 9], N);
  const solution = [[N]];

  for(i = 1; i < digits.length; i++) {
    solution[i][i % 3] = takeRandom(digits);
  }

  if (verify(output)) {
    return solution;
  }

  return permute();
}

Though there are 362,880 possible permutations for a methodical implementation of takeRandom to churn through (more if a less-methodical implementation repeats itself) a fast computer should get there soon enough.

Many algorithms’ lives start here, embracing clarity and ease-of-authorship while leaving performance as something of an afterthought. In the spirit of the unofficial UNIX motto[1], the algorithm works (or at least appears to); making it right is a project for another day.

An analytic shortcut

Waking up the next morning, you’re ready to take another shot. You didn’t sleep well with that puzzle rattling around in your head–it’s solved, but with the uneasy feeling that a random walk can’t possibly be an optimal solution.

Staring at the square with fresh eyes, you might notice some shortcuts. In particular, if you can calculate x before attempting to fill out the square, you might be able to takeRandom numbers that converge each row towards x as you work.

And you can! Since all three rows must each add up to x, and since you know the set of numbers contained within them, you can simply add them up:

1 + 2 + ... + 9 = 3x
             45 = 3x
             15 = x

With this knowledge, you no longer need to complete the entire square to know whether a valid solution will be possible.

const MAGIC_SUM = 15;

let rowValue = 0;
for(i = 1; i < digits.length; i++) {
  const next = takeRandom(digits);
  rowValue += next;
  if (rowValue > MAGIC_SUM) {
    break;
  } else if (i % 3 === 0) {
    rowValue = 0;
  }

  output[i][i % 3] = next;
}

The world outside the problem

Though you’ve made good progress, there’s still room to improve. Though the problem is all you’ve been given, a few little tidbits that may or may not have stuck back in elementary math class can get you even closer. Specifically, you know that:

1. 15 is an odd number
2. adding two odd numbers (or two even numbers, for that matter) will produce an even number

With this knowledge, you can also conclude that for each row, column, or diagonal to add up to 15, it must contain an odd number (1 or 3) of odd numbers.

In other words, the five odd digits (and hence the four even digits) must be distributed in a predictable, symmetric pattern:

   C1 C2 C3  15
R1 [N][O][E] 15
R2 [O][O][O] 15
R3 [E][O][E] 15
    15 15 15 15

You may also notice a nasty mistake in the problem statement: if N is an odd number, it won’t be possible to construct a valid solution! The initial algorithm’s performance would rarely have been fast, but without accounting for this error condition, it would (not obviously) have run indefinitely.

Many problems don’t have easy solutions. Or fast solutions. Or even any solution at all.

If you caught the edge case, though, we’re now prepared to fill in the odd digits in the square. Once again, we can produce a system of equations that (while not fully describing the problem) can help us get close.

R1C2 + R2C2 + R3C2 = R2C1 + R2C2 + R3C1
       R1C2 + R3C2 = R2C1 - R2C3

From the pool of available digits and the knowledge that large and small digits must balance, we can infer that 5 was the digit canceled out from the center of the square (R2C2), leaving the pairs { 1, 9 } and { 3, 7 } behind. These we can rotate or flip the square (addition is commutative, right?) but the shape of the solution remains the same.

   C1 C2 C3  15
R1 [N][7][E] 15
R2 [1][5][9] 15
R3 [E][3][E] 15
    15 15 15 15

All that’s left is to find the even numbers that can satisy the remaining constraints and distribute them around the square.

(from R1): 15 - 7 =  8 = N + R1C3
(from C1): 15 - 1 = 14 = N + R3C1
(from R3): 15 - 3 = 12 = R3C1 + R3C3
(from C3): 15 - 9 =  6 = R1C3 + R3C3

The iterative version of this solution is efficient: assign the odd digits (within a small set of possibilities) and solve a system of four equations to fill in the rest. It’s also far less obvious than the naïve first pass. It’s a special case that relies on both close observation and outside knowledge; applying them brings you within a hair’s breadth of the solution itself (in fact, there’s a still-more efficient solution that comes even closer. See it?)

As the one, so the many

Outside of logic, the initial constraints of a problem are rarely the only information available. Whether it’s an algorithm, a decision, or any sort of head-scratching situation, close observation and a liberal dose of outside knowledge have a way of turning intractable problems into something easier to solve.

The trouble is that the solution is no longer self-contained. To understand it, a reader happening must now follow its author through whatever mental hoops went into its making. Observations must be repeated. Knowledge must be found. Any cleverness unavailable a priori must be reinvented before it can be read. It’s an elegant moment when clarity and cleverness share the same table; far more often, reality keeps them apart.