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