KnightsTourEnhanced

/**
Author: Drew Kestell
Date: Oct 17, 2014
E-mail: [email protected]

Exercise 7.22d
An implementation of the Knight's Tour problem.  This algorithm relies on heuristics
to analyze the efficiency of of all possible moves and prioritize accordingly.
If two moves are equal, we look one step further to find the next most efficient move,
and make the move that leads us that direction.
The application repeats the simulation 64 times, starting once from each tile.
*/

package drewKestellChapter72;

import java.util.ArrayList;
import java.util.Random;

public class KnightsTourEnhanced
{
    // tracks the total tour attempts.
    static int tourTracker = 0;

    // tracks the amount of successful tours
    static int successfulTours = 0;

    // random object.
    static Random random = new Random();
    static boolean running = true;

    // tracks the amount of moves by the knight each simulation.
    // initialized in the performTour method.
    static int moveCounter;

    // this two-dimensional array represents the chess board.
    static int[][] chessBoard = new int[8][8];

    // two-dimensional heuristic accessibility array.
    static int[][] accessibility = new int[8][8];

    // these two arrays define the 8 possible moves a knight can make.
    static int[] horizontal = new int[8];
    static int[] vertical = new int[8];

    // these two ints track the knight's current position on the board.
    // initialized in the performTour method.
    static int currentRow;
    static int currentColumn;

    // initializes the chessBoard array to contain all zeros
    public static void initializeChessBoard()
    {
        for(int i = 0; i < 8; i++)
        {
            for(int j = 0; j < 8; j++)
            {
                chessBoard[i][j] = 0;
            }
        }
    }

    // initialize the two arrays which define the 8 possible moves a knight can make.
    public static void initializeMoves()
    {
        // positive numbers indicate the knight is moving right (horizontal) or down (vertical).
        // negative numbers indicate the knight is moving left (horizontal) or up (vertical).
        // for example, move 0 is defined as the knight moving right 2 tiles and up 1 tile.
        horizontal[0] = 2;
        horizontal[1] = 1;
        horizontal[2] = -1;
        horizontal[3] = -2;
        horizontal[4] = -2;
        horizontal[5] = -1;
        horizontal[6] = 1;
        horizontal[7] = 2;
        vertical[0] = -1;
        vertical[1] = -2;
        vertical[2] = -2;
        vertical[3] = -1;
        vertical[4] = 1;
        vertical[5] = 2;
        vertical[6] = 2;
        vertical[7] = 1;
    }

    // the accessibility array defines how many possible moves a knight
    // has starting from any given tile on the chess board.
    public static void initializeAccessibility()
    {
        accessibility[0][0] = 2;
        accessibility[0][1] = 3;
        accessibility[0][2] = 4;
        accessibility[0][3] = 4;
        accessibility[0][4] = 4;
        accessibility[0][5] = 4;
        accessibility[0][6] = 3;
        accessibility[0][7] = 2;
        accessibility[1][0] = 3;
        accessibility[1][1] = 4;
        accessibility[1][2] = 6;
        accessibility[1][3] = 6;
        accessibility[1][4] = 6;
        accessibility[1][5] = 6;
        accessibility[1][6] = 4;
        accessibility[1][7] = 3;
        accessibility[2][0] = 4;
        accessibility[2][1] = 6;
        accessibility[2][2] = 8;
        accessibility[2][3] = 8;
        accessibility[2][4] = 8;
        accessibility[2][5] = 8;
        accessibility[2][6] = 6;
        accessibility[2][7] = 4;
        accessibility[3][0] = 4;
        accessibility[3][1] = 6;
        accessibility[3][2] = 8;
        accessibility[3][3] = 8;
        accessibility[3][4] = 8;
        accessibility[3][5] = 8;
        accessibility[3][6] = 6;
        accessibility[3][7] = 4;
        accessibility[4][0] = 4;
        accessibility[4][1] = 6;
        accessibility[4][2] = 8;
        accessibility[4][3] = 8;
        accessibility[4][4] = 8;
        accessibility[4][5] = 8;
        accessibility[4][6] = 6;
        accessibility[4][7] = 4;
        accessibility[5][0] = 4;
        accessibility[5][1] = 6;
        accessibility[5][2] = 8;
        accessibility[5][3] = 8;
        accessibility[5][4] = 8;
        accessibility[5][5] = 8;
        accessibility[5][6] = 6;
        accessibility[5][7] = 4;
        accessibility[6][0] = 3;
        accessibility[6][1] = 4;
        accessibility[6][2] = 6;
        accessibility[6][3] = 6;
        accessibility[6][4] = 6;
        accessibility[6][5] = 6;
        accessibility[6][6] = 4;
        accessibility[6][7] = 3;
        accessibility[7][0] = 2;
        accessibility[7][1] = 3;
        accessibility[7][2] = 4;
        accessibility[7][3] = 4;
        accessibility[7][4] = 4;
        accessibility[7][5] = 4;
        accessibility[7][6] = 3;
        accessibility[7][7] = 2;
    }

    // moves the knight and updates its current location.
    public static void moveKnight(int moveNumber)
    {
        System.out.printf("Knight is currently in row %d and column %d.  Performing move type %d...\n", currentRow, currentColumn, moveNumber);
        currentRow += vertical[moveNumber];
        currentColumn += horizontal[moveNumber];
        chessBoard[currentRow][currentColumn] = 1;
        adjustAccessibility();
        System.out.printf("After the move, knight is now in row %d and column %d.\n\n", currentRow, currentColumn);

        if(moveCounter == 63)
        {
            System.out.println("Tour complete!  Printing a summary of the tour:\n");
            for(int i = 0; i < 8; i++)
            {
                for(int j = 0; j < 8; j++)
                {
                    System.out.print(chessBoard[i][j] + " ");
                }
                System.out.println();
            }
            System.out.println();
            successfulTours++;
        }
    }

    // finds all possible moves first by checking if a move will put the knight off the
    // board, then by checking if a tile has already been touched.
    public static ArrayList<Integer> findPossibleMoves(int row, int column)
    {
        ArrayList<Integer> moveTracker = new ArrayList<Integer>(0);

        for(int j = 0; j < 8; j++)
        {
            if((row + vertical[j] >= 0 && row + vertical[j] <= 7) &&
                    (column + horizontal[j] >= 0 && column + horizontal[j] <= 7))
            {
                if(chessBoard[row + vertical[j]][column + horizontal[j]] == 0)
                {
                    // if move is valid, and has not yet been made, add potential move to moveTracker.
                    moveTracker.add(j);
                }
            }
        }
        return moveTracker;
    }

    // adjusts the heuristic grid after each move.
    public static void adjustAccessibility()
    {
        ArrayList<Integer> possibleMoves = findPossibleMoves(currentRow, currentColumn);
        for(int i = 0; i < possibleMoves.size(); i++)
        {
            accessibility[(currentRow + vertical[possibleMoves.get(i)])][(currentColumn + horizontal[possibleMoves.get(i)])]--;
        }
    }

    // this method checks each possible move (as determined by the findPossibleMoves method) against the accessibility
    // array to find the best move at any given time.  "harder" moves are prioritized based on heuristic analysis.
    // if two moves are considered equally efficient, a random move is chosen.  this random element is important because
    // it allows the knight to take different routes each simulation, and eventually find a solution.
    // i think i can clean up the logic in this section to make the algorithm more efficient, and the code cleaner.
    public static Integer checkMoveEfficiency(ArrayList<Integer> moveList, int row, int column)
    {
        int tempCurrentRow = row;
        int tempCurrentColumn = column;

        int smallest = accessibility[(tempCurrentRow + vertical[moveList.get(0)])][(tempCurrentColumn + horizontal[moveList.get(0)])];

        ArrayList<Integer> returnMoveList = new ArrayList<Integer>(0);
        ArrayList<Integer> returnMoveEfficiency = new ArrayList<Integer>(0);

        for(int i = 0; i < moveList.size(); i++)
        {
            if(accessibility[(tempCurrentRow + vertical[moveList.get(i)])][(tempCurrentColumn + horizontal[moveList.get(i)])] <= smallest)
            {
                returnMoveList.add(moveList.get(i));
                returnMoveEfficiency.add(accessibility[(tempCurrentRow + vertical[moveList.get(0)])][(tempCurrentColumn + horizontal[moveList.get(0)])]);
            }
        }

        if(returnMoveList.size() == 1)
        {
            return returnMoveList.get(0);
        }

        if(returnMoveEfficiency.get(0) < returnMoveEfficiency.get(1))
        {
            return returnMoveList.get(0);
        }

        if(returnMoveEfficiency.get(1) < returnMoveEfficiency.get(0))
        {
            return returnMoveList.get(1);
        }

        else
        {
            int smallestMove = 100;
            int bestMove = 0;

            for(int i = 0; i < returnMoveList.size(); i++)
            {
                int tempRow = tempCurrentRow + vertical[returnMoveList.get(i)];
                int tempColumn = tempCurrentColumn + horizontal[returnMoveList.get(i)];
                ArrayList<Integer> possibleMoves = findPossibleMoves(tempRow, tempColumn);
                int tempSmallestMove = checkMoveEfficiencyDeeper(possibleMoves, tempRow, tempColumn);

                if(tempSmallestMove < smallestMove)
                {
                    smallestMove = tempSmallestMove;
                    bestMove = i;
                }
            }
            return returnMoveList.get(bestMove);
        }
    }

    public static Integer checkMoveEfficiencyDeeper(ArrayList<Integer> moveList, int row, int column)
    {
        int tempCurrentRow = row;
        int tempCurrentColumn = column;
        int smallestMove = 10;

        for(int i = 0; i < moveList.size(); i++)
        {
            int move = accessibility[(tempCurrentRow + vertical[moveList.get(i)])][(tempCurrentColumn + horizontal[moveList.get(i)])];
            if(move < smallestMove)
            {
                smallestMove = move;
            }
        }
        return smallestMove;
    }

    // primary loop that moves the knight around the board, choosing moves based on their efficiency.
    // (efficiency is determined by the checkMoveEfficiency method).
    public static void performTour(int startingRow, int startingColumn)
    {
        // initialize these two variables to determine the knight's starting position.
        currentRow = startingRow;
        currentColumn = startingColumn;

        // knight starts on this tile, so it should not be visited again.
        chessBoard[startingRow][startingColumn] = 1;

        // initialized moveCounter to 1.
        moveCounter = 1;

        while(moveCounter < 64)
        {
            if(findPossibleMoves(currentRow, currentColumn).size() == 0)
            {
                System.out.println("No possible moves remaining.  Printing a summary of the tour:\n");
                for(int i = 0; i < 8; i++)
                {
                    for(int j = 0; j < 8; j++)
                    {
                        System.out.print(chessBoard[i][j] + " ");
                    }
                    System.out.println();
                }
                System.out.println("\nExiting simulation.\n");
                break;
            }

            else
            {
                System.out.printf("Performing move number %d\n",moveCounter);
                Integer bestMove = checkMoveEfficiency(findPossibleMoves(currentRow, currentColumn), currentRow, currentColumn);
                moveKnight(bestMove);
                moveCounter++;
            }
        }
    }

    // main method.
    public static void main(String[] args)
    {
        // the move types don't change so they can be initialized once.
        initializeMoves();

        for(int i = 0; i < 8; i++)
        {
            for(int j = 0; j < 8; j++)
            {
            // the chessBoard array changes during each to keep track of which tiles have
            // been visited by the knight, so this needs to be reinitialized each simulation.
            initializeChessBoard();

            // the accessibility array is adjusted during the simulation after each move in order
            // to help prioritize which subsequent move to make, so this also needs to be
            // reinitialized each simulation.
            initializeAccessibility();

            // increment the tourTracker and print an update to the console.
            tourTracker++;
            System.out.printf("Attempting tour number %d.\n\n", tourTracker);

            // this method starts the knight's tour simulation.
            performTour(i, j);
            }
        }
        System.out.printf("Simulation complete after %d tours.", tourTracker);
        System.out.printf("\nThere were %d successful tours.", successfulTours);
    }
}