The Algorithm Are you curious about how the program solves this puzzle? From the discussion on the previous page, 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. (Expand the size of this window to see more detail.) 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.