I was challenged to find a Knight's Tour of a 5x5 board by my daughter the other day. This didn't have anything to do with her interest in Chess, but was required to make progress in a puzzle game she was playing. I was pleased when I found the solution on my second attempt.
It then got a bit harder, when a few puzzles later, the same task was required on a 6x6 board. I must confess that I gave up after 2 unsuccessful attempts (after trying Warndorff's Rule). However my daughter did solve it shortly after, so there was no harm done. When she reached the 8x8 task (7x7 was skipped), I did the very sensible thing, and told her to look up the answer.
We did think at first that the reason they skipped 7x7 was that there were no possible solutions, but it turns out there are in fact 165,575,218,320 different solutions! What there is no solution for on a 7x7 board, is a closed tour, where the final square is a knights move away from the start square (making the path a closed circuit).
2 comments:
Re the 7x7 board, I would think there is never a closed tour on an odd number of squares because the Knight always moves to the opposite colour, so it starts and finishes on the same colour which can't be a knight move apart. (This might be less obvious when just using a grid without colouring the squares.)
Yes, that is part of the reasoning. According to the Wikipedia page, any rectangular board (not just square), does not have a closed tour if both sides have odd number lengths, or if 1 side is 1,2 or 4 squares in length, or the boards are either 3x4, 3x6 or 3x8.
Post a Comment