13,138,881 members (53,813 online)
Article
alternative version

#### Stats

15.3K views
4 bookmarked
Posted 12 Feb 2014

# Knight's Tour

, 14 Apr 2017
 Rate this:
JavaScript implementation of Knight's tour problem

## 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.

## Background

1. Based on Warnsdorff's rule, knight must move to the square with the least future possible moves. The rule is heuristic.

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 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.

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 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.

```//x values and radius of circle give y value from formula y^2=R^2-x^2
var arrayX = [-2, -1, 1, 2];

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.

## 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.

History of this JavaScript program starts when "The page is best viewed in Internet Explorer 4" T-shirts were very popular. I mentioned earlier that fellow found that the program sometimes failed. So I added Object Oriented JavaScript to fix the issue. At last, I appended chess algebraic notation box and automated knight moves by using circle formula. These updates were done just before publishing in CodeProject. It was fun to debug in new browsers. Initial debugging was done with message boxes in era of Internet Explorer and Netscape competition. It works in Internet Explorer, Firefox and Chrome. It is possible to transform the implementation to interactive game, to change board size, or to put predefined obstacles/other chess pieces on the board.

### 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.

## Share

 Software Developer (Senior) United States
No Biography provided