Results 1 to 6 of 6

Math Help - Chessboard problem

  1. #1
    Newbie
    Joined
    Mar 2011
    Posts
    2

    Question Chessboard problem

    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.

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Quote Originally Posted by claws61 View Post
    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.

    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.



    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Mar 2011
    Posts
    2
    I meant in 8 moves.
    Sorry
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Quote Originally Posted by claws61 View Post
    I meant in 8 moves.
    Sorry

    Oh, a huge difference! 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
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    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 are {7\choose2} = 21 such 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 are {7\choose4}\times2 = 56 possible 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 are {7\choose6}\times5 = 35 possible routes.

    Thus the total number of king journeys from a1 to a8 in seven moves is 1+21+56+35 = 113. 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 be 1,\!568. I'd be interested to know if other people get the same answer.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    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)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Chessboard problem. Olympiad question.
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: March 10th 2012, 08:16 AM
  2. chessboard problem
    Posted in the Statistics Forum
    Replies: 2
    Last Post: January 5th 2011, 01:00 AM
  3. easy chessboard problem
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: August 23rd 2010, 01:09 PM
  4. chessboard problem
    Posted in the Math Topics Forum
    Replies: 4
    Last Post: January 24th 2009, 06:02 AM
  5. Chessboard Problem!
    Posted in the Math Challenge Problems Forum
    Replies: 5
    Last Post: October 22nd 2006, 06:45 PM

Search Tags


/mathhelpforum @mathhelpforum