Knight's Tour - A JavaScript Implementation of Knight's Tour Problem

• Download demo project - 118 KB

Introduction

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. In two words, knight must move to a square where it has least amount of possible moves. And if 2 squares have the same amount, the program does checking on 1 level next. This least amount of possible moves can be called degree of freedom that comes from theory of degrees of freedom of ideal gas (see Wikipedia).

Background

1. First moves based on Warnsdorff's rule.

   

2. 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 are covered.

   

   Solution to this issue could be got by temporarily 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 the starting position.

3. 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 x² + y² = R². 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 2²+1²=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:

   JavaScript

   //x values and radius of circle give y value from formula y^2=R^2-x^2
   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;
   
           //check for out of the board horizontal position
   
           //check for out of the board vertical position
   
           //check whether square visited before
   
           //do other logic here.
       }
   }
   

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.

History

It was first published in GeoCities (Yahoo) then Yahoo shut down GeoCities and I published this article on CodeProject.

References

• Warnsdorff's rule for Knight's tour
• Degrees of freedom