It is well known that when one is allowed only to move right and down, the number of paths between the upper left cell and the bottom right cell of a rectangular grid with side lengths n,m is the binomial coefficient n+m on n. I tried to think, at first in a mathematical manner, about the number of such paths when one is also allowed to move left and up; obviously, the only way to give a meaningful answer to such a question is to count non-self-intersecting paths that do not go outside the rectangle (without those restrictions, the number of paths is infinite)

Since I had no idea how to count the number of such paths combinatorially, I wrote a Java program that counts such paths and prints the paths, which I restricted to square arrays. However, already in an array of size 3x3, the program prints only 9 paths, while checking the number of such paths manually gave 12 paths. Here is the program:

public class pathCalculator {

    public static int pathsCalculator(boolean[][] arr) {

        return pathsCalculator(arr, 0, 0, "");
    }

    public static int pathsCalculator(boolean[][] arr, int i, int j, String s) {
        if (i < 0 || i > arr.length - 1 || j < 0 || j > arr[0].length - 1) {
            return 0;

        } else if (arr[i][j] == false) {
            return 0;
        }
        if (i == arr.length - 1 && j == arr[0].length - 1) {
            s = s + "[" + (arr.length - 1) + "," + (arr.length - 1) + "]";
            System.out.println(s);
            return 1;
        } else {
            arr[i][j] = false;
            s = s + "[" + i + "," + j + "]";
            boolean[][] arr1 = new boolean[arr.length][arr.length];
            for (int n = 0; n <= arr.length - 1; n++) {
                for (int m = 0; m <= arr.length - 1; m++) {
                    arr1[n][m] = arr[n][m];

                }
            }
            return pathsCalculator(arr1, i + 1, j, s) + pathsCalculator(arr1, i - 1, j, s) + pathsCalculator(arr1, i, j + 1, s) + pathsCalculator(arr1, i, j - 1, s);

        }

    }

}

The boolean array that is checked is initialized in the main program to be a square of "true"'s.

The main ideas of the program are therefore:

• Recursion - each time the method calls four variations of itself, which correspond to the four possibilities of: moving down, up, right and left.
• Flagging forbidden cells - each time the path approaches a given cell, the program changes the cell's boolean value from true to false. The second if condition causes the program to return 0 in case we arrive at a forbidden cell (this indicates the path is self-intersecting).
• Creating copies of the original boolean array - to prevent the different paths from interacting with each other on the same board, in each recursive step, the previous boolean array values are copied into a new array.

So what is the problem with what I wrote? Why does it count only a part of the total number of paths?