Posted By

greymatters on 09/13/14

Tagged

path

Versions (?)

Last Edited at 09/13/14 08:31am

Statistics

Viewed 787 times

Favorited by 0 user(s)

KnightsTour.java

/ Published in: Java

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

Highlighted TextExpand

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;
    }
}

Report this snippet Tweet

Comments

Subscribe to comments

Comment:

You need to login to post a comment.