Interesting 8x8 chess board counting problem

[PsychonautQQ]

A standard 8x8 chess board has but a lone rook in the bottom left corner. A rook a piece than can move any number of spaces either horizontally or vertically. If the rook can only move up and to the right, how many possible paths does it have to the top right corner?

I think it's a pretty interesting problem. Anyone got a creative solution/explanation?

 

[mathman]

Quick guess. If it can move only one square at a time, there are $2^{14}$ possible routes.

 

[PsychonautQQ]

Yes, i believe that's correct for the restricted situation. Unfortunately, a rook can move more than one square at a time, it can move anywhere between 1 move and the rest of the way down the board.

 

[jbriggs444]

The 2¹⁴ result cannot be correct. It assumes that there are 14 independent choices to be made. But the choices are not independent. For instance, if you make 7 "up" moves in a row, the next 7 moves are constrained to be "right" moves. The number of possible 14-hop paths would pretty clearly be given by the number of combinations of 14 things taken 7 at a time.

If multi-square moves are legal, I see no immediate way to an analytical solution, but the problem is very tractable numerically. It's just a recursion in two variables that can either be iterated from the bottom up or memoized from the top down.

 

[PsychonautQQ]

Hmm, sounds like you know what you are talking about. Care to try to explain what you mean to a nooby like myself?

 

[jbriggs444]

If you've learned about permutations and combinations in school, the "combinations of 14 things taken 7 at a time" may be familiar. Think of it as having 14 numbers in a bag. You pick out seven of them and label them "up". The seven left in the bag are labelled "right". The resulting labels correspond to a one-step-at-a-time path across the chessboard. The number of distinct ways you can pick seven numbers from a bag of 14 is called the number of "combinations of 14 things taken 7 at a time". It is computed with factorials: $C(14,7) = \frac{14!}{7!\cdot7!}$

Edit: To be clear, the above is for the one-step-at-a-time version and what follows allows for the rook moves of one or more steps.

The number of ways of going corner to corner is found by considering every possible move and adding up the number of ways of going from corner to corner in the resulting, smaller rectangle. If you use f(n,m) to denote the number of ways of going from corner to corner on a n by m rectangle then...

f(1,1) = 1
and
f(n,m) = f(n-1,m) + f(n-2,m) + f(n-3,m) + ... + f(1,m) + f(n,m-1) + f(n,m-2) + f(n,m-3) + ... f(n,1)

By "iterating", I mean starting with a 1x1 rectangle and computing the number of ways to traverse that. Then use the above relationships to figure out how many ways of traversing a 1x2 and 2x1 rectangle. Then use those to figure out how many ways of traversing 1x3, 2x2 and 3x1 rectangles. Keep going until you hit 8 by 8.

By "memoizing", I mean doing computation as a recursive function call and optimizing it with memoization. That means that each time you make a recursive call, you write down (aka memorize) the result. This means that you only have to evaluate each rectangle once. Since there are only 64 possible rectangles up to 8x8, that only takes 64 memory cells.

http://en.wikipedia.org/wiki/Memoization

 

[Merlin3189]

Assuming you move only towards the target and don't backtrack, which would give a limitless answer, there seems to be a Pascal's triangle sort of pattern.
If the initial square is 1,1 and the target is 8,8, then the target can be reached
from 7,8 in 1 route, from 8,7 in 1 route and from 7,7 in 2 routes, then
from 6,8 in 1 route, from 8,6 in 1 route, from 6,7 via 6,8 or 7,7 in 3 routes, from 7,6 via 8,6 or 7,7 in 3 routes, from 6,6 via 6,7 or 7,6 in 6 routes,
and so on until 1,1 has 1458 routes.

 

[mathman]

jbriqqs is correct. Numerical value is 3432.

Note: I thought about while trying to sleep and came to the conclusion that it had to be the middle term of the expansion of $(1+1)^{14}$.

 

[DaveC426913]

up 7, right 7
up 6, right 7, up 1
up 6, right 6, up 1, right 1
up 6, right 5, up 1, right 2
up 6, right 4, up 1, right 3
up 6, right 3, up 1, right 4
up 6, right 3, up 1, right 5
up 6, right 2, up 1, right 5
up 6, right 1, up 1, right 6
up 5, right 7, up 2OK, I've gotten it started. That sets a minimum of eleven possibilities, but it's probably a lot more than that.

Now if someone wants to jump in and finish it, that'd be great. Many hands make light work.

 

[davidmoore63@y]

I got 3432 by the following method:
The number of paths that turn only once is 2 (fairly obvious)
The number of paths that turn twice is 12 (if wlog we start off to the right, there are only 6 places to turn upwards). Then we double the answer since we could have started upwards.
The number of paths that turn three times- this is equivalent to selecting a coordinate in the internal 6x6 square, so there are 36 ways. Again this must be doubled, so 72.
The number of paths that turn r times , if r is odd, is 2* (6Cs)^2, where s= (r-1)/2, because you need to select s coordinates on each axis to define the internal points on which to turn.
If r is even the formula is 2* (6Cu)*(6Cv), where u= r/2 and v=r/2-1, again corresponding to selecting coordinates in the internal 6x6 square for the turning points.
The highest value for r is r=13, where the path is a zigzag, and the number of paths is 2*(6C6)^2 = 2.
Adding all these up we get
2*(1+6C1^2 +6C2^2 +6C3^2 +...+6C6^2)
+2*(6C06C1 + 6C16C2+ 6C26C3+...+6C56C6)
= 3432.

What's interesting here is this is the same answer as if you say the rook can only move one square at a time, which is 14C7=3432 as stated by other responders. So the key insight is to point out it doesn't matter how far the rook can move, since the distinct paths created are the same. I'm not sure if jbriggs and mathman already had that point understood.

 

[PsychonautQQ]

Wow! Awesome replies! Anyone got any other explanations?

 

[PsychonautQQ]

jbriqqs is correct. Numerical value is 3432.

Note: I thought about while trying to sleep and came to the conclusion that it had to be the middle term of the expansion of $(1+1)^{14}$.

care to expand on your reasoning?

 

[mfb]

Rotate the board to get the rook to the top (with a corner there). The number of possible paths to a specific field is then given by the sum of the paths to the two fields above it. This leads to Pascal's triangle, and there is a convenient formula to calculate its entries.

 

[PsychonautQQ]

and by field you mean square? or are you thinking in higher algebraic terms?

 

[jbriggs444]

What's interesting here is this is the same answer as if you say the rook can only move one square at a time, which is 14C7=3432 as stated by other responders. So the key insight is to point out it doesn't matter how far the rook can move, since the distinct paths created are the same. I'm not sure if jbriggs and mathman already had that point understood.

I'd been going for the number of sequences of moves rather than for the number of paths.

 

[Merlin3189]

... and so on until 1,1 has 1458 routes.

Oops! Yes, it should come to 3432 as in 14C7. Must be a dud battery in my pencil!

 

[mfb]

and by field you mean square? or are you thinking in higher algebraic terms?

Square of the board.

I'd been going for the number of sequences of moves rather than for the number of paths.

Where is the difference?

 

[jbriggs444]

I'd been going for the number of sequences of moves rather than for the number of paths.

Square of the board.
Where is the difference?

In a sequence of moves, one can distinguish between a sequence of one step moves and a single multi-square sweep.

 

[mfb]

Ah right, forgot about that part.
That gives deviations from Pascal's triangle then, but it can be calculated square by square using a similar way, you just have to add more numbers.

 

[PsychonautQQ]

The number of ways of going corner to corner is found by considering every possible move and adding up the number of ways of going from corner to corner in the resulting, smaller rectangle. If you use f(n,m) to denote the number of ways of going from corner to corner on a n by m rectangle then...

f(1,1) = 1
and
f(n,m) = f(n-1,m) + f(n-2,m) + f(n-3,m) + ... + f(1,m) + f(n,m-1) + f(n,m-2) + f(n,m-3) + ... f(n,1)

I'm a bit concerned here. I thought that total number of ways to get to any square was the sum of the paths from the two squares before it? By that logic, shouldn't f(8,8) = f(7,8) + f(8+7) rather than f(8,8) = f(7,8) + f(6,8) + f(5,8) + ... + f(1,8) + f(8,7) + f(8,6) + f(8,5) + ... f(8,1)

 

[PsychonautQQ]

Also, can you help me understand why the answer is the same as 14 choose 7? Why doesn't the solution involve choosing 14? I mean, the rook has to move 14 squares, shouldn't there be 14 choices?

 

[PsychonautQQ]

One last question (by the way, thanks for all the help!) If I were to generalize this for any nxn board, I could just do 2(n-1) choose n-1?

 

[jbriggs444]

The total number of ways, (the sequence of rightward and upward rook moves) does not match the total number of paths.

From the lower left of an 8x8 chess board there are a total of 14 legal first moves.

 

[jbriggs444]

Also, can you help me understand why the answer is the same as 14 choose 7? Why doesn't the solution involve choosing 14? I mean, the rook has to move 14 squares, shouldn't there be 14 choices?

Once you have chosen the seven "up" steps, the remaining seven "right" steps are fixed. They are not available as independent choices.

 

[mathman]

Using the binomial theorem gives the clearest explanation. There are two kinds of move r (right 1) and u (up 1). It takes exactly 14 moves to go from lower left to upper right corner. All possible 14 move combinations can be represented by $(r+u)^{14}=\sum_{k=0}^{14}\binom{14}{k}r^k u^{14-k}$. However to get to the upper right corner you need 7 r's and 7 u's with the number of possibilities $\binom{14}{7}$.

This is a repeat of jbriggs444 - I hope it makes it clearer.

 

[PeroK]

Also, can you help me understand why the answer is the same as 14 choose 7? Why doesn't the solution involve choosing 14? I mean, the rook has to move 14 squares, shouldn't there be 14 choices?

Let's use a smaller 4x4 board to make it easier.

Imagine you have 6 counters, 3 marked Right and 3 marked Up. How many ways can you arrange these counters? It's $\binom{6}{3}$.

Examples are: RRURUU, URURRU etc.

Now, we can show that each arrangement of the counters represents a path for the rook. Take the first example. It represents the rook moving 2 squares Right, then Up 1, then Right 1, then Up 2.

And, every possible path can be represented by an arrangement of the counters. For example, Up 2, Right 3, Up 1 is UURRRU

So, the number of paths for the rook is equivalent to the number of arrangements of the counters.

In general, for an nxn board, you have $\binom{2n-2}{n-1}$ possibilities.

 

[mathman]

Also, can you help me understand why the answer is the same as 14 choose 7? Why doesn't the solution involve choosing 14? I mean, the rook has to move 14 squares, shouldn't there be 14 choices?

There are 14 choices, 7 up and 7 right. that's why the answer is $\binom {14}{7}$.

 

[DaanV]

Let's use a smaller 4x4 board to make it easier.

Imagine you have 6 counters, 3 marked Right and 3 marked Up. How many ways can you arrange these counters? It's $\binom{6}{3}$.

Examples are: RRURUU, URURRU etc.

Now, we can show that each arrangement of the counters represents a path for the rook. Take the first example. It represents the rook moving 2 squares Right, then Up 1, then Right 1, then Up 2.

And, every possible path can be represented by an arrangement of the counters. For example, Up 2, Right 3, Up 1 is UURRRU

So, the number of paths for the rook is equivalent to the number of arrangements of the counters.

In general, for an nxn board, you have $\binom{2n-2}{n-1}$ possibilities.

It's not entirely clear to me if the OP intends for there to be a difference in the number of moves required to get to top-right. I agree that the trajectory passed would be the same, but the number of moves could differ. Does this count as a different path?

To explain: in your first example (RRURUU), this trajectory could be done in 4 moves (Right 2, Up 1, Right 1, Up 2) up to 6 individual moves (Right 1, Right 1, Up 1, Right 1, Up 1, Up 1). And then 2 different options of completing this exact same trajectory in 5 moves. Does this count as 4 different paths or are they one and the same path, since they are they same trajectory?

 

[PeroK]

It's not entirely clear to me if the OP intends for there to be a difference in the number of moves required to get to top-right. I agree that the trajectory passed would be the same, but the number of moves could differ. Does this count as a different path?

To explain: in your first example (RRURUU), this trajectory could be done in 4 moves (Right 2, Up 1, Right 1, Up 2) up to 6 individual moves (Right 1, Right 1, Up 1, Right 1, Up 1, Up 1). And then 2 different options of completing this exact same trajectory in 5 moves. Does this count as 4 different paths or are they one and the same path, since they are they same trajectory?

That is, indeed, a different problem. If you define a path as simply the path drawn on the board, then the above solution applies. If, instead, you look for the number of different combinations of moves, then there are a lot more of these.

You could try to solve this by inserting an X counter where the rook stops. RR would be two spaces Right and RXR would be two moves of one space Right. But, I can't immediately see a way of counting those.

Alternatively, you could use the Pascal Triangle method, but the counting there gets tricky as well.

You should have a go at solving this problem and see whether you can find an inspired solution.

 

[HuskyNamedNala]

Wouldn't the answer be infinite? If there are no restrictions on the rook movement, couldn't one theoretically move "back and fourth" between any desired positions, then decide to move to the final square? I think there needs to be some more rules added, otherwise someone can just make a bunch of "useless" moves.

 

[DaveC426913]

Wouldn't the answer be infinite? If there are no restrictions on the rook movement, couldn't one theoretically move "back and fourth" between any desired positions, then decide to move to the final square?

Not if you read the opening post carefully.

I think there needs to be some more rules added

See above.

 

[HuskyNamedNala]

Not if you read the opening post carefully.
See above.

Ok, I think I have the answer then.

I believe the solution to this problem is directly related to integer partitions. Break the problem down like this:2 moves: {(8,8),(8,8)} or {(up, right),right,up)} P(16,2)
3 moves: {(7,8,1),(1,8,7),(7,8,1),(1,8,7), ...} or {(u,r,u),(u,r,u),(r,u,r),(r,u,r)...}
4 moves: {(7,7,1,1)...}
...
16 moves {(1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1)...}

It is pretty clear that the number of squares one can move must add up to 16 (8 up and 8 over). It is also clear that one cannot move any further than 8 squares and any less than 1. So the solution is basically the set of integer partitions of 16 that satisfy those two criteria. Now, granted, I am no good at combinatorics so I don't know what the number is, but I am good at figuring out what one has to do to get the number. Ill take my fields medal now please ;)

 

[DaveC426913]

It is pretty clear that the number of squares one can move must add up to 16 (8 up and 8 over).

Surely you mean 14 (7 up, 7 over).

 

[HuskyNamedNala]

Yeah, same thing different integer.

 

[mfb]

Alternatively, you could use the Pascal Triangle method, but the counting there gets tricky as well.

I don't see what would be tricky there. You have to sum up all numbers in the "row"/"column" above the square you are calculating, everything else stays the same.