SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6 - OCEJPAD 6

How To Ask Questions How To Answer Questions

in what follows size is the size of the grid

1x1 has size = 1

2x2 has size = 2 ...

so I figured that every grid has a certain number of general paths (not routes) that can be easily found

1x1 has 2 paths

2x2 has 4 paths

3x3 has 6 paths

4x4 has 8 paths

5x5 has 10 paths and so on...

and in every grid

path 1 = path n

path 2 = path n-1

path 3 = path n-2 and so on...

and path 1 = path n = 1

the summation of all the paths is the number of routes...

take the 3x3 grid

path 1 = 1

path 2 = 3

path 3 = 6

path 4 = 6

path 5 = 3

path 6 = 1

I found out that

path 1 = path n = 1

path 2 = path n-1 = path 1 + (size - path 1) = 1 +(size-1) = size

BUT I cant figure out the general formula of path 3 !!!

how can I get path 3???

in a 3x3 grid, path 2 = 3, path 3 = 6

in a 4v4 grid, path 2 = 4, path 3 = 10

in a 5x5 grid, path 2 = 5, path 3 = 15

path 3 = path 2 + something or * something !!!

I just cant see it !!!

can anyone help now?

Your grid has a leading diagonal (at least that's what you call it in a matrix) top left->bottom right, and the other diagonal bottom left->top right (which I shall call "opposing diagonal"). Work out how many ways there are from top left to the opposing diagonal, then how many ways there are from bottom right to the opposing diagonal.

Some problems are so complex that you have to be highly intelligent and well informed just to be undecided about them. - Laurence J. Peter

At every point on your grid you have two options (right or down), except for the points located at the borders. The total number of paths from that point is then the total number of paths if you go down + the total number of paths if you go right (both if possible). At the bottom-right point there is only 1 path: direct to itself.

So you can calculate this using backtracking:

Here the size is the number of points, not the number of connections between points. So if size == 2, that means just a single square with 2 options.

Please note that I use long here - that's really necessary for 21 points (i.e. a 20x20 grid)

Around 35 you'll need to start using BigInteger.

[ March 25, 2008: Message edited by: Rob Prime ]

[ March 25, 2008: Message edited by: Rob Prime ]

[ March 25, 2008: Message edited by: Rob Prime ]

SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6 - OCEJPAD 6

How To Ask Questions How To Answer Questions

If you switch around the matrix, making (1,1) the point to go to, you can use one single matrix for multiple grid sizes; instead of returning matrix[0][0], you return matrix[size][size] (where size is again the number of points, starting at 1).

SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6 - OCEJPAD 6

How To Ask Questions How To Answer Questions

**Rob Prime: At every point on your grid you have two options (right or down), except for the points located at the borders. The total number of paths from that point is then the total number of paths if you go down + the total number of paths if you go right (both if possible). At the bottom-right point there is only 1 path: direct to itself.**

I haven't tried your code. But I'm surprised you found a backtracking solution that will actually complete for this problem. I ended up solving it with a calculator and a little googling about permutations. More specifically "permutations of indistinguishable elements".

Some problems are so complex that you have to be highly intelligent and well informed just to be undecided about them. - Laurence J. Peter

Output =

Result:35345263800

Some problems are so complex that you have to be highly intelligent and well informed just to be undecided about them. - Laurence J. Peter

Originally posted by Garrett Rowe:

But I'm surprised you found a backtracking solution that will actually complete for this problem.

I had an exercise in university that was quite similar, and this is how it was solved back then.

Originally posted by Garrett Rowe:

Rob, I just ran your code, and it is definitely fast, but there's a bug in there somewhere because it returns the wrong result unless of course I'm invoking it incorrectly.

...

Output =

Result:35345263800

As I said, my code takes the grid points as size, so you'll have to use 21 for the size, not 20.

SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6 - OCEJPAD 6

How To Ask Questions How To Answer Questions

Don't get me started about those stupid light bulbs. |