patternjavaMinor
Optimizing this Knight's Tour
Viewed 0 times
thistourknightoptimizing
Problem
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;
```
//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;
Solution
Improving the code
Some remarks about the code.
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.
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.
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.
You should also do linebreaks. Look at the code above. It would be way better with some line breaks, as it is below:
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.
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 = 0 && rowPos + movesOption[x][0] = 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.
Code Snippets
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;
}
}
}
}
}//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}
};import java.util.*;
import java.io.*;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());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());Context
StackExchange Code Review Q#79995, answer score: 6
Revisions (0)
No revisions yet.