Knight was randomly put on chessboard. How could knight visit each square of the board only once? Knight tour is a mathematical problem. Warnsdorff found a solution to it in 1823. A Wikipedia article explains algorithm in details Warnsdorff's rule for Knight's tour.
- Based on Warnsdorff's rule, knight must move to the square with the least future possible moves. The rule is heuristic.
- Knight can move like letter "L". When knight is placed in the center of chessboard e4 it can make 8 possible moves (2-9). These moves are:
- 2. g5
- 3. g3
- 4. f2
- 5. d2
- 6. c3
- 7. c5
- 8. d6
- 9. f6
When knight is put in the corner, for example a1, it has only 2 available moves. When program calculates all possible moves for the given square, it chooses the square with minimum moves. Then it goes recursively until board is completely covered with knight's moves. One of my fellow programmers found that some initial knight positions confused the program. During debugging, I noticed in some cases when knight has 2 squares with the same number of minimum moves. Here's a failed solution where not all squares covered.
Solution to this issue could be done by temporary choosing a square and calculating a number of possible moves one level deeper. Recursive method "
GetSolution" applies Warnsdorff's rule. Each move/square is marked from global counter. 1 is starting position.
- Here's the logic on how to automate/calculate knight's moves from one square.
It can be an equation. All moves from 2 to 9 belong to a circle with a center in 1, current knight position. Circle equation is x2 + y2 = R2. As we know that each knight move was described letter "L" as well so that delta coordinates for move 2 are (2,1). Let's put move 2 into circle equation 22+12=5. In other words, radius equals to square root of 5. x-axis values are -2, -1, 1, and 2 so it is easy to calculate y values. Code shows how to do this.
var arrayX = [-2, -1, 1, 2];
var circleRadiusSquared = 5;
var yOnCircle, xOnCircle, dY;
for (var k = 0; k < arrayX.length; k++)
xOnCircle = x + arrayX[k];
dY = Math.sqrt(circleRadiusSquared - Math.pow(arrayX[k], 2));
for (var m = 1; m < 3; m++)
yOnCircle = y + Math.pow(-1, m) * dY;
Using the Code
Each HTML button represents chessboard square. Person selects cell where knight will start then clicks "Find Solution" button. All moves are represented in chess algebraic notation may be copied. "Clear the chess board" resets everything to initial state.
Points of Interest
Long, long time ago, my high school physics teacher proposed to use theory of degrees of freedom of ideal gas (see Wikipedia) To make a long story short, the result was the same as Warnsdorff's rule. Physic's model missed heuristic aspect of Warnsdorff's rule. Occam razor states that one should proceed to simpler theories until simplicity can be traded for greater explanatory power. So I chose simple Warnforff's rule over complex ideal gas model.
Update on April 14, 2017
I find the article at MathWorld that discusses graph-based approach to Knight's tour. Knight Graph is an interesting read. It mentions Warnsdorff algorithm and backtracking algorithms.