Number Link « The Mathematica Journal

Ed Pegg Jr

Number Link
NB CDF PDF

B E Y O N D S U D O K U

Sudoku is just one of hundreds of great puzzle types. This column presents obscure logic puzzles of various sorts and challenges the readers to solve the puzzles in two ways: by hand and with Mathematica. For the latter, solvers are invited to send their code to edp@wolfram.com. The person submitting the most elegant solution will receive a prize.

Instructions

During the 1890s, puzzler Sam Loyd wrote columns for the Brooklyn Daily Eagle. On February 28, 1897, the following puzzle appeared [1].

There are eight houses in Puzzleland Park, and the people of each house must only go out of the park by their private gate directly across, on a line with the door of their own house. Each family has a private path of their own leading to their gate between a row of trees; no paths cross any other paths; no inmates of one house ever meet any of their neighbors, so they never quarrel about which should turn out for the other in Puzzleland. Some of the paths are crooked and very funny, but as each one has a map with his particular route marked out by the landlord, who is a great puzzlist, they never get lost. Here is one of the maps, on which you are asked to trace out the paths which each family must take to get to their private gate, across the park, but directly opposite to their door; but remember, none of the paths must cross!

(The solution to this puzzle is on page 6 of the online notebook. The online notebook contains code for the Puzzleland Park layout and code for the layout of the solution.)

This puzzle type is now a regular feature of Japanese puzzle magazines under the name Number Link. The format has been refined in the last hundred years. Each puzzle follows these rules.

Connect identical numbers with a continuous path.
Paths must go through the center of a cell horizontally or vertically and never go through the same cell twice.
Paths cannot cross, branch off, or go through other numbered cells.
Every unnumbered square must contain part of a path.

Example

Here is an example of a Number Link puzzle and its solution.

Finding the solution can start with the 1 in the corner—the path must go up, then right, then up. That forces the path of the 2 above it to start going up and the path of the 4 on the right to start going right.

Puzzles

Here are four sample puzzles from Penpa Mix #2 [2]. Each has a unique solution, which can be found by hand. In the first puzzle, each of the numbers in the corners has a forced starting path. What techniques are necessary to complete a solution by hand? A more interesting question is how these can be solved programmatically.

Puzzle Source

Previous Issue’s Solution

The 10:2 column discussed Ripple Effect puzzles. Yves Papegay sent a complete solution, which is available in ripple.nb. His solution qualifies him for The Mathematica Guidebook of his choice.

Yves’ solution has two parts. First, he checks each cell of each room for the main criteria: only once, not too close, and at least once. These three criteria form what he calls a Naive filter. Surprisingly, multiple uses of the Naive filter will solve most of the Ripple Effect puzzles given in the previous column. For the remainder, he introduces code to fix all possible values in each cell with a One Step Further filter. Fixed values that then fail to give solutions with the Naive filter are then discarded as impossible.

References

[1]	S. Loyd, Sam Loyd’s Cyclopedia of 5000 Puzzles, Tricks, and Conundrums (With Answers), New York: The Lamb Publishing Company, 1914, p. 61. www.mathpuzzle.com/loyd/cop060-061.html.
[2]	Penpa Mix #2, Tokyo, Japan: NIKOLI Co., Ltd., 2005, pp. 36-37. www.nikoli.co.jp/howtoget-e.htm.
E. Pegg Jr, “Number Link,” The Mathematica Journal, 2012. dx.doi.org/10.3888/tmj.10.3-2.