Subscribe via feed.

## Chess moves

Posted by Chris on July 13, 2010 – 4:39 pm

Starting at the bottom left-hand corner of a chessboard, how many different ways are there of moving to the top right-hand corner if

(a) You can move only one square at a time and
(b) You can move bottom to top, left to right or a diagonal combination of the two? (Each counts as one move))

This post is under “MathsChallenge” and has 16 respond so far.

### 16 Responds so far- Add one»

1. 1. Nathan Said：

It looks likes this problem if closely related to the Catalan numbers, though with more possible solutions because of the diagonal movements allowed.

2. 2. John24 Said：

3^49 * 2^14 is my guess.

This is because every square on the board has 3 possible moves except the far right 8 squares and the top 8 squares (which both contain the upper right square, which has no possible moves).

3. 3. slavy Said：

Hi, Chris. I have a question regarding the diagonal moves – so if we make an up move and then a right move, do we have the freedom to choose whether these are two moves or one diagonal one, or it is always the second type?

4. 4. Chris Said：

An up followed by a right is distinct from a diagonal.

5. 5. Anonymous Said：

Chess Moves

Starting at the bottom left-hand corner of a chessboard, how many different ways are there of moving to the top right-hand corner if

(a) You can move only one square at a time and
(b) You can move bottom to top, left to right or a diagonal combination of the two? (Each counts as one move))

Given an 8×8 board start at 1,1

it requires 7 Up or “U” moves and 7 right or “R” moves. A diagonal “D” move will replace one U and one R move.

With 0 D moves UUUUUUURRRRRRR and all it’s permutations get to the “finish”
#permutations= 14!/(7!*7!*0!)=3432

With 1 D moves DUUUUUURRRRRR and all it’s permutations get to the “finish”
#permutations= 13!/(6!*6!*1!)=12012

With 2 D moves DDUUUUURRRRRR and all it’s permutations get to the “finish”
#permutations= 12!/(5!*5!*2!)=16632

with 3 D moves DDDUUUURRRR and all it’s permutations get to the “finish”
#permutations= 11!/(4!*4!*3!)=11550

with 4 D moves DDDDUUURRR and all it’s permutations get to the “finish”
#permutations= 10!/(3!*3!*4!)=4200

with 5 D moves DDDDDUURR and all it’s permutations get to the “finish”
#permutations= 9!/(2!*2!*5!)=756

with 6 D moves DDDDDDUR and all it’s permutations get to the “finish”
#permutations= 8!/(1!*1!*6!)=56

with 7 D moves DDDDDDD and all it’s permutations get to the “finish”
#permutations= 7!/(0!*0!*7!)=1

Sum of all these results=3432+12012+16632+11550+4200+756+56+1=48639

Given the choice of U,D,R moves there are 48639 way of going from bottom left corner of a chess board to the upper right corner.

Cam

6. 6. slavy Said：

I agree with Cam

7. 7. Chris Said：

Nice one Cam. I hadn’t expected that analysis. 48639 it is.

There is another way. It will give all the numbers of paths for all the rectangular chess boards in one table. e.g. for a 2*3 chess board. And it can be readly extended to larger boards.

8. 8. Chris Said：

Unless you specify that you can’t touch the same square twice or anything the moves are infinite. You can keep moving around the chess board.

9. 9. Chris Said：

@Chris (other). It is not possible to visit a square more than once with the given rules.

10. 10. tullotoe Said：

I apologize for being dumb, but I am not seeing how Cam goes from 3432 on an 8×8 board to 12012 on a 7×7 board and 16632 ona 6×6 board.

Not really appreciating your | notation, and simply contemplating the problem, I find it har to believe the solutions increate as the effective board decreases.

Could you please be more eplicit with your solution for the slower among us?

11. 11. Chris Said：

@tullotoe. Cam was only using a 8×8 board. He was considering all paths across the board when 7 diagonal moves were made, then when exactly 6 diagonal move was made etc., all the way through to 0 diagonal moves were made.

For 7 diagonal moves there is only 1 path (of 7 steps) and that’s taking the diagonal straight line from the bottom left to the top tight corner.

If no diagonal moves are made, then each path will have 7 up and 7 right moves to get to the other corner (14 moves in total); they can be taken in any order. If you make 1 diagonal move, then you need 6 up and 6 right moves (13 in moves total). Each diagonal move takes away 1 up and 1 right move. All Cam was doing is calculating the combinations and adding them together.

If D, U and R are the number of moves of each type taken, then the number of paths that can be chosen is: (14-D)!/(U! * R! * D!). NB U = R = (7-D) in all cases, so you end up with (14-D)!/((7-D)! * (7-D)! * D!). I could have written U+R+D instead of 14-D. e.g. If D = 3, then the total number of paths is 11!/(4! * 4! * 3!)

That lot has to be summed for D = 0 to 7 to get the grand total number of possible paths. Does that help you?

PS I have re-examined this page, I think Cam’s explanation is clearer than mine, but ‘ll leave it just in case …

12. 12. Chris Said：

… taking the case of 6 D, and 1 U and 1 R we have DDDDDDUR, DDDDDDRU, DDDDDRDU, DDDDDRUD, DDDDDURD, DDDDDUDR … and that goes on to give 56 (unique) combinations altogether.

13. 13. Chris Said：

Another way to do this is to start at the bottom left corner and consider how many ways there are to get to the current square. You can then buid up the number of paths by adding the number of paths from the left, backward diagonal and below square. I’ve padded with 0s to get the layout right.

1 15 113 575 2241 7183 19825 48639
1 13 085 377 1289 3653 08989 19825
1 11 061 231 0681 1683 03653 07183
1 09 041 129 0321 0681 01289 02241
1 07 025 063 0129 0231 00377 00575
1 05 013 025 0041 0061 00085 00113
1 03 005 007 0009 0011 00013 00015
1 01 001 001 0001 0001 00001 00001

The numbers represent the number of paths that can be found to get to the given square.

These numbers are known as Delannoy numbers. http://mathworld.wolfram.com/DelannoyNumber.html

14. 14. Anonymous Said：

Wow, I really like that method Chris. It’s a peace of cake to use that on a spreadsheet for any size rectangle, and it’s nice that it’s iterative.

I don’t think it would be my choice of method by hand, but with a computer, I think I’d use your method. I think being able to see the numbers build up in a meaningful way makes the result easier to understand, and to verify. Nice job.

Cam

15. 15. Chris Said：

Hi Cam. Thank you for the compliment. I came up with it as the method by hand.

Here’s the (copy and pasted) rest of what I know:
I did a Google with “48639 chess” and came across a paper that showed the expression corresponding to the “squared” Pascal’s triangle is:
g(n,r) = Sum[a=0 to r, 2^a * c(n,a) * c(r,a)]

where c(a,b)=a!/((b-a)!b!)

The result we want is g(7,7)=48639

There’s a link (near the top left) to a pdf and djvu copy of the paper.

Here’s my Mathematica code and output (going to 9*9 board):
For[n = 0, n < 9, n++,
Print[Table[
Sum[2^a Binomial[n, a] Binomial[r, a], {a, 0, n}], {r, 0, n}]]]

{1}
{1,3}
{1,5,13}
{1,7,25,63}
{1,9,41,129,321}
{1,11,61,231,681,1683}
{1,13,85,377,1289,3653,8989}
{1,15,113,575,2241,7183,19825,48639}
{1,17,145,833,3649,13073,40081,108545,265729}

Greetz

16. 16. Chris Said：

@tullotoe. I just re-read your comment. Cam is using an exclamation mark ! (not a |). ! is the factorial symbol. e.g. 5! = 5*4*3*2*1.

Special case(s) are 1! = 1 and 0! = 1 (surprisingly).

This site seems to be using the “MS Reference Sans Serif” font (9 point). It is horrible for maths.