## The Challenge of the Challenger Puzzle

Do an internet search on "Challenger Puzzle" and you will find descriptions and solvers for a puzzle that involves sums of integers from one to nine. Indeed, on a 4 × 4 grid where sixteen integers would fit, four are given, along with the row, column, and diagonal sums of the numbers not shown. The object of the puzzle is to discover the missing twelve numbers.

Unlike Sudoku, the digits can repeat. And unlike Sudoku, the puzzle can have multiple solutions. In fact, "There may be more than one solution" is explicitly stated below the directions, copyrighted by King Features Syndicate, Inc., that appear in my local newspaper, the Waterloo Region Record, and quoted in Table 1.

Fill each square with a number, one through nine.

 • Horizontal squares should add to totals on right.
 • Vertical squares should add to totals on bottom.
 • Diagonal squares though center should add to total in upper and lower right.

Table 1   Directions for Challenger Puzzle from the Waterloo Region Record

I have always wondered about this puzzle - there are twelve numbers to be determined by some ten equations, and the condition that the numbers are integers between one and nine. To what extent will these conditions determine the solution to the puzzle?

Well, I finally decided to look into this question, and the tool below gradually evolved. Each time the "New Puzzle" button is pressed, a new puzzle is generated. Then, if the icon below the puzzle is clicked, the number of solutions, and the actual solutions, will be printed.  The puzzle generator I wrote deliberately does not accept a user-supplied puzzle. The generator is not a solver. It was designed to test the number of distinct solutions a puzzle can have.  Obviously, I start with a 4 × 4 array of sixteen numbers between one and nine, and form the row, column, and diagonal sums. I then select the four digits to be shown, but write and solve the ten equations governing the other twelve numbers.

To see the number of solutions, and the solutions themselves, click the button below.

There are 8 solutions:

The puzzle shown above has eight solutions. I was amazed to discover that in a sequence of 500 puzzles, one puzzle had 190 solutions, and fourteen puzzles had exactly one solution. Since I started from the "answer," there are no puzzles generated that will have no solution.

The sequence of integers in Table 2 is the sorted list of the numbers of solutions found in each of the 500 trials.

 Table 2   The integers in this table represent the number of solutions per trial for 500 trials

Table 3 is a compressed frequency table. The left-hand column lists the number of puzzles (out of 500) that had the number of solutions listed in the middle column.  Thus, 21 puzzles had three solutions, 17 puzzles had nine solutions and 17 puzzles had 10 solutions, etc. The right-hand column lists the cumulative number of puzzles accounted for. Thus, the cumulative total of 58 at the end of the third row indicates the number of puzzles that had 3, 6, or 8 solutions. The cumulative total of 92 at the end of the fourth row indicates 34 more puzzles have been counted, 17 with 9 solutions, and 17 with 10 solutions.

 43, 47, 52, 60, 61, 63, 64, 72, 74, 77, 78, 79, 81, 82, 83, 86, 87, 89, 92, 96, 97, 101, 109, 111, 117, 123, 125, 131, 139, 147, 190 Table 3   The left-hand column gives the number of puzzles that had the number of solutions listed in the middle column. The right-hand column gives the cumulative number of puzzles.

Figure 1 provides a discrete histogram of the data in Table 1.

 Figure 1   Absolute frequency of the number of solutions per trial in 500 trials. The largest absolute frequency is 21; the smallest, 1. The largest number of solutions in a trial was 190; the smallest, 1.

I don't know the conditions on the original 4 × 4 array of integers in the interval  that account for the number of solutions. I suspect they might have something to do with the number of partitions of the row, column, and diagonal sums. Indeed, if such a sum were, say, 25, then there would be

 (1)

partitions using integers in the interval . The first of these partitions, namely,

 (2)

suggests why the number of partitions is so high. We need to restrict the partitions to just those containing four integers. This much shorter list is then

 (3)

Note that each of these 23 partitions is sorted, from smallest to largest integer. These integers might appear permuted in the solution to a Challenger puzzle in which 25 were a row, column, or diagonal sum. The combinatorics of this approach do not look fruitful.

The code I used to generate a puzzle appears in Table 4.

 Table 4   Code for generating random Challenger puzzle

The eight lists of four pairs at the top of the table represent valid configurations for the four numbers to be revealed. I noticed that the puzzles in my local newspaper had exactly one such number in each row, column, and diagonal. (However, on the internet, I found puzzle generators that did not adhere to this restriction.) The eight lists in Table 4 are exhaustive - they represent the only ways to satisfy the constraint stated.

One such configuration is selected at random. Then, , the full 4 × 4 array of integers in the interval , is obtained randomly, and a matrix  is constructed. This matrix contains the four displayed digits, and the remaining twelve entries are the variables .  From , the row, column, and diagonal sums can be computed, and from , these sums can be expressed as ten equations in the twelve unknowns .

Maple's solve and isolve (integer-solve) commands provide the same solution, and for the cases I examined, each solution contained not just two indeterminates, but three. A typical such solution (vector) appears in Table 5, where we have called the three indeterminates .

 Table 5   Typical solution vector whose components are

Each component of this vector must be an integer in the interval , a condition that generates 24 linear inequalities.  Maple does solve this set of inequalities, but it takes a noticeable amount of time, and the solutions themselves can contain further inequalities. For these reasons, a "brute-force" solution was adopted for vectors like the one in Table 5. All possible integers in the range  were substituted for each of , , and ; then the twelve components of the resulting vector were examined for the maximum and minimum.  If the maximum was no larger than 9, and the minimum no smaller than 1, the solution was accepted as valid. In fact, to test the validity of such solutions, the row, column, and diagonal sums were checked and found to be correct.

I imagine that a puzzle with nearly 200 solutions would be more difficult to solve that one with just one or two solutions. That would probably be because most empty squares would admit so many different integers. Table 6 contains a puzzle with some 185 solutions. The rightmost column displays, for each cell in the 4 × 4 grid, the integers that appear in at least one of the 185 solutions.

Table 6   Challenger puzzle with 185 solutions: in the center, the starting array; on the left, the "puzzle"; on the right, the possible integers in some solution of the puzzle

At first, I thought the blue cells in Table 6 were a surprise. These cells contain the displayed integers for the puzzle, and in every one of the 185 solutions, these cells contain just the single displayed integer. However, the uncolored cells are the ones corresponding to the variables , so it is only in these uncolored cells that multiple integers can appear.

The complete code for creating, displaying, and solving these Challenger puzzles is available behind the "New Puzzle" button, and the Code Edit Region icon.  Simply bring up the Context Menu on these components; for the "New Puzzle" button, select "Component Properties" and click on the Edit button; for the Code Edit Region, select "Expand Code Edit Region."

﻿