Module org.jgrapht.demo

Package org.jgrapht.demo

Class WarnsdorffRuleKnightTourHeuristic

java.lang.Object

org.jgrapht.demo.WarnsdorffRuleKnightTourHeuristic

public class WarnsdorffRuleKnightTourHeuristic
extends java.lang.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 Summary

Constructors

Constructor	Description
WarnsdorffRuleKnightTourHeuristic(int n)	Constructor.
WarnsdorffRuleKnightTourHeuristic(int n, int m)	Constructor.

Method Summary

Modifier and Type	Method	Description
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.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

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.