Flipping Colors


image from book

The well-known knight’s tour problem is the challenge of placing a knight at a starting position on a chessboard and having it visit every square on the board exactly once. You can look up the knight’s tour problem on the Web to get inspiration for the much harder puzzle I’m going to ask you to do. In fact, you may decide this problem is not even possible.

This puzzle also concerns a knight, but we are going to suppose that each knight move consists of traveling two squares vertically and one square horizontally or two horizontally and then one vertically. Each move of the knight flips the colors of the three squares along the L-shaped path chosen, (not including the starting square, but including the landing square). The problem is to place the knight at an initial square of your choice, then move the knight through a series of L-shaped moves in such a way that the color of each square on the board is the reverse of the color before the knight began its journey. Assume that when you place the knight on a square to start, you flip the color of that square first.

Note that the knight may flip the color of a square more than once but must ultimately flip it an odd number of times.

  1. Can the knight flip the color of every square an odd number of times? If so, in how few moves?




Puzzles for Programmers and Pros
Puzzles for Programmers and Pros
ISBN: 0470121688
EAN: 2147483647
Year: 2007
Pages: 81
Authors: Dennis Shasha

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net