# Number of paths from a grid corner to visit all other points on a grid

Given an $$m \times n$$ grid of integer coordinates, how many paths can one start from a corner, say $$(0, 0)$$, and visit all other points? A path can end on any point.

For a start, I wrote a small script to traverse all possible paths of a $$2 \times n$$ grid. If only horizontal and vertical moves to neighboring points are allowed, the number of all possible paths seems to be $$n$$.

I extended the program a little bit to cover 8-connectivity i.e. a path can move diagonally. For $$n$$ from 1 to 9, the numbers of paths from my calculation are 1, 6, 20, 72, 240, 800, 2624, 8576, and 27904 (not in OEIS). All paths of a $$2 \times 5$$ grid are as follows. (Red dots indicate starting corner points.)

I did some quick searches on the problem. Self-avoiding walk seems to point to the right direction and there is probably no closed-form solution. However, all the examples in the reference and all sequences on OEIS frame the problem as the number of paths given a fixed length or given starting and ending nodes. I am not sure whether the 8-connectivity case is considered as self-avoiding either.

• You may be interested in graph theory elements. If the starting point wasn't fixed, the number you are looking for is the number of Hamiltonian paths in a king's graph. Here is the sequence of square grids: oeis.org/A158651 Feb 18 '20 at 18:49
• from the example you give, it seems that you are considering that the steps $(\Delta x , \Delta y)$ might only be in $[-1,1]^2 \ (0,0)$, is it so ? Feb 23 '20 at 15:49
• @GCab Yes, any consecutive pair in the path must be neighbors.
– puri
Feb 23 '20 at 17:55

Partial answers for the $$n \times 2$$ grid:

Without diagonal moves allowed, note that there's exactly one path ending in each row, so there are $$n$$ paths.

With diagonal moves allowed, classify paths as follows:

• Paths ending in the top row. It's easy to see that there are $$2^{n-1}$$ such paths.
• Paths whose first moves visit rows 1, 2 in that order (2 routes), followed by an arbitrary path in rows 2 through $$n$$.
• Paths whose first moves visit rows 2, 1, 2, 3 in that order (4 routes), followed by an arbitrary path in rows 3 through $$n$$.

This yields the recurrence $$x_{n+2}=2^{n+1}+2x_{n+1}+4x_n$$, so we have

$$\begin{pmatrix} x_{n+1} \\ x_{n+2} \\ 2^{n+1} \end{pmatrix} = \begin{pmatrix} 0&1&0\\4&2&2\\0&0&2 \end{pmatrix} \begin{pmatrix} x_n \\ x_{n+1} \\ 2^n \end{pmatrix}$$

so $$x_n$$ is the first element of $$\begin{pmatrix} 0&1&0\\4&2&2\\0&0&2 \end{pmatrix}^{n-1} \begin{pmatrix} 1\\6\\2 \end{pmatrix}$$.

You can efficiently exponentiate this matrix to compute values of $$x_n$$, or diagonalize it to obtain a closed-form solution.