Determining if a knight can pass through all cells in a 2d array - if so print board

Question

I need an advice regarding this problem called "Knight Path". Given an n*n board whose cells are initialized to 0, I need to determine, given an arbitrary Knight's position, if the knight can pass through every cell on the board exactly once, where every cell the Knight had visited will be marked as counter, counting from: 1 - n^2. If a path is possible, I need to print the board. I need to print all the valid boards. The knight, for those who do not know the rules for chess, can move either up or down one square vertically and over two squares horizontally OR up or down two squares vertically and over one square horizontally.

For example given a 5*5 board, starting at (0,0) the method should print:

{{1,16,11,6,21},
{10,5,20,15,12},
{17,2,13,22,7},
{4,9,24,19,14},
{25,18,3,8,23}};

The above out put would be one of few, as there could be different other ways considering different initial positions. I've written the below code but it doesn't print anything. I need to spot the logic flaws here so I can make it work.

public class KnightDemo {

    static int counter = 1;
    public static void KnightPath(int[][] b, int i, int j) {
        b[i][j] = counter;
        if (counter == b.length * b[0].length) {
            printMatrix(b);
            return;
        } else {
            counter++;

            if (isValid(b, i - 1, j + 2) && b[i - 1][j + 2] == 0) {
                KnightPath(b, i - 1, j + 2);
            } else {
                return;
            }
            if (isValid(b, i - 2, j + 1) && b[i - 1][j + 1] == 0) {
                KnightPath(b, i - 2, j + 1);
            } else {
                return;
            }
            if (isValid(b, i - 1, j - 2) && b[i - 1][j - 2] == 0) {
                KnightPath(b, i - 1, j - 2);
            } else {
                return;
            }
            if (isValid(b, i - 2, j - 1) && b[i - 2][j - 1] == 0) {
                KnightPath(b, i - 2, j - 1);
            } else {
                return;
            }
            if (isValid(b, i + 2, j - 1) && b[i + 2][j - 1] == 0) {
                KnightPath(b, i + 2, j - 1);
            } else {
                return;
            }
            if (isValid(b, i + 1, j - 2) && b[i + 1][j - 2] == 0) {
                KnightPath(b, i + 1, j - 2);
            } else {
                return;
            }
            if (isValid(b, i + 1, j + 2) && b[i + 1][j + 2] == 0) {
                KnightPath(b, i + 1, j + 2);
            } else {
                return;
            }
            if (isValid(b, i + 2, j + 1) && b[i + 2][j + 1] == 0) {
                KnightPath(b, i + 2, j + 1);
            } else {
                return;
            }

        }
    }

    public static boolean isValid(int[][] a, int i, int j) {
        if (i > a.length - 1 || i < 0 || j > a[0].length - 1 || j < 0) {
            return false;
        }
        return true;
    }

    public static void main(String[] args) {
        int[][] b = new int[5][5];
        for (int i = 0; i < b.length; i++) {
            for (int j = 0; j < b[0].length; j++) {
                KnightPath(b, i, j);
            }
        }
    }
    
    public static void printMatrix(int[][] matrix) {
        for (int[] rows: matrix) {
            StringBuilder buff = new StringBuilder();
            buff.append("[");
            for (int i = 0; i < rows.length; i++) {
                int value = rows[i];
                buff.append(value);
                if (i < rows.length - 1) {
                    buff.append(", ");
                }
            }
            buff.append("]");
            System.out.println(buff.toString());
        }
    }
}

The output is

[1, 2, 3, 4, 5]
[6, 7, 8, 9, 10]
[11, 12, 13, 14, 15]
[16, 17, 18, 19, 20]
[21, 22, 23, 24, 25]

Answer 1

To solve for all paths, you need to reset the placed values of paths you've exhausted so that newer paths can access them. Additionally, your counter should reflect how deep you've gone, so that if you back out to try another path, your counter should roll back, too. I would recommend passing a counter as a parameter rather than using a static counter. Also, if you want to try all valid possibilities, then you need to avoid those return statements whenever one possibility is deemed invalid.

public static void KnightPath(int[][] b, int i, int j, int counter) {
    ...
        if (isValid(b, i - 1, j + 2) && b[i - 1][j + 2] == 0) {
            KnightPath(b, i - 1, j + 2, counter+1);
        }
    ...
    b[i][j] = 0;
}

public static void main(String[] args) {
    ...
            KnightPath(b, i, j, 1);
    ...
}