Number of paths connecting opposite corners?

Note about backtracking added at the end:

~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~

If you search O E I S for "grid paths"

https://oeis.org/search?q=grid+paths&language=engl...

the first hit is

https://oeis.org/A007764

" Number of non-intersecting (or self-avoiding) rook paths joining opposite corners of an n X n grid.

And the numbers grow very quickly.

1 - 5: 1, 2, 12, 184, 8512,

6 - 10: 1262816, 575780564, 789360053252, 3266598486981642, 41044208702632496804,

...

This refers to checkerboard type grids and moving from center to center,

rather than along the edges, and might be the ones you want.

n x n squares → (n+1) x (n+1) edges

Not sure if I met your constraints regarding non-intersecting.

I generated paths which don't reuse any edges.

Number of corners visited (1 fewer for number of edges traversed):

n ... shortest path .... longest path

2 ......... 3 ... . . . . . . . . . 3

3 . . . . . 5 . . . . . . . . . . . 7

4 . . . . . 7 . .. . . . . . . . ..19

For following the edges, I generated some small ones (2, 3, 4 sides on the grid)

and then looked up the numbers:

https://oeis.org/A013990

A013990 Edge-disjoint paths between opposite corners of n X n grid.

0, 1, 2, 3, ... 4, .......5 . . . . . . . . 6

1, 1, 2, 16, 800, 323632, 1086297184,

30766606427588, 7466577706821521924, 15681997226277809235573754

and so on.

> 2. is it possible to efficiently construct them and store them in an array?

A backtracking algorithm will construct them reasonably quickly,

but after (and possibly including) 5x5 it becomes impractical to store them in an array.

Here are the 2x2 and 3x3 squares.

2 x 2 is like this:

2 -- 3

| ... |

0 -- 1

The two paths are

0,1,3

0,2,3

3 x 3 is

6 --- 7 --- 8

| . . .| . . . |

3 --- 4 --- 5

| . . .| . . . |

0 --- 1 --- 2

The 16 paths are: (* = self-crossing (4))

0,1,2,5,4,3,6,7,8

0,1,2,5,4,7,8

0,1,2,5,8

0,1,4,3,6,7,8

0,1,4,3,6,7,4,5,8 *

0,1,4,5,8

0,1,4,7,6,3,4,5,8 *

0,1,4,7,8

0,3,4,5,2,1,4,7,8 *

0,3,4,5,8

0,3,4,1,2,5,4,7,8 *

0,3,4,1,2,5,8

0,3,4,7,8

0,3,6,7,8

0,3,6,7,4,5,8

0,3,6,7,4,1,2,5,8

Note that you really only have generate half of them,

because going left first generates half,

and going up first generates the other half,

and the two sets are easily in 1-1 correspondence.

I won't list the 800 4 x 4 paths or ...

If we eliminate self-crossing paths,

those reduce to 184, and the longest is

15 corners (14 edges traversed) as you stated.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Backtracking is well known algorithm for enumerating multi-part

solutions such as these.

Using the 3x3 grid above:

6 --- 7 --- 8

| . . .| . . . |

3 --- 4 --- 5

| . . .| . . . |

0 --- 1 --- 2

You start at 0.

From 0 you can go to 1 or 3.

So go to 1 and search from there, remembering where you have been.

From 1, you can go to 0, 4, or 2.

Already been to 0, so don't go there.

Try 2.

And you keep doing that until you either reach the goal (8)

or get stuck and can't proceed any further.

Then you backtrack to the previous point and see if there

are any other possibilities:

So after you have explored everything on the

0 - 1 - 2 - ... path,

you "backtrack" to 1,

and explore 0 - 1 - 4 - ...

It is easily implemented in any language that supports

recursion, which all the current languages (C, Perl, Java, etc) do.

My program is just 50 lines long, but with a little effort,

it could be even smaller than that.

For the small cases it runs in under 1 second.

See:

https://en.wikipedia.org/wiki/Backtracking

or

http://www.cse.ohio-state.edu/~gurari/course/cis68...

for explanations and examples.

(or any of many other sites which you can find by searching

on the term 'backtracking' or 'backtrack algorithm' or variations thereof).