Package org.jgrapht.demo

Class ParberryKnightTour

  • public class ParberryKnightTour
extends Object
    Implementation of <a href = "https://doi.org/10.1016/S0166-218X(96)00010-8"> Parberry's algorithm</a> for <a href = "https://en.wikipedia.org/wiki/Knight%27s_tour">closed knight's tour problem</a>. This algorithm was firstly introduced in "Discrete Applied Mathematics" Volume 73, Issue 3, 21 March 1997, Pages 251-260. 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. The time complexity of the algorithm is linear in the size of the board, i.e. it is equal to $O(n^2)$, where $n$ is one dimension of the board. The Parberry's algorithm finds CLOSED knight's tour for all boards with size $n \times n$ and $n \times n + 2$, where $n$ is even and $n \geq 6$. The knight's tour is said to be structured if it contains the following $8$ UNDIRECTED moves: 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# #***************************************# #***************************************# #***************************************# #***************************************# #***************************************# #***************************************# #***************************************# #***************************************# #***************************************# #***************************************# #***************************************# #5*************************************7# #4*************************************6# #*54*********************************67*# ######################################### If you are confused with the formal definition of the structured knight's tour please refer to the illustration on the page 3 of the paper <a href = "https://doi.org/10.1016/S0166-218X(96)00010-8"> "An efficient algorithm for the Knight’s tour problem" </a> by Ian Parberry. Algorithm description: Split the initial board on $4$ boards as evenly as possible. Solve the problem for these $4$ boards recursively. Delete the edges which contract the start and the finish cell of the tour on each board, so that on each on $4$ boards closed knight's tour became open knight's tour. Contract these $4$ boards by adding $4$ additional edges between the quadrants.

    • Constructor Detail

      • ParberryKnightTour

        public ParberryKnightTour​(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()
        Returns a closed knight's tour.
        Returns:
        closed knight's tour.