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