Optimizing this Knight's Tour

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

• Questions like this are what Code Review is for. Stack Overflow is for specific questions.
– DennisW
Feb 8 '15 at 20:32
• Welcome to Code Review! We hope you find your stay to be nice and comfortable, and that you get all the help you need. Feb 9 '15 at 3:51

Improving 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.

• I appreciate the amount of time you took to answer my question. I know etiquette is a big deal but my teacher doesn't have too much emphasis so I don't know most of what should done when writing code. My method of solving the tour is to search for the tile with least access to move to. I am currently trying your suggestion of having preference to tiles of higher access over less access. Again, I appreciate you taking the time to help out a new kid on the block. thanks! Feb 9 '15 at 6:27
• don't worry mate :), that's why the internet is for right? Feb 9 '15 at 8:19

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.

• Its awesome how much depth you guys give to your answer. I really appreciate the detail that you go into your answer. I didn't really learn the correct etiquette but hopefully I can fix that in time. thanks for the answer! Feb 9 '15 at 6:29

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.