1
$\begingroup$

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

Paths of 2x5 grid

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.

$\endgroup$
  • 1
    $\begingroup$ 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 $\endgroup$ – NikoWielopolski Feb 18 at 18:49
  • $\begingroup$ 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 ? $\endgroup$ – G Cab Feb 23 at 15:49
  • $\begingroup$ @GCab Yes, any consecutive pair in the path must be neighbors. $\endgroup$ – puri Feb 23 at 17:55
2
+25
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.