Number of paths between points in a grid with blocked nodes?

Question

I'm working on a research project and I came across this problem. I was curious if there is a strategy to count the number of paths from A to B, using free nodes while avoiding the blocked nodes.

The starting point is always the bottom left-hand side corner, and the endpoint is always the top right-hand side corner. We can only move up or to the right.

Blocked nodes always appear on the top left-hand side corner of the grid. There is no free node on the left-hand side, or above any forbidden node.

I can find the answer using search algorithms, but that's not efficient, especially, with large scale problems. I was curious if there is a better mathematical expression/strategy for this problem. Thank you! This is an example:

Answer 1

One way to do this is by inclusion–exclusion.

It’s enough to exclude the bottom forbidden node in each column. In your example, these are the nodes $(0,2)$, $(1,2)$, $(2,4)$ and $(3,5)$. Denote the set of these nodes by $N$ and the number of paths that use all nodes in a set $S$ by $a_S$. Then by inclusion–exclusion the number of admissible paths is

$$ \sum_{S\subseteq N}(-1)^{|S|}a_S\;. $$

There are $\binom{x_2-x_1+y_2-y_1}{x_2-x_1}$ paths from $(x_1,y_1)$ to $(x_2,y_2)$. By inserting the forbidden nodes as intermediate steps, we can write the above sum as

$$ \sum_{S\subseteq N}(-1)^{|S|}\prod_{i=0}^{|S|}\binom{y_{s_{i+1}}-y_{s_i}+x_{s_{i+1}}-x_{s_i}}{x_{s_{i+1}}-x_{s_i}}\;, $$

where $s_1,\ldots,s_{|S|}$ are the nodes in $S$ in order of ascending $x$ coordinates, and $s_0=A$ and $s_{|S|+1}=B$.

In your example, this is

$$ \binom{10}5-\binom20\binom85-\binom31\binom74-\binom62\binom43-\binom83\binom22+\binom20\binom11\binom74+\binom20\binom42\binom43+\binom20\binom63\binom22+\binom31\binom31\binom43+\binom31\binom52\binom22+\binom62\binom21\binom22-\binom20\binom11\binom31\binom43-\binom20\binom11\binom52\binom22-\binom20\binom42\binom21\binom22-\binom31\binom31\binom21\binom22+\binom20\binom11\binom31\binom21\binom22 \\[15pt] =104\;. $$

Answer 2

Let $p(x,y)$ be the number of such paths from $(0,0)$ to $(x,y)$. By considering the last step into $(x,y)$, we find that $$p(x,y)=p(x-1,y)+p(x,y-1),$$ where $p(x,y)=0$ if $x<0$, $y<0$, or $(x,y)$ is blocked. The boundary condition is $p(0,0)=1$, and you want to compute $p(5,5)$.

\begin{matrix} 0 &0 &0 &0 &32 &\color{red}{104} \\ 0 &0 &0 &10 &32 &72 \\ 0 &0 &3 &10 &22 &40 \\ 0 &0 &3 &7 &12 &18 \\ 1 &2 &3 &4 &5 &6 \\ 1 &1 &1 &1 &1 &1 \\ \end{matrix}

Answer 3

Define $P_{x,y}$ as the number of way to reach point $(x,y)$ from$(0,0)$. We can reach point $(x,y)$ from $(x-1,y)$ or $(x,y-1)$. Therefore the following expression applies: $P_{x,y}=P_{x-1,y}+P_{x,y-1}$ . If You are allowed to use computer, it is very simple. For example, I use excel like below:

I just input $1$ in the bottom left cell, then $0$ in the blocked cells.

This may not be important but, a very special case is if the blocked cells form a triangle in the upper left corner, with the first blocked cell being $(0,a)$

The number of path from $(0,0)$ to $(x,y)$ become $\binom{x+y}{x}-\binom{x+y}{x+a}$

Answer 4

Let's say we have a lattice grid graph of size $n$. We now put obstacles on this graph with the following rule:
If we put an obstacle on a node, then we also put obstacles on all nodes north and west from it.

In other words, our obstacles always form a wall that segment the graph into a part that can be traveled through, and a part which is blocked.
Let's call the obstacle nodes that have no obstacle nodes the south or the east of it "outer obstacle nodes".

We can disassemble the original graph into a series of rectangle grid graphs (without obstacles):

We now count the paths from A to B using the edges between the rectangle grids.

An example path:

Let $(x_1,y_1), ..., (x_k,y_k)$ be the outer obstacle nodes.

If we have an $a\times b$ rectangle grid (i.e. $(0,0)$ to $(a-1,b-1)$), then there's $\binom {a+b}{a,b} = \binom{a+b}{a} $ ways to get from the south-west corner to the north-east-corner.
Similarly, we have that the number of paths from $(a_1,b_1) $ to $(a_2,b_2)$ is $$ \text{paths}(\pmatrix{a_1\\b_1},\pmatrix{a_2\\b_2}) := \binom{(a_2-a_1) + (b_2-b_1)}{a_2-a_1} $$

Using this, our recursion is: $$ P(x,y) = \begin{cases} \sum_{i=x_{\mu-1} +1}^x\text{paths}\left(\pmatrix{i\\y_{\mu-1}},\pmatrix{x\\y-1}\right)\cdot P(i,y_{\mu-1}) ,&\text{ if }\, \exists \mu: y = y_\mu \,\,\land\,\, x_\mu<x\le n \\ 1,&\text{ if } x=y=0 \\ \end{cases} $$ The first case depicts the situation that we are given a node that is at the bottom of one of the rectangle grids, and we trace the paths to this node back to the paths to the bottom nodes of the rectangle grid to the south.

By adding $(x_0,y_0) = (-1,0)$ and $(x_{k+1},y_{k+1}) = (n,n-1)$,
$P(n,n)$ gives us the number of paths from $(0,0)$ to $(n-1,n-1)$.

Formulating this recursion as dynamic program, one can achieve a runtime of $O(nk)$ (where $k$ is the number of outer obstacle nodes, for which always holds $k\le n$).