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

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?

• A pawn cannot move right. Oct 26, 2014 at 14:53
• I would suggest that the piece be a king instead of a pawn, as @warspyking said, pawns cannot move horizontally (or, as I would add,) diagonally unless they're taking a piece. Kings can do All these things, and this doesn't effect the answer. Oct 26, 2014 at 20:57
• Are any of these answers correct? If so, accept one of them, as this will give both you and the owner of the accepted answer a boost in reputation. Oct 26, 2014 at 21:39
• @skv Actually, it's more like an undergraduate combinatorics (mathematics) exercise. The phrasing as a chess problem is, frankly, unhelpful, since chess has no piece that moves in the way described in the question. Oct 27, 2014 at 11:20
• I'm voting to close this question as off-topic because it is a standard combinatorial problem solved by mathematical techniques with no puzzling spark.
– xnor
Feb 13, 2015 at 17:12

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$$

## 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

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();
}

• I'd use dynamic programming. Jan 12, 2015 at 19:54

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

• nice method, so there's a concrete 1 in the bottom left is there? Oct 26, 2014 at 15:04
• @d'alar'cop yes, but actually the whole bottom row and leftmost column because of this. Oct 26, 2014 at 15:09
• This is how I did it too (except by hand, good idea with excel). I wonder if we can get a closed form mathematical formula for this for arbitrary n? Oct 26, 2014 at 15:41
• @Cruncher N being the size of the board NxN? Oct 26, 2014 at 15:51
• @Cruncher WolframAlpha has this as its formula. I'm only in Algebra 2 so I don't really understand it, or I'm just over thinking it. - wolframalpha.com/share/… Oct 26, 2014 at 16:25

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.