How many paths are there through a chess board? [closed]

Question

A pawn is placed on the lower left corner square of a standard 8 by 8 chessboard. A 'move' involves moving the pawn, where possible, either:

• one square to the right,
• one square up, or
• diagonally one square up and to the right.

Using these legitimate moves the pawn is to be moved along a path from the lower left square to the upper right square.

How many such paths are there?

Answer 1

Answer: 48639.

Prove: Let's number moves like this:
A) one square to the right
B) one square up
C) diagonally one square up and to the right

We can consider set of moves, that leads to the other corner. For example, CCCCCACB.
It is obvious that for any set like this the numbers of A-moves and B-moves must be always the same: $N_A=N_B$ (Otherwise you will not end in the upper right corner). Also $N_A+N_B+2N_C = 14$ (The maximum number of moves is 14 and C can take values from 0 to 7). And that is all limitations on the sets, so we need to find all sets of A,B and C, that satisfy to these two equations.

Let's consider 8 cases, each corresponds to different $N_C$ (from 0 to 7).
If $N_C = M$, then $N_A=N_B=7-M$ (A and B cannot take more than 7 steps each) and in total we have $14-M$ moves. There are $14-M \choose M$ possible placements for C-s and, once C are placed, $14-2M \choose 7-M$ possible placements for B-s and, once B are placed too, only one possible placement for A-s. So we have ${14-M \choose M} \cdot {14-2M \choose 7-M}$ possible sets with $M$ C-s.

In total we will have:

$\sum_{M=0}^{7}{14-M \choose M} \cdot {14-2M \choose 7-M} = $
${14 \choose 0}\cdot{14 \choose 7} + {13 \choose 1}\cdot{12 \choose 6} + {12 \choose 2}\cdot{10 \choose 5} + {11 \choose 3}\cdot{8 \choose 4} + $
$ + {10 \choose 4}\cdot{6 \choose 3} + {9 \choose 5}\cdot{4 \choose 2} + {8 \choose 6}\cdot{2 \choose 1} + {7 \choose 7}\cdot{0 \choose 0} = 48639$

Answer 2

Delannoy numbers

The solution for a $n+1$ by $m+1$ grid is given by Delannoy numbers

$D(n,m) = \Sigma_{d=0}^{n} \ ^mC_d \ ^{n+m-d}C_m$

note this assumes n<=m, we can easily express the dimensions either way round to achievement this

Derivation

There are 3 possible moves, $(1,0), (0,1)$ or $(1,1)$

for $n+1$ by $m+1$ board we must move a total of $(n,m)$ this is made using using any combination of the 3 moves such that:

$num(1,0) +num(1,1) = n$
$num(0,1) + num(1,1) = m$

we can decide how many of $(1,0)$ and $(0,1)$ to use based on the numebr of $(1,1)$s

Starting with diagonal moves

As n is the smaller dimension there are between 0 and n $(1,1)$s (diagonal moves) in any solution

so lets look at how they can be arranged (ignoring the other entries)

• for 0 $(1,1)$s there is 1 (or $\ ^nC_0$) possible arrangement
• for 1 $(1,1)$s there are $\ ^nC_1$ possible arrangements

and so on until

• for n $(1,1)$s there are $\ ^nC_n$ possible arrangements

in generality

• for $d$ (1,1)s there are $\ ^nC_{d}$ possible arrangements
• and d must fall between 0 and n (inclusive)

so there are in total $\Sigma_{d=0}^{n} \ ^kC_d$ possible locations for moves of $(1,1)$ in an $n+1$ by $m+1$ grid.

Now the non-diagonal moves

For each of these numbers of (1,1)s there is also many ways to arrange the (0,1)s and (1,0)s

For 0 $(1,1)$s

• there must be $n (1,0)$s out of a total number of moves of $n+m$
• i.e. there must be $n (1,0)$s and $m (0,1)$s

so there is $\ ^{n+m}C_m $ possible arrangements

Now for $1 (1,1)$

• there must be $n-1 (1,0)$s out of a total number of positions of $n+m-2$,
• i.e. there must be $n-1 (1,0)$s and $m-1 (0,1)$s
• one position is already $(1,1)$ so there are $n+m-1$ locations that can be taken

There are $\ ^{n+m-1}C_m$ possible arrangements of $(0,1)$ and $(1,1)$ for each location of the one $(1,1)$.
Giving $\ ^nC_1 \ ^{n+m-1}C_m $ arrangements possible for 1 diagonal move

In generality for $d (1,1)$s There are $\ ^nC_d \ ^{n+m-d}C_m $ possible arrangements
where $d$ must again be between $0$ and $n$

So summing over all $d$ gives the overall total number of paths and gives the formula given at the beginning

$D(n,m) = \Sigma_{d=0}^{n} \ ^mC_d \ ^{n+m-d}C_m$

for 8 by 8, n=7 and m = 7 the solution as given by others is 48639

Answer 3

Yes, the answer is 48639. I found it using a simple C++ code:

int move(int a=1,int b=1)
{
    if((a==8)||(b==8))
        return 1;
    return move(a+1,b)+move(a,b+1)+move(a+1,b+1);
}
int main()
{
    cout<<move();
}

Answer 4

Based on your rules, I think the answer is

48639
I did this in excel, adding up the three cells below, to the left, and diagonally to the lower left of each cell.

Answer 5

Here's a simple python script that solves the problem:

def path_count(rows, cols):
    if rows == 1 or cols == 1:
        return 1
    return path_count(rows-1, cols) + path_count(rows, cols-1) + path_count(rows-1, cols-1)

The idea behind this is that there are three possible first moves: up, right, and diagonally. For each first move, count the number of ways from the second square to the goal. This is equivalent to solving the original problem on a smaller board. The number of paths with up as the first move is equal to the number of paths on a 7-row by 8-column board. This lends itself to recursion since the board is always getting smaller with every move. If the board shrinks to one row or one column, then there's only one path, straight across or straight up to the goal. The solution is the number of paths with first move up, plus the number with first move right, plus the number with first move diagonal.

path_count(8,8) returns 48,639.

Note: I am well-aware that the function above would need to be optimized to handle much larger boards. For 8x8, the run time is less than a second. For 20x20, I stopped the program after several minutes.