Click here to Skip to main content
13,138,881 members (53,813 online)
Click here to Skip to main content
Add your own
alternative version

Tagged as

Stats

15.3K views
610 downloads
4 bookmarked
Posted 12 Feb 2014

Knight's Tour

, 14 Apr 2017
Rate this:
Please Sign up or sign in to vote.
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 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.

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.

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

Alex Gawkins
Software Developer (Senior)
United States United States
No Biography provided

You may also be interested in...

Comments and Discussions

 
-- There are no messages in this forum --
Permalink | Advertise | Privacy | Terms of Use | Mobile
Web01 | 2.8.170915.1 | Last Updated 14 Apr 2017
Article Copyright 2014 by Alex Gawkins
Everything else Copyright © CodeProject, 1999-2017
Layout: fixed | fluid