Optimizing this Knight's Tour

Question

My assignment in CS was to make a knight's tour application that could solve the problem from any starting position. I had just finished the code so excuse the lack of deeply descriptive comments. My goal was short code length and easy comprehensibility. There is a lot of excess code such as putting the 0 border around the ACCESS array and that's just due to the assignment requirements. I am looking for improvements that could increase effectiveness and comprehensibility to make this code better. Also, I welcome comments on the code's etiquette. I knows it's not the prettiest thing in the world so have at it.

//Knight's Tour Solver
//Willy Xu 2015
import java.util.*;
import java.io.*;

public class Lab16ast {
    public static void main (String args[]) throws IOException {
        Knight knight = new Knight();
        knight.getStart();
        knight.solveTour();
        knight.displayBoard();
    }
}

class Knight {
    private int board[][];
    private int startRow;
    private int startCol;
    private int rowPos;
    private int colPos;
    private int moves;
    //Matrix of possible moves
    private int movesOption[][] = {
        {-2,1},
        {-1,2},
        {1,2},
        {2,1},
        {2,-1},
        {1,-2},
        {-1,-2},
        {-2,-1}
    };
    //Warnsdorff accessibility matrix
     final private int ACCESS[][] = {
        {0,0,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0,0,0},
        {0,0,2,3,4,4,4,4,3,2,0,0},
        {0,0,3,4,6,6,6,6,4,3,0,0},
        {0,0,4,6,8,8,8,8,6,4,0,0},
        {0,0,4,6,8,8,8,8,6,4,0,0},
        {0,0,4,6,8,8,8,8,6,4,0,0},
        {0,0,4,6,8,8,8,8,6,4,0,0},
        {0,0,3,4,6,6,6,6,4,3,0,0},
        {0,0,2,3,4,4,4,4,3,2,0,0},
        {0,0,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0,0,0}
    };

    public Knight() {}

    public void getStart() throws IOException{
        Scanner input = new Scanner(System.in);
        System.out.print("Enter starting row: ");
        startRow = input.nextInt() - 1;
        System.out.print("enter starting col: ");
        startCol = input.nextInt() - 1;
        System.out.println();
    }

    public void displayBoard() {
        System.out.println();
        for (int y = 0; y < board.length; y++) {
            for (int x = 0; x < board[y].length; x++)
                    System.out.printf("%02d ",board[y][x]);
            System.out.println();
        } 
        System.out.println("\nThe knight made " + moves + " moves");
    }

    private boolean getMove() {
        int moveID = -1;
        int numOfmove = 8;
        //go through each option in movesOption until one works.
        for (int x = 0; x < movesOption.length; x++) {
            if (rowPos + movesOption[x][0] >= 0 && rowPos + movesOption[x][0] < board.length) {
                if (colPos + movesOption[x][1] >= 0 && colPos + movesOption[x][1] < board[0].length) {
                    if (board[rowPos + movesOption[x][0]][colPos+movesOption[x][1]] == 0) {
                        if (ACCESS[rowPos + movesOption[x][0] + 2][colPos + movesOption[x][1] + 2] <= numOfmove) {
                            numOfmove = ACCESS[rowPos + movesOption[x][0] + 2][colPos + movesOption[x][1] + 2];
                            moveID = x;
                        }
                    }
                }
            }
        }

        if (moveID != -1) {
            board[rowPos+=movesOption[moveID][0]][colPos+=movesOption[moveID][1]] = ++moves;
            return true;
        }
        return false;
    }

    public void solveTour() {
        while (moves != 64) {
            moves = 0;
            board = new int[8][8];
            rowPos = startRow;
            colPos = startCol;
            board[rowPos][colPos] = ++moves;
            //Randomize the order of movesOption to change hierarchy of moves
            Random rnd = new Random();
            for (int s = movesOption.length - 1; s > 0; s--) {
                int index = rnd.nextInt(s + 1);
                int temp[] = movesOption[index].clone();
                movesOption[index] = movesOption[s];
                movesOption[s] = temp.clone();
            }
           //Plug and chug until something works
            while(getMove());
        }
    }
}

Answer 1

Improving the code

Some remarks about the code.

private boolean getMove() {
    int moveID = -1;
    int numOfmove = 8;
    //go through each option in movesOption until one works.
    for (int x = 0; x < movesOption.length; x++) {
        if (rowPos + movesOption[x][0] >= 0 && rowPos + movesOption[x][0] < board.length) {
            if (colPos + movesOption[x][1] >= 0 && colPos + movesOption[x][1] < board[0].length) {
                if (board[rowPos + movesOption[x][0]][colPos+movesOption[x][1]] == 0) {
                    if (ACCESS[rowPos + movesOption[x][0] + 2][colPos + movesOption[x][1] + 2] <= numOfmove) {
                        numOfmove = ACCESS[rowPos + movesOption[x][0] + 2][colPos + movesOption[x][1] + 2];
                        moveID = x;
                    }
                }
            }
        }
    }

Why not creating a function isValid, another for loop and then iterating through both of them just checking if isValid == true? Seems more elegant and sophisticated.

//Warnsdorff accessibility matrix
final private int ACCESS[][] = {
    {0,0,0,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0,0,0},
    {0,0,2,3,4,4,4,4,3,2,0,0},
    {0,0,3,4,6,6,6,6,4,3,0,0},
    {0,0,4,6,8,8,8,8,6,4,0,0},
    {0,0,4,6,8,8,8,8,6,4,0,0},
    {0,0,4,6,8,8,8,8,6,4,0,0},
    {0,0,4,6,8,8,8,8,6,4,0,0},
    {0,0,3,4,6,6,6,6,4,3,0,0},
    {0,0,2,3,4,4,4,4,3,2,0,0},
    {0,0,0,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0,0,0}
};

Why making this matrix having extra rows? I mean, the only time I've noticed you using it you have to increment both indexes by two, so it makes no sense.

import java.util.*;
import java.io.*;

Importing .* is not good, you should try to import only the methods you are using. You should also separate your file into different classes. But that's less important in a small piece of code such as yours.

        moves = 0;
        board = new int[8][8];
        rowPos = startRow;
        colPos = startCol;
        board[rowPos][colPos] = ++moves;
        //Randomize the order of movesOption to change hierarchy of moves
        Random rnd = new Random();
        for (int s = movesOption.length - 1; s > 0; s--) {
            int index = rnd.nextInt(s + 1);
            int temp[] = movesOption[index].clone();
            movesOption[index] = movesOption[s];
            movesOption[s] = temp.clone();
        }
       //Plug and chug until something works
        while(getMove());

You should also do linebreaks. Look at the code above. It would be way better with some line breaks, as it is below:

        moves = 0;

        board = new int[8][8];

        rowPos = startRow;
        colPos = startCol;

        board[rowPos][colPos] = ++moves;

        //Randomize the order of movesOption to change hierarchy of moves
        Random rnd = new Random();

        for (int s = movesOption.length - 1; s > 0; s--) {
            int index = rnd.nextInt(s + 1);
            int temp[] = movesOption[index].clone();
            movesOption[index] = movesOption[s];
            movesOption[s] = temp.clone();
        }

       //Plug and chug until something works
        while(getMove());

How to get to the solution faster

You seem to have used some sort of Warnsdorff Matrix heuristic (which I honestly didn't understand, but that's fine). But you definitely didn't used the heuristic to its fullest. What you have to do is picking the movement that leads to the biggest amount of subsequent movements. What does this means? If you have two choices of movements, one will allow you to move to 5 different places in the next round and the other one will allow you to move to 4 different places in the next round, move to the place that will give you more options.

It is basically pretending you made each possible play and seeing how it looks like after, to then choose the best option. The image bellow illustrate the process.

Answer 2

This is quite the first post you have here, I'm not too familiar with this problem, but since you welcomed improvements on etiquette, here goes:

Get in the habit of only importing the specific classes you need rather than entire libraries. For this code you need only:

import java.io.IOException;
import java.util.Scanner;
import java.util.Random;

You don't really need the empty constructor in your Knight class public Knight() {} it is the same as the default constructor java would automatically generate for you. Though this is minor and can be included as it is possibly convenient and extensible.

Consistency

Some areas you use spaces between your operators and others you don't, stick to one. Excepting unary operators, I'd opt for spaces, as it is conventional, and if it becomes horizontally unwieldy consider using more line breaks.

In your displayboard method you use loops in the outer loop but not the inner loop, why? Someone else running your code(me) might botch a paste job and get a completely unintended display, add braces and avoid ambiguity.

Line Breaks

Try to add some line breaks it improves readability, much like this post would be less readable if it was all one wall of text. Before and after loops and conditional checks, separate similar items' declaration, and unrelated formatting prints.

For example, Compare:

public void getStart() throws IOException{
        Scanner input = new Scanner(System.in);
        System.out.print("Enter starting row: ");
        startRow = input.nextInt() - 1;
        System.out.print("enter starting col: ");
        startCol = input.nextInt() - 1;
        System.out.println();
    }

to

public void getStart() throws IOException{
        Scanner input = new Scanner(System.in);

        System.out.print("Enter starting row: ");
        startRow = input.nextInt() - 1;

        System.out.print("enter starting col: ");
        startCol = input.nextInt() - 1;

        System.out.println();
    }

If nothing else if the empty spaces bother you they could act as a reminder to comment some sections.

The quadruple nested conditional is a behemoth that begs for refactoring if possible.

Not necessarily required here, but separate files for different classes help in maintainability going forward.

Answer 3

Use explicit imports rather than

import java.util.*;
import java.io.*;

This is bad practice, das there may be duplicates in the import and you are also importing unnecessary packages.