algorithmrecursionknights-tour

Knight's Tour on a 5 x 5 Board Start from any Square?


I'd just like to check my logic here...

I wrote code to solve the Knight's Tour and it works well for 8x8 boards starting the Knight at any square.

But... on a 5x5 board I show no solution possible when starting at square (0, 1).

What I tried for 5x5 starting the Knight at Row 0, Col 1:

  1. Warnsdorff's path
  2. Added Roth (tie breakers based on Euclidean distance from center).

Since those did not produce a solution I did code that is just basic recursion with backtracking to test every possible path -- also no solution found when starting a 5x5 on 1, 0.

I looked everywhere for a list of exhaustive solutions to the 5x5 board but found none.

Is it that there just is no solution for 5x5 when starting at square 0, 1?

Thank you!


Solution

  • Correct, there is no solution when you start at any of the squares adjacent to a corner square.