[Math] Number of paths from A to B with no direction constraints

combinationscombinatoricsgraph theory

There's a fairly common problem finding paths which is usually stated something like this:

Consider a grid that is 4 rows by 4 columns with the
upper left corner named A and lower right corner named B.

Suppose that starting at point A you can go one step down or one step to
the right at each move. This is continued until the point B is
reached. How many different paths from A to B are possible?

This problem is very easy to solve. One Solution.

However, this problem becomes extraordinarily more difficult if we ignore the direction constraint:

you can go one step down or one step to the right at each move.

The only rule is that you cannot pass through the same cell twice.

Is it possible to determine the number of unique paths from A to B without simply trying every possible path?

Can we apply our solution to any n x n grid? What about any m x n grid?

(P.S. This is not a homework question. I came up with it a few hours ago and have been trying to solve it since.)

Best Answer

I believe this is the problem of counting self-avoiding rook walks, and for the square case, you can look here for the first few values at the OEIS here. Unfortunately it seems like there is no known closed-form expression for arbitrary $n$. There's some more information and references at Mathworld.

Related Solutions

[Math] Number of optimal paths through a grid with an ordered path constraint

Wrap RU with duct tape and consider it to be one character; there must be m of these. There must also be n-m U's not preceded by an R. (Hence $n \ge m$.) So there are $$\binom{n}{m} = \binom{n}{n-m}$$ acceptable arrangements.

[Math] Number of paths in a MxN matrix

If m==n you can find the no of paths to reach the bottom right cell from the top left cell using slight modification of Backtracking problem. Find below the code in Java.

public class Robot {
    private static int count = 0;
    public static void main(String[] args) {
        Robot robot = new Robot();
        int m = 5, n = 5;
        boolean Visited[][] = new boolean[5][5];
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++)
                Visited[i][j] = false;
        }
        robot.traverse(Visited, 0, 0, m, n);
        System.out.println(count);
    }
    /**
     * 
     * @param Visited array
     * @param index i
     * @param index j
     * @param max Row m
     * @param max column n
     */
    private void traverse(boolean Visited[][], int i, int j, int m, int n){
        if(i==m-1&&j==n-1){
            count++;
            return;
        }
        if(isSafe(i, j, m, n, Visited)){
            Visited[i][j]=true;
            traverse(Visited, i, j+1, m, n);
            traverse(Visited, i+1, j, m, n);
            traverse(Visited, i-1, j, m, n);
            traverse(Visited, i, j-1, m, n);
            Visited[i][j] = false;
        }
    }
    /**
     * 
     * @param index i
     * @param index j
     * @param max Row m
     * @param max Column n
     * @param Visited array
     * @return isSafe or not
     */
    private boolean isSafe(int i, int j, int m, int n, boolean Visited[][]){
        if(i>=0&&j>=0&&i<m&&j<n&&!Visited[i][j])
            return true;
        else
            return false;
    }

}

Best Answer

Related Solutions

[Math] Number of optimal paths through a grid with an ordered path constraint

[Math] Number of paths in a MxN matrix

Related Question