Knights tour problem with an irregular chessboard

Question

the knights tour problem is a problem based on backtracking. In the normal version you have a N*N chessboard and you have to visit every single field on the board with your knight. But here comes the real problem: I can visit every field only once! So if i have no more fields to visit, i have to backtrack. At the end of your game, the number of fields should equals the number of movements. Now to my different version: I'm not working with a N*N chessboard, but with an irregular one. For example: The first row has 5 fields, the second one has 3, and the third one 8. These information are given me by a boolean array. There are also "false" fields that are not allowed to visit. I'm not allowed to change the boolean array.

public static boolean checkboard(boolean[][] board) {
        for (int i0 = 0; i0 < board.length; i0++) {

            boolean[] dim1 = board[i0];

            if (dim1 == null) {
                return false;
            } if (board.length == 1) {
                return false;
            }
        }
        return true;
    }

This is the first part of my code. It checks if the board (boolean array) is valid. That means it should give me false if at least one row is null or if there are no rows.

public static boolean checkPoint(boolean[][] board, int i, int j) {
        try {
            boolean test = board[i][j];

        } catch (IndexOutOfBoundsException a) {
            return false;
        }
        return true;
    }

This method checks if the point is in the array.

public static boolean isValid(int i, int j, int[][] sol, boolean[][] board) {
        if (i >= 0 && j >= 0 && sol[i][j] == -1 && board[i][j] != false && checkPoint(board,i,j)) {
            return true;
        }
        return false;
    }

Here are now some additional information: In the end i want an int array called "sol" that has the same chessboard like my boolean array "board". But in sol I save the number of movements. If there is an false in board, there has to be a 0 in sol. Here is an example of the sol array:

public static boolean springtour(int[][] sol, int i, int j, int step_count, int[] x_move, int[] y_move, boolean[][] board) {
        int counter = 0;
        for (int row = 0; row < sol.length; row++) {
            for (int col = 0; col < sol[row].length; col++) {
                if (board[row][col] == true) {
                    counter++;
                }
            }
        }
        if (step_count == counter) {
            return true;
        }
        for(int k=0; k<8; k++) {
            int nextI = i+x_move[k];
            int nextJ = j+y_move[k];

            if (isValid(nextI, nextJ, sol, board)) {
                sol[nextI][nextJ] = step_count;
                if (springtour(sol, nextI, nextJ, step_count+1, x_move, y_move,board)) {
                    return true;
                }
                    sol[nextI][nextJ] = -1;
            }
        }
        return false;
    }

So now here happens the backtracking. There is a maximum of 8 possible moves from a cell (i, j). Thus, I will make 2 arrays so that we can use them to check for the possible moves (called x_move and y_move). Thus if I am on a cell (i, j), I can iterate over these arrays to find the possible move i.e., (i+2, j+1), (i+1, j+2), etc. My next task is to move to the next possible knight's move and check if this will lead me to the solution. If not, then I will select the different move and if none of the moves are leading me to the solution, then I will return false.

public static int[][] solve(boolean[][] board, int startRow, int startCol) throws IllegalArgumentException {
        if (checkboard(board) == false || checkPoint(board,startRow, startCol) == false) {
            throw new IllegalArgumentException();
        }
        int[][] sol = new int[board.length][];
        for (int i = 0 ; i < board.length; i++) {
            sol[i] = new int[board[i].length];
        }
        for (int row = 0; row < sol.length; row++) {
            for (int col = 0; col < sol[row].length; col++) {
                if (board[row][col] == false) {
                    sol[row][col] = 0;
                }
                else {
                    sol[row][col] = -1;
                }
            }
        }
        int[] x_move = new int[]{2, 1, -1, -2, -2, -1, 1, 2};
        int[] y_move = new int[]{1, 2, 2, 1, -1, -2, -2, -1};

        sol[startRow][startCol] = 1;

        if(springtour(sol, startRow, startCol,1,x_move,y_move, board)) {
            return sol;
        }
        return null;
    }

Now to the last one. Here i will return the sol array. At first i check is there is everything fine with my board and the starting point of the knight. Then i create a sol array and fill it with -1 (or 0 if board is false). Then i have these two arrays with the possible moves x_move and y_move. I set the starting point to 1 and i call my method springtour to do the backtracking. If nothing works it returns null. My code is not working. There is an ArrayIndexOutOfBoundsException. Can someone help me with this? Maybe i have some other mistakes here. Thank you for helping!

Knights tour problem with an irregular chessboard

Answers (1)

Related Questions