Printable View
Problem:
Imagine a King on an 8x8 chessboard.
It's located in a1, bottom left corner.
And it wants to get to a8, top left corner.
It can only move one step at a time, diagonally, vertically and horizontally.(Surprised)
How many different ways can it get there?
Is there a specific formula?
P.S Please tell me if there's a short way of doing it (or as an equation or formula), don't list all the possibilities.
thanks.
Quote:
Originally Posted by claws61
As you put the problem the answer is infinite ways, since the king can go up and down as often as
we want...
Perhaps the problem meant it to ask how many ways if the king cannot go back at any stage...
Tonio
I meant in 8 moves.
Sorry
Quote:
Originally Posted by claws61
Oh, a huge difference!(Rock) But then you're limited to just the first 5 columns (can you see why?)
so the problem can now be re-stated as follows:
suppose you have side by side 5 columns, each with 8 squares in it, and we want to know
how many ways there are to take a chip from the left inferior square to the top left
square in 8 steps, knowing that each step has to be either horizontal, vertical or
diagonal and between adyacent squares.
Further hint: decide from the beginning how many diagonal mover will be there, and count
according to this.
Tonio
I think this is quite a tricky counting problem. The minimum number of king moves to get from a1 to a8 is seven. To get there in seven moves, the king must move upwards, either vertically or diagonally, each time. So there are three possible moves: L (= diagonally left and upwards), V (= vertically upwards) and R (= diagonally right and upwards). Clearly the number of L moves must be the same as the number of R moves, and this number must be 0, 1, 2 or 3. There is an additional complication in that at no stage of the journey should the total number of L moves made up to that time be greater than the total number of R moves made up to that time. That is because the king starts and finishes on the leftmost file of the chessboard, and must not at any stage disappear off the left side of the board.
If the number of R moves is 0, then every move must be a V move, and there is only 1 such route.
If the number of R moves is 1, then there are 2 diagonal moves, first an R and later an L. There aresuch routes.
If the number of R moves is 2, then there are 4 diagonal moves, and there are two orders in which they can occur, namely RRLL or RLRL. Any other order would mean the king going off the left side of the chessboard. So in this case there arepossible routes.
Finally, if the number of R moves is 3, then there are 6 diagonal moves, and there are five orders in which they can occur. You can list these five possible orders if you want, but the significance of this number 5 is that it is the Catalan number C(3) (see property 5 in the list on that link page to understand why Catalan numbers are relevant here). So in this case there arepossible routes.
Thus the total number of king journeys from a1 to a8 in seven moves is. Is there a shorter way to get this result? I don't see one.
However, the problem here is to count the number of possible journeys in eight moves. If you think about it, it should be clear that exactly one of these eight moves should be horizontal (either to the left or to the right) and that the other seven moves must be a combination of types L, V and R. I have a suggestion for simplifying the counting process for this problem. The suggestion is to use the same procedure as for the seven-move case above, to list the number of possible routes (using only moves of types L, V and R) for getting from square a1 to a notional square a9 in eight moves. For each such route, you can then get an eight-move route from a1 to a8 by selecting one diagonal move and replacing it by a horizontal move (in the same horizontal direction).
Doing that, and using the fact that the Catalan number C(4) is 14, I found the total number of eight-move routes from a1 to a8 to beI'd be interested to know if other people get the same answer. (Mmm)
I computed 1,568 using a recursive function written in Python. The code is below. N(x,y,n) is the number of ways a king can get from (0,0) to (x,y) in exactly n moves. The idea is that in order to get to (x,y) in n moves, the king must move to an adjacent square in n-1 moves.
Code:def N(x, y, n):
if x == 0 and y == 0 and n == 0:
return 1
if x > n or y > n:
return 0
if x < 0 or y < 0:
return 0
if x > 7 or y > 7:
return 0
sum = 0
for i in [-1, 0, 1]:
for j in [-1, 0, 1]:
if i != 0 or j != 0:
sum = sum + N(x+i, y+j, n-1)
return sum
print N(0, 7, 8)