Revision: 67345
Updated Code
at September 14, 2014 12:32 by greymatters
Updated Code
package testknight;
import java.util.Arrays;
/**
*
* @author piguy
*/
// Recommended reading on basics of graphs:
// http://www.seas.gwu.edu/~simhaweb/alg/lectures/module7/module7.html
//
public class KnightsTour {
private int[][] board;
private int[] vertex;
private int[][] adjMatrix;
private int[] path;
private int count, V;
private boolean hasPrinted;
// Used in calendar match routine variation
// Highest number of date-to-position matches
private int calMatchRecord = 0;
// Create standard 8 by 8 chessboard using default constructor
// No need to test for rectangular arrays, as it is being built rectangular
// 1 denotes square onto which knight can be moved
// 0 denotes square onto which knight cannot be moved (Not used in default construtor)
//
// board[][] is an 8 by 8 array of 1s,
// denoting shape of the board
//
// vertex[X] = N, where X is the Xth legal square and
// N is the Nth square in the shape[][] array,
// starting from 0 in the upper left, reading across, THEN down.
//
// adjMatrix[][] (adjacency matrix) is an array used to denote which
// vertices are adjacent to which other vertices
// Note: Knight's Tour is always an
// undirected graph with no self-loops
// References:
// http://en.wikipedia.org/wiki/Adjacency_matrix
// http://mathworld.wolfram.com/AdjacencyMatrix.html
public KnightsTour() {
board = new int[8][8];
vertex = new int[64];
for (int i=0; i < 8; i++) {
for (int j=0; j < 8; j++) {
// Allow knight to be on this square
board[i][j] = 1;
// Record the location of this vertex (legal square for a knight)
vertex[(8 * i) + j] = ((8 * i) + j);
}
}
// Build adjacency matrix
//
// Declare size of adjacency matrix
adjMatrix = new int[vertex.length][vertex.length];
// Test for adjacency
// between a current spot, vertex i whose coordinates are (x, y)
// and a second test spot, vertex j whose coordinates are (x, y)
for (int i=0; i < vertex.length; i++) {
for (int j=0; j < vertex.length; j++) {
// Convert vertex i's location into x and y coordinates
int curSpotX = (int)(Math.floor(vertex[i] / (board[0].length)));
int curSpotY = (vertex[i] % (board[0].length));
// Convert vertex j's location into x and y coordinates
int testSpotX = (int)(Math.floor(vertex[j] / (board[0].length)));
int testSpotY = (vertex[j] % (board[0].length));
// Calculate the absolute difference in x coordinates
int xDiff = Math.abs(testSpotX - curSpotX);
// Calculate the absolute difference in y coordinates
int yDiff = Math.abs(testSpotY - curSpotY);
// Is one difference 2 and the other difference 1?
if (((xDiff == 2) && (yDiff == 1)) || ((xDiff == 1) && (yDiff == 2))) {
// If so, consider them adjacent
adjMatrix[i][j] = 1;
}
else {
// If not, don't consider them adjacent
adjMatrix[i][j] = 0;
}
}
}
}
// Create custom-shaped board using 2d integer array via custom constructor
// "shape" is passed from 2d integer array
// 1 denotes square onto which knight can be moved
// 0 denotes square onto which knight cannot be moved
//
// board[][] is a copy of shape[][]
//
// vertex[X] = N, where X is the Xth legal square and
// N is the Nth square in the board[][] array,
// starting from 0 in the upper left, reading across, THEN down.
//
// adjMatrix[][] (adjacency matrix) is a 2D array used to denote which
// vertices are adjacent to which other vertices
// Note: Knight's Tour is always an
// undirected graph with no self-loops
// References:
// http://en.wikipedia.org/wiki/Adjacency_matrix
// http://mathworld.wolfram.com/AdjacencyMatrix.html
public KnightsTour(int[][] shape) {
// Test whether integer array is rectangular
//
// Get the length of the first row
int width = shape[0].length;
// Get height of array
int height = shape.length;
boolean passTest = true;
for (int i = 1; i < height; i++) {
// Is the length of this row different from the first row?
if (shape[i].length != width) {
// Mark the test as having failed
passTest = false;
break;
}
}
if (passTest == false) {
// If board is NOT rectangular, notify user and end program
System.out.println("Error! Shape array is not rectangular!");
System.exit(0);
}
// Declare size of board
board = new int[height][width];
// Count # of vertices for later array declaration
int vertexCounter = 0;
// Since board is rectangular, make it a new KnightsTourOrig object
for (int i=0; i < height; i++) {
for (int j=0; j < width; j++) {
// Copy custom shape into board
board[i][j] = shape[i][j];
if (shape[i][j] == 1) {
// If this square is a legal move for the knight,
// add 1 to the vertex counter
vertexCounter++;
}
}
}
// Use number of vertices to declare vertex array
vertex = new int[vertexCounter];
// Create list of vertices (squares onto which the knight can move)
// starting with 0
int vertexInc = 0;
for (int i=0; i < height; i++) {
for (int j=0; j < width; j++) {
// Is this a legal square upon which the knight can move?
if (board[i][j] == 1) {
// Record the location of this vertex (legal square for a knight)
vertex[vertexInc] = (width * i) + j;
// Increment array counter for next vertex
vertexInc++;
}
}
}
// Build adjacency matrix
//
// Declare size of adjacency matrix
adjMatrix = new int[vertex.length][vertex.length];
// Test for adjacency
// between a current spot, vertex i whose coordinates are (x, y)
// and a second test spot, vertex j whose coordinates are (x, y)
for (int i=0; i < vertex.length; i++) {
for (int j=0; j < vertex.length; j++) {
// Convert vertex i's location into x and y coordinates
int curSpotX = (int)(Math.floor(vertex[i] / (board[0].length)));
int curSpotY = (vertex[i] % (board[0].length));
// Convert vertex j's location into x and y coordinates
int testSpotX = (int)(Math.floor(vertex[j] / (board[0].length)));
int testSpotY = (vertex[j] % (board[0].length));
// Calculate the absolute difference in x coordinates
int xDiff = Math.abs(testSpotX - curSpotX);
// Calculate the absolute difference in y coordinates
int yDiff = Math.abs(testSpotY - curSpotY);
// Is one difference 2 and the other difference 1?
if (((xDiff == 2) && (yDiff == 1)) || ((xDiff == 1) && (yDiff == 2))) {
// If so, consider them adjacent
adjMatrix[i][j] = 1;
}
else {
// If not, don't consider them adjacent
adjMatrix[i][j] = 0;
}
}
}
}
// return number of vertices on board
public int getNumOfVertices() {
return vertex.length;
}
// Display board shape
public void displayBoard() {
int rows = board.length;
int cols = board[0].length;
for (int i=0; i < rows; i++) {
for (int j=0; j < cols; j++) {
if (board[i][j] == 1) {
System.out.print("X ");
}
else {
System.out.print(" ");
}
}
System.out.println();
}
}
// Display adjMatrix contents
public void displayAdjMatrix() {
int n = vertex.length;
for (int i=0; i < n; i++) {
for (int j=0; j < n; j++) {
System.out.print(adjMatrix[i][j]);
}
System.out.println();
}
}
// Backtracking algorithm to
// find 1 closed Knight's Tour
// AKA a Hamiltonian cycle
public void findAClosedKnightsTour() {
// Variable used to ensure only one solution is printed
hasPrinted = false;
// Get size of adjacency matrix
V = adjMatrix.length;
// Set path to size of adjacency matrix
path = new int[V];
// Fill path with -1s to start
Arrays.fill(path, -1);
// Use 0 as starting point
// Since we're looking for a cycle
// It doesn't matter which point is chosen
path[0] = 0;
if (singleTourUtil(1, "closed") == false) {
System.out.println("No closed Knight's Tours found on this board.");
}
}
// Backtracking algorithm to
// find 1 closed Knight's Tour
// starting at a given vertex
// AKA a Hamiltonian cycle
public void findAClosedKnightsTour(int start) {
// Variable used to ensure only one solution is printed
hasPrinted = false;
// Get size of adjacency matrix
V = adjMatrix.length;
// Set path to size of adjacency matrix
path = new int[V];
// Fill path with -1s to start
Arrays.fill(path, -1);
// Use 0 as starting point
// Since we're looking for a cycle
// It doesn't matter which point is chosen
path[0] = start;
if (singleTourUtil(1, "closed") == false) {
System.out.println("No closed Knight's Tours found on this board starting at vertex #" + start + ".");
}
}
// Backtracking algorithm to
// find all closed Knight's Tours
// AKA Hamiltonian cycles
public void findAllClosedKnightsTours() {
// Clear count of open Knight's Tour paths
count = 0;
// Get size of adjacency matrix
V = adjMatrix.length;
// Set path to size of adjacency matrix
path = new int[V];
// Fill path with -1s to start
Arrays.fill(path, -1);
// Use 0 as starting point
// Since we're looking for a cycle
// It doesn't matter which point is chosen
path[0] = 0;
multiToursUtil(1, "closed");
if (count != 0) {
System.out.println("Found " + count + " closed Knight's Tours on this board.");
}
else {
System.out.println("No closed Knight's Tours found on this board.");
}
}
// Backtracking algorithm to
// find all closed Knight's Tours
// starting at a given vertex
// AKA Hamiltonian cycles
public void findAllClosedKnightsTours(int start) {
// Clear count of open Knight's Tour paths
count = 0;
// Get size of adjacency matrix
V = adjMatrix.length;
// Set path to size of adjacency matrix
path = new int[V];
// Fill path with -1s to start
Arrays.fill(path, -1);
// Use 0 as starting point
// Since we're looking for a cycle
// It doesn't matter which point is chosen
path[0] = start;
multiToursUtil(1, "closed");
if (count != 0) {
System.out.println("Found " + count + " closed Knight's Tours on this board starting at vertex #" + start + ".");
}
else {
System.out.println("No closed Knight's Tours found on this board starting at vertex #" + start + ".");
}
}
// Backtracking algorithm to
// find 1 open Knight's Tour
// starting at a given vertex
// AKA a Hamiltonian path
public void findAnOpenKnightsTour(int start) {
// Variable used to ensure only one solution is printed
hasPrinted = false;
// Get size of adjacency matrix
V = adjMatrix.length;
// Set path to size of adjacency matrix
path = new int[V];
// Fill path with -1s to start
Arrays.fill(path, -1);
// Set starting point
path[0] = start;
if (singleTourUtil(1, "open") == false) {
System.out.println("No open Knight's Tours found on this board starting at vertex #" + start + ".");
}
}
// Backtracking algorithm to
// find all open Knight's Tours
// starting at a given vertex
// AKA Hamiltonian paths
public void findAllOpenKnightsTours(int start) {
// Clear count of open Knight's Tour paths
count = 0;
// Get size of adjacency matrix
V = adjMatrix.length;
// Set path to size of adjacency matrix
path = new int[V];
// Fill path with -1s to start
Arrays.fill(path, -1);
// Set starting point
path[0] = start;
multiToursUtil(1, "open");
if (count != 0) {
System.out.println("Found " + count + " open Knight's Tours on this board starting at vertex #" + start + ".");
}
else {
System.out.println("No open Knight's Tours found on this board starting at vertex #" + start + ".");
}
}
// Backtracking algorithm to
// find all Knight's Tours starting
// at a given vertex
// AKA Hamiltonian paths AND cycles
public void findAllKnightsTours(int start) {
// Clear count of open Knight's Tour paths
count = 0;
// Get size of adjacency matrix
V = adjMatrix.length;
// Set path to size of adjacency matrix
path = new int[V];
// Fill path with -1s to start
Arrays.fill(path, -1);
// Set starting point
path[0] = start;
multiToursUtil(1, "all");
if (count != 0) {
System.out.println("Found " + count + " Knight's Tours on this board starting at vertex #" + start + ".");
}
else {
System.out.println("No Knight's Tours found on this board starting at vertex #" + start + ".");
}
}
// Recursive backtracking routine to
// build and check paths for the first
// Knights Tour it can find
// "open" = open Knight's Tour (Hamiltonian path)
// "closed" = closed Knight's Tour (Hamiltonian cycle)
// "all" = either an open or closed Knight's Tour
private boolean singleTourUtil(int pos, String type) {
// Are all vertices included in the cycle?
if (pos == V) {
// Can you move from the final position to the start?
if (adjMatrix[path[pos-1]][path[0]] == 1) {
if (((type.equals("closed")) || (type.equals("all"))) && (hasPrinted == false)) {
displayKnightsTour("CLOSED TOUR:");
hasPrinted = true;
return true;
}
else {
return false;
}
}
else {
if (((type.equals("open")) || (type.equals("all"))) && (hasPrinted == false)) {
displayKnightsTour("OPEN TOUR:");
hasPrinted = true;
return true;
}
else {
return false;
}
}
}
// Try different vertices as a next candidate in Hamiltonian Cycle
for (int v = 0; v < V; v++) {
// Can this vertex be added to the path?
if (isSafe(v, pos)) {
// Add this vertex to the path
path[pos] = v;
// Recur to construct the rest of the path
if (singleTourUtil(pos+1, type) == true) {
return true;
}
// If program makes it here, adding vertex v
// didn't lead to a solution, so remove it
path[pos] = -1;
}
}
// If program makes it here, then
// no vertex can be added
return false;
}
// Recursive backtracking routine to
// build and check paths for multiple
// Knights Tours
// "open" = open Knight's Tour (Hamiltonian path)
// "closed" = closed Knight's Tour (Hamiltonian cycle)
// "all" = both open and closed Knight's Tours
private void multiToursUtil(int pos, String type) {
// Are all veritces included in the cycle?
if (pos == V) {
// Can you move from the final position to the start?
if (adjMatrix[path[pos-1]][path[0]] == 1) {
if ((type.equals("closed")) || (type.equals("all"))) {
count++;
if (type.equals("all")) {
displayKnightsTour("CLOSED:");
}
else {
displayKnightsTour("");
}
}
return;
}
else {
if ((type.equals("open")) || (type.equals("all"))) {
count++;
if (type.equals("all")) {
displayKnightsTour("OPEN:");
}
else {
displayKnightsTour("");
}
}
return;
}
}
// Try different vertices as a next candidate in Hamiltonian Cycle
for (int v = 0; v < V; v++) {
// Can this vertex be added to the path?
if (isSafe(v, pos)) {
// Add this vertex to the path
path[pos] = v;
// Recur to construct the rest of the path
multiToursUtil(pos + 1, type);
// If program makes it here, adding vertex v
// didn't lead to a solution, so remove it
path[pos] = -1;
}
}
}
// Check whether vertex v can be added
// at index pos in the path constructed so far
// Used in tour-finding algorithms
private boolean isSafe(int v, int pos) {
// Is this vertex NOT adjacent to the previously added vertex?
if (adjMatrix[path[pos-1]][ v ] == 0) {
return false;
}
// Loop to check whether vertex has already been included
for (int i = 0; i < pos; i++) {
// If vertex is already in path
if (path[i] == v) {
// report that it isn't safe
return false;
}
}
// vertex passed all the tests
return true;
}
private void displayKnightsTour(String type) {
// Get and display row and column information
int rows = board.length;
int cols = board[0].length;
int temp1 = 0;
int temp2 = 0;
// If needed, add label to tour
// Currently used to denoted whether
// a tour is open or closed
if (!type.equals("")) {
System.out.println(type);
}
for (int i=0; i < rows; i++) {
for (int j=0; j < cols; j++) {
int n = (cols * i) + j;
// Is it legal for the knight to be on this square?
if (board[i][j] == 1) {
// Find out which vertex this is
for (int k = 0; k < vertex.length; k++) {
if (vertex[k] == n) {
// Save the vertex as temp1
temp1 = k;
break;
}
}
// Find the index of this vertex in path[]
for (int k = 0; k < path.length; k++) {
if (path[k] == temp1) {
// Save the index as temp2
temp2 = k;
break;
}
}
// Display move as starting from 1, not 0
System.out.printf("%2d", (temp2 + 1));
System.out.print(" ");
}
else {
System.out.print(" ");
}
}
System.out.println();
}
System.out.println();
}
// Beyond here are various methods
// which can be deleted, if desired
// Find tours with matches to their dates
// Inspired by:
// http://forums.xkcd.com/viewtopic.php?f=3&t=62580
// Backtracking algorithm to
// find all Knight's Tours starting
// at a given vertex
// AKA Hamiltonian paths (including Hamiltonian cycles)
public void findAllKnightsToursCalendars(int start) {
// Clear count of open Knight's Tour paths
count = 0;
// Get size of adjacency matrix
V = adjMatrix.length;
// Set path to size of adjacency matrix
path = new int[V];
// Fill path with -1s to start
Arrays.fill(path, -1);
// Set starting point
path[0] = start;
multiToursCalUtil(1, "all");
if (count != 0) {
System.out.println("Found " + count + " Knight's Tours on this board starting at vertex #" + start + ".");
}
else {
System.out.println("No Knight's Tours found on this board starting at vertex #" + start + ".");
}
}
// Recursive backtracking routine to
// build and check paths for multiple
// Knights Tours
// "open" = open Knight's Tour (Hamiltonian path)
// "closed" = closed Knight's Tour (Hamiltonian cycle)
// "all" = both open and closed Knight's Tours
private void multiToursCalUtil(int pos, String type) {
// Are all veritces included in the cycle?
if (pos == V) {
// Can you move from the final position to the start?
if (adjMatrix[path[pos-1]][path[0]] == 1) {
if ((type.equals("closed")) || (type.equals("all"))) {
count++;
if (type.equals("all")) {
displayKnightsTourCalendar("CLOSED:");
}
else {
displayKnightsTourCalendar("");
}
}
return;
}
else {
if ((type.equals("open")) || (type.equals("all"))) {
count++;
if (type.equals("all")) {
displayKnightsTourCalendar("OPEN:");
}
else {
displayKnightsTourCalendar("");
}
}
return;
}
}
// Try different vertices as a next candidate in Hamiltonian Cycle
for (int v = 0; v < V; v++) {
// Can this vertex be added to the path?
if (isSafe(v, pos)) {
// Add this vertex to the path
path[pos] = v;
// Recur to construct the rest of the path
multiToursCalUtil(pos + 1, type);
// If program makes it here, adding vertex v
// didn't lead to a solution, so remove it
path[pos] = -1;
}
}
}
private void displayKnightsTourCalendar(String type) {
// Get and display row and column information
int rows = board.length;
int cols = board[0].length;
int temp1 = 0;
int temp2 = 0;
// calOffset = Code for day of week of the 1st
// Code: 0=Sunday, 1=Monday, 2=Tuesday, 3=Wednesday
// 4=Thursday, 5=Friday, 6=Saturday,
int calOffset = 3;
// Counter for number of date-to-position matches
int calMatchCounter = 0;
// If needed, add label to tour
// Currently used to denoted whether
// a tour is open or closed
if (!type.equals("")) {
System.out.println(type);
}
for (int i=0; i < rows; i++) {
for (int j=0; j < cols; j++) {
int n = (cols * i) + j;
// Is it legal for the knight to be on this square?
if (board[i][j] == 1) {
// Find out which vertex this is
for (int k = 0; k < vertex.length; k++) {
if (vertex[k] == n) {
// Save the vertex as temp1
temp1 = k;
break;
}
}
// Find the index of this vertex in path[]
for (int k = 0; k < path.length; k++) {
if (path[k] == temp1) {
// Save the index as temp2
temp2 = k;
break;
}
}
// Display move as starting from 1, not 0
System.out.printf("%2d", (temp2 + 1));
// Do date and move number match?
if ((temp2 + calOffset) == n) {
calMatchCounter++;
System.out.print("* ");
}
else {
System.out.print(" ");
}
}
else {
System.out.print(" ");
}
}
System.out.println();
}
// Print out number of date-to-move matches
System.out.println(calMatchCounter + " matches.");
// Determine whether this is a record
if (calMatchCounter > calMatchRecord) {
calMatchRecord = calMatchCounter;
System.out.println(calMatchRecord + " is a new record!");
}
System.out.println();
}
// Return the number of highest matches
// of moves and dates
public int getMostMatches() {
return calMatchRecord;
}
}
Revision: 67344
Initial Code
Initial URL
Initial Description
Initial Title
Initial Tags
Initial Language
at September 13, 2014 08:31 by greymatters
Initial Code
package testknight;
import java.util.Arrays;
/**
*
* @author piguy
*/
// Recommended reading on basics of graphs:
// http://www.seas.gwu.edu/~simhaweb/alg/lectures/module7/module7.html
//
public class KnightsTour {
private int[][] board;
private int[] vertex;
private int[][] adjMatrix;
private int[] path;
private int count, V;
private boolean hasPrinted;
private long startTime;
private String progressBar;
// Used in calendar match routine variation
// Highest number of date-to-position matches
private int calMatchRecord = 0;
// Create standard 8 by 8 chessboard using default constructor
// No need to test for rectangular arrays, as it is being built rectangular
// 1 denotes square onto which knight can be moved
// 0 denotes square onto which knight cannot be moved (Not used in default construtor)
//
// board[][] is an 8 by 8 array of 1s,
// denoting shape of the board
//
// vertex[X] = N, where X is the Xth legal square and
// N is the Nth square in the shape[][] array,
// starting from 0 in the upper left, reading across, THEN down.
//
// adjMatrix[][] (adjacency matrix) is an array used to denote which
// vertices are adjacent to which other vertices
// Note: Knight's Tour is always an
// undirected graph with no self-loops
// References:
// http://en.wikipedia.org/wiki/Adjacency_matrix
// http://mathworld.wolfram.com/AdjacencyMatrix.html
public KnightsTour() {
board = new int[8][8];
vertex = new int[64];
for (int i=0; i < 8; i++) {
for (int j=0; j < 8; j++) {
// Allow knight to be on this square
board[i][j] = 1;
// Record the location of this vertex (legal square for a knight)
vertex[(8 * i) + j] = ((8 * i) + j);
}
}
// Build adjacency matrix
//
// Declare size of adjacency matrix
adjMatrix = new int[vertex.length][vertex.length];
// Test for adjacency
// between a current spot, vertex i whose coordinates are (x, y)
// and a second test spot, vertex j whose coordinates are (x, y)
for (int i=0; i < vertex.length; i++) {
for (int j=0; j < vertex.length; j++) {
// Convert vertex i's location into x and y coordinates
int curSpotX = (int)(Math.floor(vertex[i] / (board[0].length)));
int curSpotY = (vertex[i] % (board[0].length));
// Convert vertex j's location into x and y coordinates
int testSpotX = (int)(Math.floor(vertex[j] / (board[0].length)));
int testSpotY = (vertex[j] % (board[0].length));
// Calculate the absolute difference in x coordinates
int xDiff = Math.abs(testSpotX - curSpotX);
// Calculate the absolute difference in y coordinates
int yDiff = Math.abs(testSpotY - curSpotY);
// Is one difference 2 and the other difference 1?
if (((xDiff == 2) && (yDiff == 1)) || ((xDiff == 1) && (yDiff == 2))) {
// If so, consider them adjacent
adjMatrix[i][j] = 1;
}
else {
// If not, don't consider them adjacent
adjMatrix[i][j] = 0;
}
}
}
}
// Create custom-shaped board using 2d integer array via custom constructor
// "shape" is passed from 2d integer array
// 1 denotes square onto which knight can be moved
// 0 denotes square onto which knight cannot be moved
//
// board[][] is a copy of shape[][]
//
// vertex[X] = N, where X is the Xth legal square and
// N is the Nth square in the board[][] array,
// starting from 0 in the upper left, reading across, THEN down.
//
// adjMatrix[][] (adjacency matrix) is a 2D array used to denote which
// vertices are adjacent to which other vertices
// Note: Knight's Tour is always an
// undirected graph with no self-loops
// References:
// http://en.wikipedia.org/wiki/Adjacency_matrix
// http://mathworld.wolfram.com/AdjacencyMatrix.html
public KnightsTour(int[][] shape) {
// Test whether integer array is rectangular
//
// Get the length of the first row
int width = shape[0].length;
// Get height of array
int height = shape.length;
boolean passTest = true;
for (int i = 1; i < height; i++) {
// Is the length of this row different from the first row?
if (shape[i].length != width) {
// Mark the test as having failed
passTest = false;
break;
}
}
if (passTest == false) {
// If board is NOT rectangular, notify user and end program
System.out.println("Error! Shape array is not rectangular!");
System.exit(0);
}
// Declare size of board
board = new int[height][width];
// Count # of vertices for later array declaration
int vertexCounter = 0;
// Since board is rectangular, make it a new KnightsTourOrig object
for (int i=0; i < height; i++) {
for (int j=0; j < width; j++) {
// Copy custom shape into board
board[i][j] = shape[i][j];
if (shape[i][j] == 1) {
// If this square is a legal move for the knight,
// add 1 to the vertex counter
vertexCounter++;
}
}
}
// Use number of vertices to declare vertex array
vertex = new int[vertexCounter];
// Create list of vertices (squares onto which the knight can move)
// starting with 0
int vertexInc = 0;
for (int i=0; i < height; i++) {
for (int j=0; j < width; j++) {
// Is this a legal square upon which the knight can move?
if (board[i][j] == 1) {
// Record the location of this vertex (legal square for a knight)
vertex[vertexInc] = (width * i) + j;
// Increment array counter for next vertex
vertexInc++;
}
}
}
// Build adjacency matrix
//
// Declare size of adjacency matrix
adjMatrix = new int[vertex.length][vertex.length];
// Test for adjacency
// between a current spot, vertex i whose coordinates are (x, y)
// and a second test spot, vertex j whose coordinates are (x, y)
for (int i=0; i < vertex.length; i++) {
for (int j=0; j < vertex.length; j++) {
// Convert vertex i's location into x and y coordinates
int curSpotX = (int)(Math.floor(vertex[i] / (board[0].length)));
int curSpotY = (vertex[i] % (board[0].length));
// Convert vertex j's location into x and y coordinates
int testSpotX = (int)(Math.floor(vertex[j] / (board[0].length)));
int testSpotY = (vertex[j] % (board[0].length));
// Calculate the absolute difference in x coordinates
int xDiff = Math.abs(testSpotX - curSpotX);
// Calculate the absolute difference in y coordinates
int yDiff = Math.abs(testSpotY - curSpotY);
// Is one difference 2 and the other difference 1?
if (((xDiff == 2) && (yDiff == 1)) || ((xDiff == 1) && (yDiff == 2))) {
// If so, consider them adjacent
adjMatrix[i][j] = 1;
}
else {
// If not, don't consider them adjacent
adjMatrix[i][j] = 0;
}
}
}
}
// return number of vertices on board
public int getNumOfVertices() {
return vertex.length;
}
// Display board shape
public void displayBoard() {
int rows = board.length;
int cols = board[0].length;
for (int i=0; i < rows; i++) {
for (int j=0; j < cols; j++) {
if (board[i][j] == 1) {
System.out.print("X ");
}
else {
System.out.print(" ");
}
}
System.out.println();
}
}
// Display adjMatrix contents
public void displayAdjMatrix() {
int n = vertex.length;
for (int i=0; i < n; i++) {
for (int j=0; j < n; j++) {
System.out.print(adjMatrix[i][j]);
}
System.out.println();
}
}
// Backtracking algorithm to
// find 1 closed Knight's Tour
// AKA a Hamiltonian cycle
public void findAClosedKnightsTour() {
// Variable used to ensure only one solution is printed
hasPrinted = false;
// Get size of adjacency matrix
V = adjMatrix.length;
// Set path to size of adjacency matrix
path = new int[V];
// Fill path with -1s to start
Arrays.fill(path, -1);
// Use 0 as starting point
// Since we're looking for a cycle
// It doesn't matter which point is chosen
path[0] = 0;
if (singleTourUtil(1, "closed") == false) {
System.out.println("No closed Knight's Tours found on this board.");
}
}
// Backtracking algorithm to
// find 1 closed Knight's Tour
// starting at a given vertex
// AKA a Hamiltonian cycle
public void findAClosedKnightsTour(int start) {
// Variable used to ensure only one solution is printed
hasPrinted = false;
// Get size of adjacency matrix
V = adjMatrix.length;
// Set path to size of adjacency matrix
path = new int[V];
// Fill path with -1s to start
Arrays.fill(path, -1);
// Use 0 as starting point
// Since we're looking for a cycle
// It doesn't matter which point is chosen
path[0] = start;
if (singleTourUtil(1, "closed") == false) {
System.out.println("No closed Knight's Tours found on this board starting at vertex #" + start + ".");
}
}
// Backtracking algorithm to
// find all closed Knight's Tours
// AKA Hamiltonian cycles
public void findAllClosedKnightsTours() {
// Clear count of open Knight's Tour paths
count = 0;
// Get size of adjacency matrix
V = adjMatrix.length;
// Set path to size of adjacency matrix
path = new int[V];
// Fill path with -1s to start
Arrays.fill(path, -1);
// Use 0 as starting point
// Since we're looking for a cycle
// It doesn't matter which point is chosen
path[0] = 0;
multiToursUtil(1, "closed");
if (count != 0) {
System.out.println("Found " + count + " closed Knight's Tours on this board.");
}
else {
System.out.println("No closed Knight's Tours found on this board.");
}
}
// Backtracking algorithm to
// find all closed Knight's Tours
// starting at a given vertex
// AKA Hamiltonian cycles
public void findAllClosedKnightsTours(int start) {
// Clear count of open Knight's Tour paths
count = 0;
// Get size of adjacency matrix
V = adjMatrix.length;
// Set path to size of adjacency matrix
path = new int[V];
// Fill path with -1s to start
Arrays.fill(path, -1);
// Use 0 as starting point
// Since we're looking for a cycle
// It doesn't matter which point is chosen
path[0] = start;
multiToursUtil(1, "closed");
if (count != 0) {
System.out.println("Found " + count + " closed Knight's Tours on this board starting at vertex #" + start + ".");
}
else {
System.out.println("No closed Knight's Tours found on this board starting at vertex #" + start + ".");
}
}
// Backtracking algorithm to
// find 1 open Knight's Tour
// starting at a given vertex
// AKA a Hamiltonian path
public void findAnOpenKnightsTour(int start) {
// Variable used to ensure only one solution is printed
hasPrinted = false;
// Get size of adjacency matrix
V = adjMatrix.length;
// Set path to size of adjacency matrix
path = new int[V];
// Fill path with -1s to start
Arrays.fill(path, -1);
// Set starting point
path[0] = start;
if (singleTourUtil(1, "open") == false) {
System.out.println("No open Knight's Tours found on this board starting at vertex #" + start + ".");
}
}
// Backtracking algorithm to
// find all open Knight's Tours
// starting at a given vertex
// AKA Hamiltonian paths
public void findAllOpenKnightsTours(int start) {
// Clear count of open Knight's Tour paths
count = 0;
// Get size of adjacency matrix
V = adjMatrix.length;
// Set path to size of adjacency matrix
path = new int[V];
// Fill path with -1s to start
Arrays.fill(path, -1);
// Set starting point
path[0] = start;
multiToursUtil(1, "open");
if (count != 0) {
System.out.println("Found " + count + " open Knight's Tours on this board starting at vertex #" + start + ".");
}
else {
System.out.println("No open Knight's Tours found on this board starting at vertex #" + start + ".");
}
}
// Backtracking algorithm to
// find all Knight's Tours starting
// at a given vertex
// AKA Hamiltonian paths AND cycles
public void findAllKnightsTours(int start) {
// Clear count of open Knight's Tour paths
count = 0;
// Get size of adjacency matrix
V = adjMatrix.length;
// Set path to size of adjacency matrix
path = new int[V];
// Fill path with -1s to start
Arrays.fill(path, -1);
// Set starting point
path[0] = start;
multiToursUtil(1, "all");
if (count != 0) {
System.out.println("Found " + count + " Knight's Tours on this board starting at vertex #" + start + ".");
}
else {
System.out.println("No Knight's Tours found on this board starting at vertex #" + start + ".");
}
}
// Recursive backtracking routine to
// build and check paths for the first
// Knights Tour it can find
// "open" = open Knight's Tour (Hamiltonian path)
// "closed" = closed Knight's Tour (Hamiltonian cycle)
// "all" = either an open or closed Knight's Tour
private boolean singleTourUtil(int pos, String type) {
// Are all vertices included in the cycle?
if (pos == V) {
// Can you move from the final position to the start?
if (adjMatrix[path[pos-1]][path[0]] == 1) {
if (((type.equals("closed")) || (type.equals("all"))) && (hasPrinted == false)) {
displayKnightsTour("CLOSED TOUR:");
hasPrinted = true;
return true;
}
else {
return false;
}
}
else {
if (((type.equals("open")) || (type.equals("all"))) && (hasPrinted == false)) {
displayKnightsTour("OPEN TOUR:");
hasPrinted = true;
return true;
}
else {
return false;
}
}
}
// Try different vertices as a next candidate in Hamiltonian Cycle
for (int v = 0; v < V; v++) {
// Can this vertex be added to the path?
if (isSafe(v, pos)) {
// Add this vertex to the path
path[pos] = v;
// Recur to construct the rest of the path
if (singleTourUtil(pos+1, type) == true) {
return true;
}
// If program makes it here, adding vertex v
// didn't lead to a solution, so remove it
path[pos] = -1;
}
}
// If program makes it here, then
// no vertex can be added
return false;
}
// Recursive backtracking routine to
// build and check paths for multiple
// Knights Tours
// "open" = open Knight's Tour (Hamiltonian path)
// "closed" = closed Knight's Tour (Hamiltonian cycle)
// "all" = both open and closed Knight's Tours
private void multiToursUtil(int pos, String type) {
// Are all veritces included in the cycle?
if (pos == V) {
// Can you move from the final position to the start?
if (adjMatrix[path[pos-1]][path[0]] == 1) {
if ((type.equals("closed")) || (type.equals("all"))) {
count++;
if (type.equals("all")) {
displayKnightsTour("CLOSED:");
}
else {
displayKnightsTour("");
}
}
return;
}
else {
if ((type.equals("open")) || (type.equals("all"))) {
count++;
if (type.equals("all")) {
displayKnightsTour("OPEN:");
}
else {
displayKnightsTour("");
}
}
return;
}
}
// Try different vertices as a next candidate in Hamiltonian Cycle
for (int v = 0; v < V; v++) {
// Can this vertex be added to the path?
if (isSafe(v, pos)) {
// Add this vertex to the path
path[pos] = v;
// Recur to construct the rest of the path
multiToursUtil(pos + 1, type);
// If program makes it here, adding vertex v
// didn't lead to a solution, so remove it
path[pos] = -1;
}
}
}
// Check whether vertex v can be added
// at index pos in the path constructed so far
// Used in tour-finding algorithms
private boolean isSafe(int v, int pos) {
// Is this vertex NOT adjacent to the previously added vertex?
if (adjMatrix[path[pos-1]][ v ] == 0) {
return false;
}
// Loop to check whether vertex has already been included
for (int i = 0; i < pos; i++) {
// If vertex is already in path
if (path[i] == v) {
// report that it isn't safe
return false;
}
}
// vertex passed all the tests
return true;
}
private void displayKnightsTour(String type) {
// Get and display row and column information
int rows = board.length;
int cols = board[0].length;
int temp1 = 0;
int temp2 = 0;
// If needed, add label to tour
// Currently used to denoted whether
// a tour is open or closed
if (!type.equals("")) {
System.out.println(type);
}
for (int i=0; i < rows; i++) {
for (int j=0; j < cols; j++) {
int n = (cols * i) + j;
// Is it legal for the knight to be on this square?
if (board[i][j] == 1) {
// Find out which vertex this is
for (int k = 0; k < vertex.length; k++) {
if (vertex[k] == n) {
// Save the vertex as temp1
temp1 = k;
break;
}
}
// Find the index of this vertex in path[]
for (int k = 0; k < path.length; k++) {
if (path[k] == temp1) {
// Save the index as temp2
temp2 = k;
break;
}
}
// Display move as starting from 1, not 0
System.out.printf("%2d", (temp2 + 1));
System.out.print(" ");
}
else {
System.out.print(" ");
}
}
System.out.println();
}
System.out.println();
}
// Beyond here are various methods
// which can be deleted, if desired
// Find tours with matches to their dates
// Inspired by:
// http://forums.xkcd.com/viewtopic.php?f=3&t=62580
// Backtracking algorithm to
// find all Knight's Tours starting
// at a given vertex
// AKA Hamiltonian paths (including Hamiltonian cycles)
public void findAllKnightsToursCalendars(int start) {
// Clear count of open Knight's Tour paths
count = 0;
// Get size of adjacency matrix
V = adjMatrix.length;
// Set path to size of adjacency matrix
path = new int[V];
// Fill path with -1s to start
Arrays.fill(path, -1);
// Set starting point
path[0] = start;
multiToursCalUtil(1, "all");
if (count != 0) {
System.out.println("Found " + count + " Knight's Tours on this board starting at vertex #" + start + ".");
}
else {
System.out.println("No Knight's Tours found on this board starting at vertex #" + start + ".");
}
}
// Recursive backtracking routine to
// build and check paths for multiple
// Knights Tours
// "open" = open Knight's Tour (Hamiltonian path)
// "closed" = closed Knight's Tour (Hamiltonian cycle)
// "all" = both open and closed Knight's Tours
private void multiToursCalUtil(int pos, String type) {
// Are all veritces included in the cycle?
if (pos == V) {
// Can you move from the final position to the start?
if (adjMatrix[path[pos-1]][path[0]] == 1) {
if ((type.equals("closed")) || (type.equals("all"))) {
count++;
if (type.equals("all")) {
displayKnightsTourCalendar("CLOSED:");
}
else {
displayKnightsTourCalendar("");
}
}
return;
}
else {
if ((type.equals("open")) || (type.equals("all"))) {
count++;
if (type.equals("all")) {
displayKnightsTourCalendar("OPEN:");
}
else {
displayKnightsTourCalendar("");
}
}
return;
}
}
// Try different vertices as a next candidate in Hamiltonian Cycle
for (int v = 0; v < V; v++) {
// Can this vertex be added to the path?
if (isSafe(v, pos)) {
// Add this vertex to the path
path[pos] = v;
// Recur to construct the rest of the path
multiToursCalUtil(pos + 1, type);
// If program makes it here, adding vertex v
// didn't lead to a solution, so remove it
path[pos] = -1;
}
}
}
private void displayKnightsTourCalendar(String type) {
// Get and display row and column information
int rows = board.length;
int cols = board[0].length;
int temp1 = 0;
int temp2 = 0;
// calOffset = Code for day of week of the 1st
// Code: 0=Sunday, 1=Monday, 2=Tuesday, 3=Wednesday
// 4=Thursday, 5=Friday, 6=Saturday,
int calOffset = 1;
// Counter for number of date-to-position matches
int calMatchCounter = 0;
// If needed, add label to tour
// Currently used to denoted whether
// a tour is open or closed
if (!type.equals("")) {
System.out.println(type);
}
for (int i=0; i < rows; i++) {
for (int j=0; j < cols; j++) {
int n = (cols * i) + j;
// Is it legal for the knight to be on this square?
if (board[i][j] == 1) {
// Find out which vertex this is
for (int k = 0; k < vertex.length; k++) {
if (vertex[k] == n) {
// Save the vertex as temp1
temp1 = k;
break;
}
}
// Find the index of this vertex in path[]
for (int k = 0; k < path.length; k++) {
if (path[k] == temp1) {
// Save the index as temp2
temp2 = k;
break;
}
}
// Display move as starting from 1, not 0
System.out.printf("%2d", (temp2 + 1));
// Do date and move number match?
if ((temp2 + calOffset) == n) {
calMatchCounter++;
System.out.print("* ");
}
else {
System.out.print(" ");
}
}
else {
System.out.print(" ");
}
}
System.out.println();
}
// Print out number of date-to-move matches
System.out.println(calMatchCounter + " matches.");
// Determine whether this is a record
if (calMatchCounter > calMatchRecord) {
calMatchRecord = calMatchCounter;
System.out.println(calMatchRecord + " is a new record!");
}
System.out.println();
}
// Return the number of highest matches
// of moves and dates
public int getMostMatches() {
return calMatchRecord;
}
}
Initial URL
Initial Description
This is a Java class for solving a knight's tour via Hamiltonian path and Hamiltonian cycle algorithms.
Initial Title
KnightsTour.java
Initial Tags
path
Initial Language
Java