Interesting 8x8 chess board counting problem

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

 

[Stephanus]

To jbriggs444.
Good, good, good.
So in every element of the array, there is a number. And the number represents how many path to the solution. In the end it's a matter of memory vs process. I remember the case once in finding prime number.
Well, well, well, jbriggs444, you never cease to amaze me!.
I always find good explanations from you!.
I don't know whether you're a good scientist, physicist or a good computer programmer.
But one thing for sure, you're a damn GOOD TEACHER!. Bravo!

 

[Stephanus]

#!/usr/bin/perl
#
# Iterative approach. Populate n by n array
#

Foolish of me. Of course, perl!

 

[Stephanus]

for $i ( 1 .. $row-1 ) {
  $ways = $ways + $count[$i][$column];
};
for $i ( 1 .. $column-1 ) {
  $ways = $ways + $count[$row][$i];
};

I'm sorry jbriggs444,
I think that line of code should be changed to:

if ($Row>1) $ways = $ways + $count[$Row-1][$column];
if ($Col>1) $ways = $ways + $count[$Row][$column-1];

Thanks for your explanations!

For QueenMode

if ($Row>1) $ways = $ways + $count[$Row-1][$column];
if ($Col>1) $ways = $ways + $count[$Row][$column-1];
if ($QueenMode && ($Row>1) && ($Col>1)) $ways = $ways + $count[$Row-1][$column-1];

Ahhh, PhysicsForums is suck!
Why there's no "Pascal" option in insert code. From all languages, they have FORTAN!

 

[jbriggs444]

for $i ( 1 .. $row-1 ) {
  $ways = $ways + $count[$i][$column];
};
for $i ( 1 .. $column-1 ) {
  $ways = $ways + $count[$row][$i];
};

I'm sorry jbriggs444,
I think that line of code should be changed to:

if ($Row>1) $ways = $ways + $count[$Row-1][$column];
if ($Col>1) $ways = $ways + $count[$Row][$column-1];

That depends on what problem you are trying to solve. The program correctly solves the problem it was intended to solve. That problem being finding the number of distinct sequences of [eastward and northward] rook moves that can go from one corner to the other of an i by j chessboard.

If you want to determine the number of paths, the recurrence does indeed become much simpler. The distinction between the number of paths and the number of sequences of moves has been pointed out multiple times in this thread.

 

[Hitarth001]

You are on 1,1 to get on 8,8 you have to move 7 steps along x-axis and 7 steps along the y axis. Since we can't "back off" therefore whenever we will make a move we will add "1" to the value of x or that of y. Let's write "x" for move along x axis, and "y" for that along y axis. Now each possible path can be associated uniquely with a sequence of seven x's and seven y's. e.g., xxxyyyxyxyxyyx is one the possible path, fortunately there is one to one correspondence between the possible arrangement and no. of paths, now finding former is simple its just purmutation of 14 thing seven of one kind and rest of other kind, this no. is just equal to 14!/7!*7!.
On solving gives 3432.