What is a crossnumber puzzle?

You can contact Dr. Rainer Typke, the author of this web site, by e-mail:

Copyrights for all puzzles are held by their authors.

Would you like to print some puzzles by the user "rt" in your newspaper or other publication? With a premium subscription, you can get access to high-quality PDF files of the grids and solutions. Please contact Rainer Typke (contact information: see above) for more information.

Prof. William Sit of CUNY wrote a very interesting article about crossnumber puzzles that also mentions this website and the types of number puzzles one can solve with it. I quote from this article:

"Advanced Algebraic with Finite-Matching. The crossnumber puzzles by Rainer Typke have related clues as well as independent clues, but even if you are an experienced solver, the clues do not show any obvious starting points (and perhaps there are none), making them both harder to construct and to solve. The clues make use of powers (squares and cubes), primes, perfect numbers, Fibonacci numbers, palindromes, reversals, sums and products of digits, simple arithmetic to relate answers, logical operators and inequalities. Thus they combine every type of clues we have examined so far, and a descriptive label for them may be advanced algebraic with finite-matching, or perhaps to honor their author, simply refer them as Typke puzzles.

...

A systematic solution technique to solve Typke puzzles was developed and implemented by Typke in the form of a Crossnumber Solver. According to Typke, the program was first developed in 1992, when he presented it in the German science competition Jugend forscht. After some improvement, the program Programm zum Lösen von Kreuzzahlrätseln (Program for Solving Crossnumber Puzzles), won second place in this nationwide competition in 1994 and also received the special Federal Chancellor of Germany Prize. The algorithm has remained the same since, and around 2001–2002, Typke rewrote it into a web-based program.

Roughly speaking the algorithm goes as follows. The solver initializes and maintains a list of all possible digits for each blank cell. These lists are then trimmed by repeatedly passing through the clues in the order they are entered. For example, this may use first all the across-clues in order, followed by all the down-clues in order; but a more sophisticated order may be also used to help the program, such as one based on the dependency tree(s) for really huge puzzles. In this traversal through the clues, the program considers each clue by first calculating how much work it will be to evaluate (or enumerate all possible solutions of) a clue before it actually uses it. If this effort is above a user-defined threshold (which Typke called "patience"), the clue is skipped, but it will be reconsidered once all other clues have been considered. By then, more information on the answers referenced by the clue in question may be available, and that may push the effort below the threshold. This modified traversal is iterated until either every list has been trimmed down to the unique correct digit, or every list remains unchanged after a new iteration. If no list can be further reduced and some list contains more than one possibility (a deadlock situation), then one of the possibilities in a selected cell is assumed and the process of elimination repeats.

The selection strategy needs to be carefully studied, both in terms of the potential benefit of a choice if it succeeds in breaking the deadlock, and in terms of the efficiency to do backtracking. Just using a cell with very few remaining digits is generally a bad idea since there are easily constructed examples where this will simply multiply the remaining time with the number of possible digits left in the list associated to the cell, without breaking the deadlock. Typke’s algorithm spends a considerable effort into picking a good cell: in every cell where there is more than one digit left, it picks one digit and then evaluates all clues until there is a new deadlock (sort of "look-ahead"). Then it compares the reduction achieved in the number of possibilities before and after picking this digit. This is done for every cell and eventually the cell and digit that lead to the largest reduction is selected. This method is a compromise that trades efficiency and a good step with a perhaps inefficient but better step, and avoids the likelihood that a selection would be just a waste of time. When the total number of possibilities is strictly decreasing after each selection, the algorithm is guaranteed to terminate. Proof of termination is one of the most important aspects in the design of any algorithm.

At any time during the solution process, if a solution or an inconsistency is found, a new possibility in this selected cell will be assumed. In this way, all solutions (if any at all) can be found.

The critical routines to support Typke’s algorithm are the elimination algorithms for each type of clue: translating the clue into actions on the lists. For simple independent clues, this is straightforward since one can compute the unique answer. For finite-matching clues (such as primes, squares, cubes, Fibonacci numbers, or perfect numbers) one can generate the set of all possible answers within range and then obtain the restrictions for the list of each digit using pattern matching. For a palindrome or reversal clue, one can use a set-intersection computation to update the lists for all the cells that form the palindrome. The updating algorithm for algebraic clues is probably the hardest, but restrictions to the least or the most significant digit not yet known are often possible. The main algorithm can allow certain heuristics such as delaying an update until the next iteration if it is too complicated, and choosing when it is advantageous to simply start trial and error if the size of some list goes below a certain threshold.

To a certain extent, Typke’s algorithm can actually be applied manually, at least for reasonably sized puzzles. For larger puzzles, say with size larger than 9 × 9, the procedure quickly becomes tedious. However, it is possible to improve the algorithm by only updating the lists for those cells that are cross-referenced by a cell whose list has recently been changed. Thus, the goal in a manual solution process is to find the next cell(s) whose digit(s) can be uniquely determined, and then update all lists corresponding to cells that either cross-reference, or are cross-referenced by, the new found digit(s). Note that in a well-designed puzzle, the author of the puzzle should

ensure that there is at least one such path to the complete solution. I used this to manually solve many of the puzzles mentioned in Section 2 and the experience reminds me of the diagram-chasing technique in proving large commutative diagrams in homological algebra!

The use of computer programs to help solve crossnumber puzzles may be controversial, but unavoidable. To give you just a taste of what a computer can do in a flash, consider a simple clue for a 4-digit number: a Fibonacci number. Typke’s Crossnumber Solver will immediately narrow the digits a, b, c, d (a being the most significant digit) to a ∈ { 1, 2, 4, 6 }, b ∈ { 1, 5, 7 }, c ∈ { 6, 8, 9 }, and d ∈ { 1, 4, 5, 7 }. As we shall see, computer programs are often used to construct advanced crossnumber puzzles. It is only fair that solvers use computers, too. As a matter of fact, writing your own programs, even to solve for just one clue in a puzzle, can be a rewarding experience in mathematics and in mastering the computer language or software used.

Now, it is usually not possible to solve a crossnumber puzzle directly by entering the inter-relationships as equations with the answers to clues as unknowns into a computer algebra system such as Mathematica or Maple. First, the equations are constrained diophantine equations (the solutions are positive integers within a given range). Without a specially designed package, in general, these off-the-shelf systems will not be able to provide much additional information other than returning the same set of equations, perhaps with some trivial rearrangements of the variables. Second, the equations obtained from the clues are but one aspect of the puzzle. The layout of the grid and locations of the crossed cells provide critical information, too. To use this approach, one would have to treat the digit in each blank cell rather than the answer for each clue as an unknown. It is not easy to break a clue, say of multiplicative type y = ax, into clues for the digits of x and y. Finally, the finite-matching clues are also difficult to translate into equations. In my opinion, if one tries to carry this out, one would invariably be led to an algorithm similar to Typke’s described above.

A more formal analysis of Typke’s algorithm will lead us into constraint satisfaction problems, an active area of computer science research. ..."

The complete article is available for download on William Sit's web page.