Problem of the Week 1161

Traceable Knights

MacPOW Home || Math Forum POWs || Search MacPOW

Solution

Several readers solved the problem posed for all n ≥ 5, including John Duncan, Michael Elgersma, John Watkins, Joseph DeVincentis.

Rob Pratt used some traveling salesman code to solve the particular case of the problem that was given. It turns out this problem was completely settled in 1972 by Mark Krusemeyer in an addendum to his PhD thesis. My solution is based on finding a certain gadget for the 4 × 3 case. Using that, one can start with certain paths for 4 × 5, 4 × 6, 4 × 7, and then add the gadget repeatedly on the left. Mathematica's FindHamiltonianCycle function (easily modified to FindHamiltonianPath) works fine here, but I am fooling around today with even better methods: thanks to Rasmus Kamper, I now have a Hamiltonian cycle finder on my computer based on cutting-edge code for the traveling salesman problem (Concorde and LKH). It is working very well.

Here is the gadget I used to solve the problem.

Three base cases

A typical large path

Elgersma's path

Pratt's path

I am preparing a paper (with Michael Dupuis), just about finished, that complete solves the harder problem:

Which knight's graphs are Hamilton-laceable?

A bipartite graph is laceable if there is a Hamiltonian path from any point in one part to any point in the other. A preprint is at stanwagon.com/public/LaceableKnightPreprint.pdf.

[Back to Problem 1161]

© Copyright 2012 Stan Wagon. Reproduced with permission.