Package org.jgrapht.demo

Class WarnsdorffRuleKnightTourHeuristic

  • public class WarnsdorffRuleKnightTourHeuristic
extends Object
    Implementation of <a href = "https://en.wikipedia.org/wiki/Knight%27s_tour#Warnsdorf's_rule">Warnsdorff's rule</a> - heuristic for finding a knight's tour on chessboards. A knight's tour is a sequence of moves of a knight on a chessboard such that the knight visits every square only once. If the knight ends on a square that is one knight's move from the beginning square (so that it could tour the board again immediately, following the same path), the tour is closed, otherwise it is open. The knight's tour problem is the mathematical problem of finding a knight's tour. Description of the Warnsdorff's rule: set a start cell. Always proceed to the cell that have the fewest onward moves. In case of a tie(i.e. there exist more than one possible choice for the next cell) go to the cell with largest Euclidean distance from the center of the board. This implementation also allows you to find a structured knight's tour. Knight's tour on board of size $n \times m$ is called structured if it contains the following $8$ UNDIRECTED moves: 1). $(1, 0) \to (0, 2)$ - denoted as $1$ on the picture below. 2). $(2, 0) \to (0, 1)$ - denoted as $2$ on the picture below. 3). $(n - 3, 0) \to (n - 1, 1)$ - denoted as $3$ on the picture below. 4). $(n - 2, 0) \to (n - 1, 2)$ - denoted as $4$ on the picture below. 5). $(0, m - 3) \to (1, m - 1)$ - denoted as $5$ on the picture below. 6). $(0, m - 2) \to (2, m - 1)$ - denoted as $6$ on the picture below. 7). $(n - 3, m - 1) \to (n - 1, m - 2)$ - denoted as $7$ on the picture below. 8). $(n - 2, m - 1) \to (n - 1, m - 3)$ - denoted as $8$ on the picture below. ######################################### #*12*********************************34*# #2*************************************3# #1*************************************4# #***************************************# #***************************************# #***************************************# #***************************************# #***************************************# #***************************************# #***************************************# #***************************************# #***************************************# #***************************************# #***************************************# #6*************************************8# #5*************************************7# #*65*********************************78*# ######################################### If you are confused with the formal definition of the structured knight's tour please refer to illustration on the page $3$ of the paper "An efficient algorithm for the Knight’s tour problem " by Ian Parberry. One more feature of this implementation is that it provides an option to return a shifted knight's tour, where all cell's coordinates are shifted by some values. Basically it is the same as knight's tour of some piece of the board.

    • Constructor Detail

      • WarnsdorffRuleKnightTourHeuristic

        public WarnsdorffRuleKnightTourHeuristic​(int n)
        Constructor.
        Parameters:
        n - width and height of the board.

      • WarnsdorffRuleKnightTourHeuristic

        public WarnsdorffRuleKnightTourHeuristic​(int n,
                                         int m)
        Constructor.
        Parameters:
        n - width of the board.
        m - height of the board.

    • Method Detail

      • getTour

        public org.jgrapht.demo.KnightTour getTour​(org.jgrapht.demo.TourType type,
                                           boolean structured,
                                           int shiftX,
                                           int shiftY)
        Generates a knight's tour that satisfies the input parameters. Warnsdorff's rule heuristic is an example of a greedy method, which we use to select the next cell to move, and thus may fail to find a tour. However, another greedy heuristic is used to prevent failing: in case of a tie we will select a cell with the largest euclidean distance from the center of the board. Such combination of greedy methods significantly increases our chances to find a tour.
        Parameters:
        type - of the tour.
        structured - true if we want the tour to be structured, otherwise false.
        shiftX - the value will be added to each cell's x-coordinate to reach effect of shifting.
        shiftY - the value will be added to each cell's t-coordinate to reach effect of shifting.
        Returns:
        knight's tour.