Interesting 8x8 chess board counting problem

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