- #51

- 16

- 2

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

- Thread starter PsychonautQQ
- Start date

- #51

- 16

- 2

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

- #52

- 3

- 1

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:An elementary path (without repeating any of the squares) from (1,1) to (8,8)

"UUUUUUURBBBBBBBRUUUUUUURBBBBBBBRUUUUUUURBBBBBBBRRULURULURULURU"

"U" Up

"B" Bottom

"L" Left

"R" Right

And arrive Home!

- #53

mfb

Mentor

- 35,150

- 11,398

Please start a new thread if you want to discuss this in more detail.

- #54

BruceW

Homework Helper

- 3,611

- 119

- #55

- 347

- 12

- #56

- 55

- 13

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.

- #57

- 1,316

- 104

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;

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;

Last edited:

- #58

jbriggs444

Science Advisor

Homework Helper

- 9,487

- 4,172

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

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.

Code:

```
#!/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";
};
```

$ ./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

Last edited:

- #59

- 1,316

- 104

Btw, what is your programming language called?

I remember you replied to me in Force vs Power. It surely gave me a good explanation!.

- #60

jbriggs444

Science Advisor

Homework Helper

- 9,487

- 4,172

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.Btw, what is your programming language called?

- #61

- 1,316

- 104

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!

- #62

- 1,316

- 104

Foolish of me. Of course, perl!#!/usr/bin/perl

#

# Iterative approach. Populate n by n array

#

- #63

- 1,316

- 104

Code:

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

I think that line of code should be changed to:

Code:

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

For QueenMode

Code:

```
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];
```

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

- #64

jbriggs444

Science Advisor

Homework Helper

- 9,487

- 4,172

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.I'm sorry jbriggs444,Code:`for $i ( 1 .. $row-1 ) { $ways = $ways + $count[$i][$column]; }; for $i ( 1 .. $column-1 ) { $ways = $ways + $count[$row][$i]; };`

I think that line of code should be changed to:

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

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.

- #65

- 1

- 0

On solving gives 3432.

- Last Post

- Replies
- 13

- Views
- 2K

- Last Post

- Replies
- 179

- Views
- 18K

- Last Post

- Replies
- 25

- Views
- 3K

- Last Post

- Replies
- 7

- Views
- 3K

- Last Post

- Replies
- 25

- Views
- 15K

- Last Post

- Replies
- 9

- Views
- 2K

- Last Post

- Replies
- 18

- Views
- 3K

- Last Post

- Replies
- 7

- Views
- 6K

- Last Post

- Replies
- 19

- Views
- 3K

- Last Post

- Replies
- 2

- Views
- 560