Figure 1. The unsolved Snaky.
Ed Pegg Jr., August 17, 2006
In 1976, Frank Harary introduced a new form of tic-tac-toe. As usual, players alternate X's and O's. For a particular shape and board, player X attempts to make the shape, while player O prevents the shape. For square boards and polyominoes, all shapes have been solved except one -- the Snaky, illustrated below. For thirty years, the Snaky has remained unsolved. When I last saw Dr. Harary in 2004, I asked him about the Snaky. "Have you solved it?" he asked me, in his wonderful professorial voice. "If you've solved it, I'll put $50 in your hands right now." I had to tell him that I hadn't solved it. But perhaps a reader can solve it -- on an 8x8 board, can either X or O force a win? X wins by making a Snaky in any orientation, while O wins by reaching a filled board with no Snaky.
Figure 1. The unsolved Snaky.
A feature of the Snaky is that it is a strip polyform. Two squares (the head and tail) each border exactly one square, the other squares each border exactly two squares. A simple, non-crossing path connects the head and tail. With 8 squares, there are exactly 64 possible strip-octominoes. Patrick Hamlyn demonstrates that two 16x16 can be made with these pieces. Two puzzles might be possible with these grids. First, filling both with the same set of letters, so that each snake spells out an 8-letter word. Second, dividing each grid into 4 8x8 sudoku puzzles.
Figure 2. Patrick Hamlyn's solution for the 64 octastrips in 2 squares.
A few months ago, Games magazine editor Francis Heaney made a snake sudoku as a joke on his blog. This spiralled out of control, and is now an official movie tie-in: Snakes on a Sudoku. Bob Harris is perhaps the master of irregular sudoku, for his law of leftovers technique and his minimal clue compositions, some of which are in his book Squiggly Sudoku. Here are two examples of sudoku made with snaky regions built especially for this column by Bob Harris. Each row, column, and snake has the letters LOP SNAKE, and are completely solvable with simple logic.
Figure 3. Two snaky Sudoku by Bob Harris. (More.)
What else can be done with strip polyominoes and the sudoku idea? If a snake is on a toroidal grid, where the top-bottom and left-right edges are continuous, making a torus, what are the possible borders for the squares? Assuming the torus is completely covered with snakes, there are 10 different ways a square can be bordered when covered with strip polyforms. A 10x10 torus can be covered with snakes such that all the squares in each row and column use all ten bordering methods. The first image below gives a sample of this. Can you deduce the borders between the snakes in the second image? I'll call this new puzzle type Edge Wrangler Sudoku.
Figure 4. The 10 possible component squares of a strip polyform is each row and column, by Ed Pegg Jr.
Another snaky Sudoku is what I call circle and arrow Sudoku. Each circle is the sum of the numbers on the arrow (For an example, see the solution to the first puzzle). I've only found this variety of Sudoku in Nanpure Fan, published by www.puzzler.ne.jp. Nanpure translates to "number place", the english name by Howard Garns and Dell (1978). I like Nanpure Fan more than other japanese sudoku magazines: Nanpure Plaza, Nanpure Magazine, Nanpure Mate, Nanpure Kan, Nanpure Land, Cho Nanmon Nanpure, Nanpure Hiroba, Nanpure Lotto, Nanpure Jack, Nanpure Taro, and Nanpure Express. Only Nikoli can use the Sudoku name in Japan.
Figure 5. Circle and Arrow Sudoku. From Nanpure Fan. (Solution to first puzzle.)
Serhiy Grabarchuk considered a snake as linked, non-crossing unit paths, with turns in increments of 30 degrees. What is the longest snake that can fit in a 2x2 or 2x3 rectangle? Erich Friedman expanded the problem in his Math Magic column. These two particular sizes were first solved by Susan Hoover and Dave Langers. The next Al Zimmermann Programming Contest will look for big snakes in larger areas.
Figure 6. Serhiy Grabarchuk's Angle Snake. Solutions by Susan Hoover
and Dave Langers.
Puzzleland Park by Sam Loyd elaborately uses the concept of noncrossing snaky paths. In the gated park, each of eight houses has a private gate directly opposite the home's main door. Connecting each house and gate is windy path, and none of the 8 paths cross or touch each other. Can you connect each house with its gate? (Answer)
Figure 7. Sam Loyd's Puzzleland Park. Connect gates to like-colored houses, without crossing paths. Answer.
The Puzzleland Park idea has been popularized by Nikoli in their Number Link puzzles. Number Link involves the seemingly simple task of connecting 1 to 1, 2 to 2, 3 to 3, and so on, without any paths crossing, and with a path segment in every square. Also, every square must be used. In other words, a grid must be completely divided into snakes with matching numbers on the heads and tails. (Tim Halbert also has an excellent selection of number link puzzles.)
Figure 8. Number Link puzzles by Nikoli. All from Penpa Mix 2.
Slither Link first appeared in Puzzle Communication Nikoli #26 (June 1989), and was originally composed by Nob Kanamoto, Yada Reenin, and Yuki Todoroki. In Slither Link (also called Fences or Loop the Loop) the dots are connected to form a single closed loop, like a snake biting its tail. Each number represents the number of path segments bordering that square. One part of the solving logic is that a horizontal or vertical line not passing through the dots will pass through an even number of segments. Slither Link and Spiral Galaxies (another Nikoli creation) are both NP-complete. Erich's Puzzle Palace lists other path puzzles.
Figure 9. Slither Link puzzles by Nikoli. From the Puzzle Cyclopedia.
Hamiltonian paths in a graph
The Snake puzzle
Snakes in DROD
Frank Harary and Heiko Harborth, "Extremal Animals." in Journal of Combinatorics, Information, and System Sciences, 1, 1976, pages 1-8.
Heiko Harborth and Markus Seemann, Snaky is a Paving Winner, http://citeseer.ifi.unizh.ch/303663.html
Comments are welcome. Please send comments to Ed Pegg Jr. at ed@mathpuzzle.com.
Ed Pegg Jr. is the webmaster of mathpuzzle.com. He works at Wolfram Research, Inc. as an associate editor of MathWorld. He is also a math consultant for the TV show Numb3rs.
