The Math
This section contains a few thoughts about the math behind the puzzle.
The Number of Combinations
Think about this sequence:
- When you start out, the first cell you fill can have any one of nine digits.
- The second cell you fill can have any one of the remaining eight digits.
- The third cell you fill can have any one of the remaining seven digits.
- And so on...
- When you get to the last cell, there’s only one digit remaining, so it’s not much of a choice.
Do you see the pattern?
The total number of combinations can be easily calculated:
9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1
This pattern occurs frequently. Mathematicians call it a “factorial”, They even have a special notation, using an exclamation point. So they would say that the number of combinations in this puzzle is 9!, pronounced “9 factorial”.
Did you try multiplying those numbers? Go ahead, get out your calculator and do it. You’ll find that 9! is equal to 362,880. That’s a lot of combinations, so it’s not surprising that the puzzle is difficult to solve.
The Solutions
In the Solution tab, run or skip to a solution, and then try again repeatedly. You will find that the program finds four solutions.
Skip back and forth between them and examine the results. The four solutions are reflections of each other on the horizontal and vertical axes. So there is really just a single solution, flipped around the four possible different ways.
Another way of saying this is that the arrangement of the cells is symmetrical on the horizontal and vertical axes, so the solutions must have the same symmetry.
The Algorithm
Are you curious about how the program solves this puzzle?
From the discussion above, remember that we start with 9 choices for the first cell we want to fill, 8 for the second, and so on. Those choices can be diagramed as shown below in what programers call a “decision tree”. As is customary, the tree is illustrated with the “root” at the top, with multiple “branches” leading to “nodes” at each level, leading eventually to the nodes at the bottom which are called “leaves”.
Note that the diagram only shows a very small portion of the tree. The rest is left for your imagination to fill in. The full tree has 362,880 leaves — way more than we can fit on a diagram of any reasonable size. We’ve only shown the first 12 leaves. (For a larger view, click the image to open it in a new window or tab.)
Programmers describe the method used here as “walking” or “traversing” the decision tree, a process which begins at the root and proceeds systematically down every branch. Traversing the entire tree will visit every node (the decision points) and try every branch (the alternatives), proceeding all the way down to every leaf.
The order is top to bottom, and left to right. At each node we take the first branch, going all the way down to an individual leaf. Then we go back to the node one level up and try the next branch in the same way until all the possibilities at that level have been tried. Then it’s back up one more level and do the same. Do you see how this will eventually visit every leaf?
Computers are very good at repetitive work, so we can easily create a program that traverses a tree of any size. The rules are simple at each step and can easily be used to define an “algorithm” for performing the entire process.
But even for a computer, the number of possibilities to explore can be prohibitively large.
Consider our Puzzle. Each node in the tree represents a decision point, a simple choice of a digit for a cell,
based on the digits which have not yet been used. The number of nodes is the sum of the numbers on the far
right of the diagram:
9 + 72 + 504 + 3,024 + 15,120 + 60,480 + 181,440 + 362,880 + 362,880 = 986,409 nodes
Visiting a node corresponds to a “step” in the program. And traversing the entire tree requires
nearly a million steps!
All this for a relatively simple little math puzzle. Some problems we may wish to solve may have many times this number of nodes. Exhaustively examining every single one of the possibilities may require more time and processing resources than we have available. We need to find a way to make the process more efficient.
The solution is to “prune” the tree by eliminating any branches that we can determine will be fruitless in our search. In our Puzzle example, this is done by testing the requirement for multiples at each step where a choice of a digit for a particular cell completes the circle of neighbors for some other cell(s) nearby. If we contradict the requirement, there is no need to pursue this branch of the tree any further, and that branch and all its sub-branches can be safely eliminated from consideration.
Run the program slowly (or single step) in the Solution tab and watch this process in action. The program makes choices for each cell in turn until it picks a number that leads to a contradiction of the rules (one or more cells turn red). It then backs up as far as it needs to for the next choice, never trying digits in the empty cells if any one of the filled cells is red. At each step, try to imagine where you are in the decision tree.
By pruning the decision tree as it traverses it, the Puzzle program runs to completion in only 22,185 steps, compared to the 986,409 steps it would have required to examine the tree in its entirety. That is an enormous improvement. We do the entire job with only 2.25% of the effort.
Applying this kind of improvement to a more difficult problem can make the difference between totally impractical and entirely feasible.
