Tuesday, June 28, 2011

Hidato, or a king's tour

I picked up a logic puzzle book on the weekend and learned of Hidato puzzles - a type of number puzzle that was developed (recently, I think) by Gyora Benedek. This appealing genre of puzzle was, according to Benedek, inspired by trying to follow the path taken by small fish as they darted through a coral reef.

In a Hidato puzzle you are given an n-celled grid where some cells contain numbers while others are left blank. Your task is to fill in the blanks so that the numbers form a the consecutive series from 1 to n. Cells are considered adjacent if they are touching edges or corners. Another way to think of the puzzle is to imagine moving along the grid while trying to fill in the numbers 1 to n in order - you are allowed to move one square at a time either horizontally, vertically, or diagonally.

Just as Sudoku are latin squares with missing values, so the Hidato are really king's tours in disguise. A chess king can move one cell in any direction, and a king's tour is a complete covering of the chessboard where each square is visited exactly once (a hamiltonian path on the king's tour graph). As with knight tours, a king's tour can be open (if the final square is not adjacent to the start) or closed (if you are one move away from the beginning when you get to the end). Below is an example of an open king's tour on standard 64 cell chess board.

A solved Hidato is a completed king's tour since it is played on a chess-like grid and the Hidato moves are precisely those which a king is allowed. Whether by accident or design, the Hidato puzzles I've seen so far are not 8x8 boards like in standard chess - I've seen 6x6, 7x7 and a variety of rectangular and odd-shaped boards.

Here are two not-too-hard Hidato-inspired king's tour puzzles (note that I am not calling them Hidato - that's a trade mark... they are "king's tour puzzles") on a 5x5 board (the solutions at the bottom of this post). These puzzles were created by first creating a king's tour and then only labeling some of the cells - hopefully enough to guarantee the uniqueness of the solution.

King's Tour Puzzle A 

King's Tour Puzzle B

You can generate king's tours using the same algorithm as used for knight's tours. You can also use the same knight-tour techniques to transform an open king's tour into a closed king's tour.  The "king's graph" is much more connected than the knight's graph, so tours are much easier to generate (and close). The interior cells have 8 neighbours, with cells at the edges and corners with 5 and 3, respectively.

If you picture the board as a graph, kings have a lot more edges to travel along than knights do.Interestingly, the sequence, 6, 20, 42, 72, 110,... (A002943) gives the number of edges in a king's graph for an n+1 by n+1 board, and this sequence shows up as a diagonal in the Ulam number spiral of a few posts back.

Here are solutions to the small king-tour puzzles above.

Puzzle A Solution

Puzzle B Solution

Update: I have put up a page that generates playable Hidato puzzles here.