Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Interesting 8x8 chess board counting problem

  1. Apr 24, 2015 #1
    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?
     
  2. jcsd
  3. Apr 24, 2015 #2

    mathman

    User Avatar
    Science Advisor
    Gold Member

    Quick guess. If it can move only one square at a time, there are [itex]2^{14}[/itex] possible routes.
     
  4. Apr 24, 2015 #3
    Yes, i believe thats 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.
     
  5. Apr 24, 2015 #4

    jbriggs444

    User Avatar
    Science Advisor

    The 214 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.
     
  6. Apr 24, 2015 #5
    Hmm, sounds like you know what you are talking about. Care to try to explain what you mean to a nooby like myself?
     
  7. Apr 24, 2015 #6

    jbriggs444

    User Avatar
    Science Advisor

    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
     
    Last edited: Apr 25, 2015
  8. Apr 25, 2015 #7

    Merlin3189

    User Avatar
    Gold Member

    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.
     
  9. Apr 25, 2015 #8

    mathman

    User Avatar
    Science Advisor
    Gold Member

    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 [itex](1+1)^{14}[/itex].
     
  10. Apr 25, 2015 #9

    DaveC426913

    User Avatar
    Gold Member

    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 2


    OK, 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.
     
  11. Apr 25, 2015 #10
    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.
     
  12. Apr 25, 2015 #11
    Wow! Awesome replies! Anyone got any other explanations?
     
  13. Apr 25, 2015 #12
    care to expand on your reasoning?
     
  14. Apr 25, 2015 #13

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    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.
     
  15. Apr 25, 2015 #14
    and by field you mean square? or are you thinking in higher algebraic terms?
     
  16. Apr 25, 2015 #15

    jbriggs444

    User Avatar
    Science Advisor

    I'd been going for the number of sequences of moves rather than for the number of paths.
     
    Last edited: Apr 26, 2015
  17. Apr 26, 2015 #16

    Merlin3189

    User Avatar
    Gold Member

    Oops! Yes, it should come to 3432 as in 14C7. Must be a dud battery in my pencil!
     
  18. Apr 26, 2015 #17

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    Square of the board.
    Where is the difference?
     
  19. Apr 26, 2015 #18

    jbriggs444

    User Avatar
    Science Advisor

    In a sequence of moves, one can distinguish between a sequence of one step moves and a single multi-square sweep.
     
  20. Apr 26, 2015 #19

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    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.
     
  21. Apr 26, 2015 #20
    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)
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Interesting 8x8 chess board counting problem
  1. Counting problem. (Replies: 7)

  2. Interesting Problem (Replies: 9)

  3. Interesting problem (Replies: 18)

  4. Chess problem (Replies: 13)

Loading...