Thursday, June 30, 2011

kixote, or knight's path puzzles

If you can make puzzles out of king's tours, why not try to do the same with knight's tours? Here is a first attempt. Remember, a knight moves this way:

So, the goal of these puzzles is to complete a "knight's tour" of the board, honoring the numbers that have already been filled in. The types of boards that you can use for a knight's tour are much more limited than those you can use for a king's tour. The two puzzles in this post are based on a 5x6 board (as in "quick chess" if you have ever played that).

First draft of "kixote" instructions: Fill in the missing numbers so that when followed in order they form a "knight's path" around the grid, where each square is visited exactly once. A knight is a chess piece that follows an L-shaped path, moving in one of these ways: (a) two steps vertically followed by one step horizontally, or (b) two steps horizontally followed by one step vertically.

Kixote Puzzle A

Kixote Puzzle B

OK, but what about the silly name "kixote"? Well, it's clear that any number puzzle has to have a three syllable name that sounds vaguely Japanese, and this one should have something to do with knights that roam around

It seems that one way to make a puzzle is to start with a problem and its solution, and then hide part of the solution. Finding the solution to the problem is now just a puzzle, since some of it is right there in front of you. In this case, the original problem is finding a knight's tour - the puzzle is generated by taking some particular solution and hiding some of it. To be a well-formed puzzle, you should only be able to obtain the original solution, not several other solutions that just match on their exposed parts. Making sure that the puzzle is well-formed either takes good puzzle-making skills, or good puzzle-checking algorithms. Right now, I have neither - please let me know if these puzzles work or not.

Update: the solutions to the puzzles in this post are here.