On supporting science journalism
If you're enjoying this article, consider supporting our award-winning journalism by subscribing. By purchasing a subscription you are helping to ensure the future of impactful stories about the discoveries and ideas shaping our world today.
The well-known knight's tour problem is the challenge of placing a chess-piece knight at a starting position on a chessboard and having it visit every square on the board exactly once. (You will recall that in chess, a knight performs L-shaped moves that go two squares in one direction and then one at right angles to it. Recall also that it doesn¿t matter if there are pieces on any of those intermediate squares. The knight effectively jumps over them.) You can look up the knight's tour problem as an aid to the much harder puzzle I'm going to ask you to do. In fact, you may decide my problem is not even possible.
This puzzle also concerns a knight, but unlike in chess, we are going to suppose that the knight walks (or trots, if you wish) two squares vertically and then one horizontally (or, if you prefer, two horizontally and one vertically). No jumping for these horses. This walk flips the colors of all the squares along that L-shaped path (not including the starting square, but including the final square). The problem is to flip the color of all the squares on the board assuming that when you place the knight on a square to start, you flip the color of that square first.
Can it be done? If so, how fast? If not, why not?
