java.lang.Object
org.jgrapht.demo.ParberryKnightTour
public class ParberryKnightTour
extends java.lang.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 Summary
Constructors Constructor Description ParberryKnightTour(int n, int m)Constructor. -
Method Summary
Modifier and Type Method Description org.jgrapht.demo.KnightTourgetTour()Returns a closed knight's tour.
-
Constructor Details
-
ParberryKnightTour
public ParberryKnightTour(int n, int m)Constructor.- Parameters:
n- width of the board.m- height of the board.
-
-
Method Details
-
getTour
public org.jgrapht.demo.KnightTour getTour()Returns a closed knight's tour.- Returns:
- closed knight's tour.
-