I'm working on the Knight's Tour problem and I'm making a recursive solution for it. https://www.chess.com/terms/knights-tour-chess#:~:text=The%20knight's%20tour%20is%20a,same%20square%20more%20than%20once.
I have a matrix[8][8] and a method called knightMove(int currentRow, int currentColumn);. This method should add all possible moves that the knight can make from the current position into an array. If the value of the position of the possible move is equal to 0, then knightMove(newRow, newColumn) will be called again from the new position.
If it finds a dead end, then it will try the next possible move in the array in the previous call. If it runs out of previous array positions, it will try the next position in the array called before this one and so on. The program will only end when it finds the right solution to the problem.
Now comes my question, I'd like to avoid use so many 'ifs' to check whether a knight move goes out of table or not.
ArrayList <int[]> moves = new ArrayList<int[]>();
int[] arr = new int[2];
int max=8;
if (currentColumn-2 > 0){
if(currentRow - 1 > 0){
arr[0] = currentColumn-2;
arr[1] = currentRow-1;
moves.add(arr);
}
if(currentRow+1 < max){
arr[0] = currentColumn-2;
arr[1] = currentRow+1;
moves.add(arr);
}
}
if (currentRow-2 > 0){
if(currentColumn-1 > 0){
arr[0] = currentColumn-1;
arr[1] = currentRow-2;
moves.add(arr);
}
if(currentColumn+1 < max){
arr[0] = currentColumn+1;
arr[1] = currentRow-2;
moves.add(arr);
}
}
if (currentColumn+2 > 0){
if(currentRow-1 > 0){
arr[0] = currentColumn+2;
arr[1] = currentRow-1;
moves.add(arr);
}
if(currentRow+1 < max){
arr[0] = currentColumn+2;
arr[1] = currentRow+1;
moves.add(arr);
}
}
if (currentRow+2 > 0){
if(currentColumn-1 > 0){
arr[0] = currentColumn-1;
arr[1] = currentRow+2;
moves.add(arr);
}
if(currentRow+1 < max){
arr[0] = currentColumn+2;
arr[1] = currentRow+1;
moves.add(arr);
}
}
for (int[] c : moves){
// recursive logic...
}
I'm not interested in invalid positions. If the compiler can't access such invalid positions, it should just don't do anything with them, and not break my code. Focus on the ones that are really a valid position. I'd like do something like below, adding just the values of valid positions in an array (Utopic solution):
int[] temp = {
table[currentRow-2][currentColumn-1],
table[currentRow-2][currentColumn+1],
table[currentRow+1][currentColumn-2],
table[currentRow-1][currentColumn-2],
table[currentRow+2][currentColumn-1],
table[currentRow+2][currentColumn+1],
table[currentRow-1][currentColumn+2],
table[currentRow+1][currentColumn+2]
};
I want help to figure out a better approach to avoid accessing an invalid position in a matrix.
Here are the results of one of my many test runs.
Origin row: 3, column: 4
Move to row: 1, column: 5
Move to row: 1, column: 3
Move to row: 2, column: 6
Move to row: 2, column: 2
Move to row: 4, column: 6
Move to row: 4, column: 2
Move to row: 5, column: 5
Move to row: 5, column: 3
Origin row: 1, column: 1
Move to row: 0, column: 3
Move to row: 2, column: 3
Move to row: 3, column: 2
Move to row: 3, column: 0
Origin row: 7, column: 7
Move to row: 5, column: 8
Move to row: 5, column: 6
Move to row: 6, column: 5
Move to row: 8, column: 5
Origin row: 1, column: 7
Move to row: 0, column: 5
Move to row: 2, column: 5
Move to row: 3, column: 8
Move to row: 3, column: 6
Origin row: 7, column: 1
Move to row: 5, column: 2
Move to row: 5, column: 0
Move to row: 6, column: 3
Move to row: 8, column: 3
The first thing I did was create a Coordinate class. This allowed me to put the index out of bounds test in one place, in the Coordinate class.
The knightMove method figures out how many moves are valid, creates a Coordinates array, and returns the valid move coordinates.
Here's the complete, runnable code.
public class MoveKnight {
public static void main(String[] args) {
MoveKnight mk = new MoveKnight();
displayOutput(mk, 3, 4);
displayOutput(mk, 1, 1);
displayOutput(mk, 7, 7);
displayOutput(mk, 1, 7);
displayOutput(mk, 7, 1);
}
private static void displayOutput(MoveKnight mk, int row, int column) {
System.out.println("Origin row: " + row + ", column: " + column);
Coordinate[] output = mk.knightMove(row, column);
for (int index = 0; index < output.length; index++) {
System.out.println(" Move to row: " + output[index].getRow() +
", column: " + output[index].getColumn());
}
System.out.println();
}
public Coordinate[] knightMove(int currentRow, int currentColumn) {
Coordinate[] difference = { new Coordinate(-2, 1), new Coordinate(-2, -1),
new Coordinate(-1, 2), new Coordinate(-1, -2), new Coordinate(1, 2),
new Coordinate(1, -2), new Coordinate(2, 1), new Coordinate(2, -1) };
int count = 0;
for (int index = 0; index < difference.length; index++) {
Coordinate destination = new Coordinate(currentRow, currentColumn);
destination.incrementCoordinate(difference[index]);
if (destination.isValid()) {
count++;
}
}
Coordinate[] output = new Coordinate[count];
count = 0;
for (int index = 0; index < difference.length; index++) {
Coordinate destination = new Coordinate(currentRow, currentColumn);
destination.incrementCoordinate(difference[index]);
if (destination.isValid()) {
output[count++] = destination;
}
}
return output;
}
public class Coordinate {
private int column, row;
public Coordinate(int row, int column) {
setRowColumn(row, column);
}
public int getColumn() {
return column;
}
public int getRow() {
return row;
}
public void incrementCoordinate(Coordinate increment) {
this.row += increment.getRow();
this.column += increment.getColumn();
}
public void setRowColumn(int row, int column) {
this.row = row;
this.column = column;
}
public boolean isValid() {
return row >= 0 && row < 8 && column >= 0 && column < 8;
}
}
}