13
$\begingroup$

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.

enter image description here

How many such paths are there?

$\endgroup$

closed as off-topic by xnor, Set Big O, Len, Rob Watts, Gamow Feb 14 '15 at 14:37

  • This question does not appear to be about creation and solving of puzzles, within the scope defined in the help center.
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 3
    $\begingroup$ A pawn cannot move right. $\endgroup$ – warspyking Oct 26 '14 at 14:53
  • 1
    $\begingroup$ 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. $\endgroup$ – BitNinja Oct 26 '14 at 20:57
  • 2
    $\begingroup$ 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. $\endgroup$ – mdc32 Oct 26 '14 at 21:39
  • 4
    $\begingroup$ @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. $\endgroup$ – David Richerby Oct 27 '14 at 11:20
  • 4
    $\begingroup$ 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. $\endgroup$ – xnor Feb 13 '15 at 17:12
18
$\begingroup$

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$. Also $N_A+N_B+2N_C = 14$. 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$ 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$

$\endgroup$
8
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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();
}
$\endgroup$
  • 2
    $\begingroup$ I'd use dynamic programming. $\endgroup$ – Gary Ye Jan 12 '15 at 19:54
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ nice method, so there's a concrete 1 in the bottom left is there? $\endgroup$ – d'alar'cop Oct 26 '14 at 15:04
  • $\begingroup$ @d'alar'cop yes, but actually the whole bottom row and leftmost column because of this. $\endgroup$ – mdc32 Oct 26 '14 at 15:09
  • $\begingroup$ 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? $\endgroup$ – Cruncher Oct 26 '14 at 15:41
  • $\begingroup$ @Cruncher N being the size of the board NxN? $\endgroup$ – mdc32 Oct 26 '14 at 15:51
  • $\begingroup$ @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/… $\endgroup$ – mdc32 Oct 26 '14 at 16:25
2
$\begingroup$

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.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.