## Snakes on a Plane

Ed Pegg Jr., August 14, 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 except 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.

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 best known for this form of irregular sudoku, for his valuable the 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.

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. It is possible to cover a 10x10 torus 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?

Serhiy Grabarchuk's 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.

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)

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 like numbers on the heads and tails. (Tim Halbert also has an excellent selection of number link puzzles.) As an aside, Nikoli is one force behind Brain Age, now one of the best-selling puzzle games of all time. Over 215 language-neutral puzzle types developed by Nikoli (detailed in their Puzzle Cyclopedia).

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. Other path puzzles are at Erich's Puzzle Palace.

circle and arrow Sudoku (Solution to first puzzle) I've only found this variety of Sudoku in Nanpure Fan, published by www.puzzler.ne.jp.

Hamiltonian paths in a graph

The Snake puzzle

Snakes in DROD

References:

Arthur C. Clarke, The City and the Stars, 1956.

"Extremal Animals." Frank Harary and Heiko Harborth, in
Journal of Combinatorics, Information, and System Sciences,
1, 1976, pages 1-8.

Heiko Harborth, Markus Seemann, Snaky is a Paving Winner, http://citeseer.ifi.unizh.ch/303663.html ,

Martin Gardner, "Patterns and Primes." Martin Gardner's Mathematical Games, MAA, 2005.

Jean-Charles Meyrignac, "Al Zimmermann Programming Contests: Prime Generating Polynomials Final Report." July 9, 2006. http://euler.free.fr/contest/PGPReport.htm.

Eric W. Weisstein. Bouniakowsky Conjecture, Dirichlet's Theorem, Heegner Number, Monstrous Moonshine, Prime Arithmetic Progression, Prime-Generating Polynomial, Prime Spiral, From MathWorld--A Wolfram Web Resource.

Wikipedia, "Laurence M. Klauber." http://en.wikipedia.org/wiki/Laurence_M._Klauber.

Math Games archives.