1. Joined
    31 May '07
    Moves
    696
    01 Nov '07 07:42
    A queen is on a8. It can move down, right, or diagonally down-right. How many ways are there in which the queen can reach h1?
    IE. One way is Qa5, Qe1, Qh1.
    Another is Qh8, Qh1.

    How many ways are there on a 16/16 chess board to reach the bottom right?

    Or an X/X board?
  2. Standard memberwolfgang59
    howling mad
    In the den
    Joined
    09 Jun '07
    Moves
    45641
    01 Nov '07 18:39
    Originally posted by doodinthemood
    A queen is on a8. It can move down, right, or diagonally down-right. How many ways are there in which the queen can reach h1?
    IE. One way is Qa5, Qe1, Qh1.
    Another is Qh8, Qh1.

    How many ways are there on a 16/16 chess board to reach the bottom right?

    Or an X/X board?
    Pascall's Triangle?
  3. Standard memberTheMaster37
    Kupikupopo!
    Out of my mind
    Joined
    25 Oct '02
    Moves
    20443
    02 Nov '07 07:09
    Hmm, not quite I think. It'd be Pascal's Triangle if the queen could only move down and right.

    The Triangle is a good deal of the solution though.
  4. Joined
    02 Nov '07
    Moves
    509
    07 Nov '07 07:54
    assuming infinite moves?
  5. Account suspended
    Joined
    18 Mar '06
    Moves
    3118
    07 Nov '07 20:00
    Originally posted by doodinthemood
    A queen is on a8. It can move down, right, or diagonally down-right. How many ways are there in which the queen can reach h1?
    IE. One way is Qa5, Qe1, Qh1.
    Another is Qh8, Qh1.

    How many ways are there on a 16/16 chess board to reach the bottom right?

    Or an X/X board?
    infinite, assuming it can land on the same square more than once on its circuitous voyage.
  6. Joined
    07 Sep '05
    Moves
    35068
    07 Nov '07 21:12
    Originally posted by rubberjaw30
    infinite, assuming it can land on the same square more than once on its circuitous voyage.
    Only down and right - so the longest route will only take 14 moves.
  7. Standard memberPBE6
    Bananarama
    False berry
    Joined
    14 Feb '04
    Moves
    28719
    07 Nov '07 21:56
    Originally posted by wolfgang59
    Pascall's Triangle?
    Yes, a modified version. Instead of just adding the values north and west of the node, you need to add the value northwest of the node as well. Using this method, the number of ways for the queen to go from a8 to h1 by moving south, east or southeast is 48639.
  8. Joined
    12 Sep '07
    Moves
    2668
    05 Dec '07 23:44
    Here's a related problem. Suppose we have an mxn chessboard. A queen sits on the bottom-left, and can only move up right or diagonally up-right. Given this, A and B play the following game:
    A makes any move with the queen, then B does the same thing. The two players alternate moves, and the person who cannot make a move is the loser. Find a general winnings strategy for A or B.

    Some board sizes are a win for A, some are a win for B. e.g an nxn board is a win for A but a 2x3 board is a win for B.
  9. Joined
    31 May '07
    Moves
    696
    06 Dec '07 16:41
    Nice question.
    The simplest board (basic) is 6x6 for this. Where the player that moves to c1,e4,a3,d5 or f6 wins. Then if you continue, the next winning squares are calculated by applying half the relationship between f6 and the winning squares on 6x6 board to every other square.

    I.E. If we take the bottom right half, the winning squares on 6x6 are f6,e4 and c1. If we put this on a 10x10 board so these squares are J10, I8 and G5. The relationship between the first two (J10 and I8) is down two and left one, so if we assume g5 to be the new J10, the next winning square is f3. The relationship between the second two (I8 and g5) is down three and left two. So the next winning square is the theoretical D0.

    More taxing: If you have a game where there are two rooks on g8 and h8 and each player can only move one of the rooks left or down each move, and person who cannot move loses, how to win?
Back to Top