Figure 1. The unsolved Snaky.
Ed Pegg Jr., August 17, 2006
Two dimensional surfaces are ideal for many snake-based puzzles.
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 saw Dr. Harary in 2004, I asked him about the Snaky. "Have you solved it?" he asked me, in his warm, 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 16×16 squares 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 8×8 Sudoku puzzles.
Figure 2. Patrick Hamlyn's solution for the 64 octastrips in 2 squares.
A few months ago, former Games magazine editor Francis Heaney made a snake Sudoku as a joke on his blog. This spiraled 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 a 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.
Tough Puzzles is a self-describing magazine name, featuring many of the world's best puzzles. One puzzle type is called Serpent. A 42-foot long sea serpent is to be found somewhere in the grid. The head and tail can be seen, but the remainder lies below the surface. The serpent's path only moves horizontally or vertically between squares, and never crosses or touches itself, not even diagonally. The numbers below and to the side show the number of squares in each row or column which the serpent occupies. Can you work out it's exact position?
Figure 10. Serpent, from Tough Puzzles. Both puzzles by Hans Eendebak.
Graph Theory has many snaky problems. For example, the Icosian Game, developed by Sir William Rowan Hamilton, asked solvers to traverse the vertices of a dodecahedron. Graphs with such paths are called Hamiltonian. A graph without crossings is planar (and fits nicely on a plane). If a graph won't fit on a plane, one can try redrawing it so that it will have fewer crossings, but this aspect of graph drawing is a mostly unsolved problem. The minimal known number of crossings for the Coxeter graph is eleven. Adding crossings is likewise difficult. For example, a $1000 prize is offered for a thrackle that has more edges than vertices. The writhings of larger graphs is mostly unsolved. An example is the thickness problem: if the edges of a graph can be differently colored, how many are needed to prevent two edges from the same color crossing?
I'll close by mentioning the snakes in Deadly Rooms of Death, the best puzzle game I know. In addition to lots of snakes, DROD has a very active community of puzzlers, all who strive to make or solve clever puzzles with the elements of the game. The DROD community holds a monthly contest each month. This month, the contest is Snakes! .. to the Death! Sixty-four snakes are in a fight to the death.
Figure 11. Algorithmic jumping snakes, as imagined by DROD creator Erik Hermansen.
The funny thing is, I actually have even more puzzles fitting in the theme of snakes on a plane. But I think, for now, that's enough snakes on the plane.
Andrew Clarke, "Strip Polyforms," http://www.recmath.com/PolyPages/PolyPages/PolyX/index.htm?PolyX.htm.
James Dalgety, "The Icosian Game," July 2002. http://puzzlemuseum.com/month/picm02/200207icosian.htm.
Hans Eendebak, Tough Puzzles, Issue 260, April 2006, p. 30. http://www.puzzler.co.uk/guardian/.
David Eppstein, "Layered Graph Drawing," http://www.ics.uci.edu/~eppstein/junkyard/thickness/.
Erich Friedman, "Problem of the Month (May 2003)," http://www.stetson.edu/%7Eefriedma/mathmagic/0503.html.
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.
Sam Loyd, Cyclopedia of Puzzles, 1905, p. 61. http://www.mathpuzzle.com/loyd/cop060-061.html.
Nanpure Fan, http://www.puzzler.ne.jp/page/000268.html.
Nikoli, Penpa Mix #2, 2005, p. 36-37. https://www.nikoli.co.jp/howtoget-e.htm.
Nikoli, Puzzle Cyclopedia, 2004, p. 11. https://www.nikoli.co.jp/howtoget-e.htm.
Stephan Wehner, "Thrackle.org," December 2000, http://www.thrackle.org/.
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.
