Click here to Skip to main content
Click here to Skip to main content

Tagged as

Knight's Tour

, 12 Feb 2014 CPOL
Rate this:
Please Sign up or sign in to vote.
JavaScript implementation of Knight's tour problem
Solution when started on e4.

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.
    Possible moves and the path.
  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
    All possible moves of knight place in the center of chessboard.

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.

Partial Solution when started on f1
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.

All possible moves of knight place in the center of chessboard.
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 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.

Solution when started on e4.jpg

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.

References

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

JS00001
Software Developer (Senior)
United States United States
No Biography provided

Comments and Discussions

 
-- There are no messages in this forum --
| Advertise | Privacy | Terms of Use | Mobile
Web04 | 2.8.1411023.1 | Last Updated 12 Feb 2014
Article Copyright 2014 by JS00001
Everything else Copyright © CodeProject, 1999-2014
Layout: fixed | fluid