After a long-long
time wanted to restart this blog and planning keep it updated with more problems/math
and algorithms.

**Problem**

Find the number of routes from the
top-left corner to the bottom right corner without backtracking in a 20x20
array. The example give is a 2x2 square. In this square, you can have around 6
routes from start point to end point.

How would you
start thinking about this problem? Start counting? You can never reach the
conclusion.

**Analysis**

As we have a useful condition that
we cannot backtrack, once we move forward in any direction we can never come
back. So, if we move in that angle, we get more routes passing through points
in forward direction. The first thing came to my mind is the points!!

If you count the points and tell that is the
total route, then you are wrong as a single point might lead to multiple routes
both vertical/horizontal. We started doing manual steps for 3x3. But at second
thought, what got into my mind is a graph!! If u have a unidirectional graph
all starting from one point and ending at the bottom right corner, can we then
calculate for 4x4, 5x5 etc. First I tried for a 3x3 the approach we got in
mind,

For each point,
how many route that is possible? I remembered my entire graph logic learned to
come up with this but was not sure whether this is right on 3x3 having total 20
routes. Moreover, writing in algorithm to implement this for 20x20 is
impossible!!

When I wanted to find the actual easiest way
to solve this, then came the forgotten mathematics concept: combinations.

**Solution**

As we know the routes are from
top-left corner to bottom-right corner, we can only move two ways, right or
down. For a 2x2, the various combinations possible are 6, RDDR, RRDD, RDRD,
DRDR, DDRR, DRRD. All this means that, we need to find how many possible ways 2
rights can be placed in total 4 sided route.

This can be done using combination
with 4 C 2 = 4! / 2! (2!) = 6. So for NxN, we always have this generic formula,
2N C N = 2N! / N! (2N-N)!.

Simply said, with
the above formula, you can easily get all the combinations. Then the analysis
we did? What is that? Can the problem be solved in that way? Yes. The approach
we got is nothing but Pascal’s triangle using acyclic graph method. It would
have taken years to complete it. J

## No comments:

## Post a Comment