Problem of the Week 1161

Traceable Knights

MacPoW Home ||  Forum PoWs ||  Teachers' Place ||  Student Center ||  Search MacPoW

Consider a 4×100 chessboard. Show that there is an open knight's tour (also called a Hamiltonian path) from some white square to some black square. That is, find a sequence of knight's moves that lands on each square exactly once.

If you solve this case, you will no doubt have solved the general 4×n case (the answer is positive so long as n ≥ 5). I solved this and also the 3×n case; together with known results about 5×n or larger, this completely settles the problem of which knight's graphs are "traceable": a graph is traceable if it has a Hamiltonian path.

Note that there is no Hamiltonian cycle for knights on a 4×n board.

As I was working on the problem, I asked it of John Watkins (Colorado College), and within a short time he found (by hand I believe) the solution for the full 4-case as well.

© Copyright 2012 Stan Wagon. Reproduced with permission.

[View the solution]