Interesting 8x8 chess board counting problem

[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.

 

[jbriggs444]

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.

Yes. Coding up a computation along those lines (as alluded to in post #6) gives a total of 470,010 possible move sequences for an 8x8 square.

1: 1
2: 2
3: 14
4: 106
5: 838
6: 6802
7: 56190
8: 470010

 

[mfb]

I just get 10 for a 3x3 square. Here is a full list (notation should be clear, U=up R=right):

RRUU
RURU
RUUR
URRU
URUR
UURR
(2R)(2U)
(2U)(2R)
R(2U)R
U(2R)U

Or, as triangle:

    1
  1   1
1   2   1
  4   4
    10

 

[jbriggs444]

I just get 10 for a 3x3 square.

    1
  1   1
1   2   1
  4   4
    10

That triangle first fails in the 3x1 case where there are two traversals, not one.

2R
RR

Try instead:

    1
  1   1
2   2   2
  5   5
    14

 

[mfb]

Oh right, forgot about those.
(2R)UU
UU(2R)
RR(2U)
(2U)RR

 

[jbriggs444]

A Google search keyed on the numbers generated in #36 above yields a number of hits including:

http://www.combinatorics.net/conf/z60/sp/sp/chyzak.pdf

 

[Khashishi]

Sounds like a dynamic programming problem.

 

[Number Nine]

Any path to the top-right corner must consist of 7 "up" moves and 7 "right" moves, for a total of 14. Pick 7 spaces for the "up" moves for a total of 14 choose 7.

 

[firouzyan]

The same as @Number Nine said but the in the better way we can use this:
Make string with "U" and "R" like this:
"RRUURRUURRUURU"
This means two Right, two up,... . The string length must be 14 and use 7 "U" and 7 "R". For generating this string we have 14! possibilities but we have 2 set of 7 same sign! this mean if we change same sign we don't arrive something new! For this issue we divide this number by 7! for "U" and another 7! for "R" and this is the same result as \begin{pmatrix} 14 \\7 \end{pmatrix}

 

[PeroK]

The same as @Number Nine said but the in the better way we can use this:
Make string with "U" and "R" like this:
"RRUURRUURRUURU"
This means two Right, two up,... . The string length must be 14 and use 7 "U" and 7 "R". For generating this string we have 14! possibilities but we have 2 set of 7 same sign! this mean if we change same sign we don't arrive something new! For this issue we divide this number by 7! for "U" and another 7! for "R" and this is the same result as \begin{pmatrix} 14 \\7 \end{pmatrix}

Brilliant idea. But, I'm sure I've seen it somewhere before! It looks very familiar.

 

[firouzyan]

Brilliant idea. But, I'm sure I've seen it somewhere before! It looks very familiar.

Of Course You see that before in high school and discrete mathematics!

 

[PeroK]

Of Course You see that before in high school and discrete mathematics!

I was thinking perhaps someone posted it already earlier on this thread.

 

[marksman95]

If we leave aside the constriction of moving only up and right (we can move to all four directions), how many squares would take the longest path from (1, 1) to (8,8)?

Obviously it should be an even number, right?

62 steps?

EDIT: I meant without going twice through the same square

 

[Number Nine]

If we leave aside the constriction of moving only up and right (we can move to all four directions), how many squares would take the longest path from (1, 1) to (8,8)?

Obviously it should be an even number, right?

70 steps?

EDIT: I meant without going twice through the same square

There is a path using every square except 1, giving a path length of 63. I can't find one using every square, so I suspect that 63 is a maximum (if the board is nxn for n odd, then we can use every square, for a path of length n^2: just traverse the rows in a zig-zag pattern)

 

[marksman95]

Well, I wasn't counting the first one and (don't know why) counting an extra row/column. Without counting the first square, we could say that every path has an even number of squares right? Could this help us to compute the number of all possible paths in an optimized way (knowing that is a huge number)?

 

[Number Nine]

Well, I wasn't counting the first one and (don't know why) counting an extra row/column. Without counting the first square, we could say that every path has an even number of squares right? Could this help us to compute the number of all possible paths in an optimized way (knowing that is a huge number)?

The number of what kind of path?

 

[marksman95]

An elementary path (without repeating any of the squares) from (1,1) to (8,8)

 

[firouzyan]

An elementary path (without repeating any of the squares) from (1,1) to (8,8)

I Think the length is 62. This is even number of square so I think we can go through all square except one. this is my path:
"UUUUUUURBBBBBBBRUUUUUUURBBBBBBBRUUUUUUURBBBBBBBRRULURULURULURU"
"U" Up
"B" Bottom
"L" Left
"R" Right

And arrive Home!

 

[mfb]

Every move goes from a black square to a white one or vice versa. Using all fields would mean 63 steps, which is an odd number, which means start and finish would have different color => contradiction. Therefore, visiting all squares but one is optimal.
Please start a new thread if you want to discuss this in more detail.

 

[BruceW]

I was curious about this, so I looked it up. It seems there is a recurrence relation, for the n by n chess board sizes, given in the 2010 paper by M. Erickson et. al. "Enumerating rook and queen paths" in the journal "Bull. Inst. Combin. Appl." Which agrees with the answer 470010 for the 8by8 chessboard. But they also say that it is an open question whether there exists a combinatorial proof for the n by n chess board. But then, in 2012, there was a paper by Jin and Nebel, "A combinatorial proof of the recurrence for rook paths" in the electronic journal of combinatorics, where they apparently do give a combinatorial proof. So anyway, it looks like a combinatorial proof is not completely trivial ! Interesting though.

 

[Yashbhatt]

Have a look at this puzzle which is similar to yours(actually, it's the same except the chess board). https://www.khanacademy.org/math/re...es/brain-teasers/v/path-counting-brain-teaser

 

[Brage]

I think by far the easiest way to think of this is in terms of number of moves up and number of moves right and using combinations. If you want another fun way of thinking about it, the number of ways to get to (8,8) is the same as the number of way to get to (7,8) and (8,7) added together. This is turn is the number of ways to get to (6,8) and to (8,6) and twice to (7,7). Building up this way you get that there are 3432 ways to get to (1,1) and there is only 1 way to get to (1,1) so that is the answer.
Most people can probably tell that by now you have pascal's triangle imprinted on the chess board, starting from the uper left (8,8) at 1. Then as you have 14 possible first moves, this is the central term of $2^{14}$ which is 14C7. No new insight here of course, just a bit of a different way of thinking about the same problem, and relating different approaches together.

 

[Stephanus]

For 8 by 8 board, Rook: 3432, Queen: 48639
For 10 by 10 board, Rook: 48,620, Queen: 1,462,563
For 16 by 16 board it takes lot of time. I stop the program. That's where math beats the computer.

I don't know, I'm not a mathematician, I'm just a computer programmer. Can some one give the formula?
I failed at math in high school and college. That's why I choose computer programmer.


const
TargetX = 8;
TargetY = 8;
QueenMode = False;

var
Counter: Integer;

procedure Search(X, Y: Integer);
begin
if X<TargetX then begin
if Y<TargetY then begin
Search(X,Y+1); // Search Up
if QueenMode then Search(X+1,Y+1); // Search diagonal, queen mode
end;
Search(X+1,Y); // Search Right
end
else begin
if Y<TargetY then Search(X,Y+1) // Search right
else Inc(Counter); // Piece reaches target
end
end;

begin
Counter:=0;
Search(1,1);
Counter:=Counter;
end;

 

[jbriggs444]

For 8 by 8 board, Rook: 3432, Queen: 48639
For 10 by 10 board, Rook: 48,620, Queen: 1,462,563
For 16 by 16 board it takes lot of time. I stop the program. That's where math beats the computer.

The code that you display is a straight recursion. As mentioned in post #6 in this thread, that approach can be dramatically improved by memoization. Keep a cache of the results of search(x,y) in an n by n array. Every time you have a subroutine call, have the search() subroutine start by checking the cache. If a result is found, that result can be returned immediately. If a result is not found, it can be computed recursively and the appropriate cache entry populated.

Edit: I had only glanced at your code. Rather than having search(x,y) return the number of paths across an x by y rectangle, you have it actually traverse each such path and increment a global static count whenever it completes one. More conventionally, the recursion would return the number of paths found rather than updating a global variable.

The approach that I took for the somewhat more difficult version of the problem (the number of sequences of rook moves of 1 to n squares per move) used the other approach referred to in post 6 -- an iteration where all smaller rectangles are computed first and all bigger rectangles after. The traversal sequence from smaller to bigger is a simple raster scan.

#!/usr/bin/perl
#
# Iterative approach.  Populate n by n array
#
$limit = 16;
for $row ( 1 .. $limit ) {
  for $column ( $1 .. $limit ) {
    if ( $row == 1 && $column == 1 ) {
      $ways = 1
    } else {
      $ways = 0;
      for $i ( 1 .. $row-1 ) {
        $ways = $ways + $count[$i][$column];
      };
      for $i ( 1 .. $column-1 ) {
        $ways = $ways + $count[$row][$i];
      };
    };
    $count[$row][$column] = $ways;
  };
};
for $diagonal ( 1 .. $limit ) {
  print "$diagonal: $count[$diagonal][$diagonal]\n";
};

That code executes near instantly.

$ ./rook-move.pl
1: 1
2: 2
3: 14
4: 106
5: 838
6: 6802
7: 56190
8: 470010
9: 3968310
10: 33747490
11: 288654574
12: 2480593546
13: 21400729382
14: 185239360178
15: 1607913963614
16: 13991107041306

 

[Stephanus]

Wow, jbriggs444, it's neat and nice!.
Btw, what is your programming language called?
I remember you replied to me in Force vs Power. It surely gave me a good explanation!.

 

[jbriggs444]

Btw, what is your programming language called?

We are getting away somewhat from the subject matter of this thread. The programming language is called Perl. The only reason I used Perl was that it was handy. As the old saying goes, real programmers can write Fortran in any language.