## Posted By

greymatters on 09/13/14

# KnightsTour.java

/ Published in: Java   This is a Java class for solving a knight's tour via Hamiltonian path and Hamiltonian cycle algorithms.

`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;        vertex = new int;        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.length)));                int curSpotY = (vertex[i] % (board.length));                // Convert vertex j's location into x and y coordinates                int testSpotX = (int)(Math.floor(vertex[j] / (board.length)));                int testSpotY = (vertex[j] % (board.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.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.length)));                int curSpotY = (vertex[i] % (board.length));                // Convert vertex j's location into x and y coordinates                int testSpotX = (int)(Math.floor(vertex[j] / (board.length)));                int testSpotY = (vertex[j] % (board.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.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;         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 = 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;         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 = 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 = 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 = 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 = 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] == 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] == 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.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 = 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] == 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.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;    }}`