6
$\begingroup$

I started with a 4x4 grid (although I want to eventually generalize for an n x n grid). You must move through a grid on the squares, not on the grid lines.

The number of paths for path length = 1 is trivial, equaling n x n, so let's start with the case where the path length = 2. How many paths of length 2 are there on the 4x4 grid? Then we will consider, 3, 4, ... and hopefully get data that will help us figure out a general equation.

Rules:
1. No square can be visited more than once in any path.
2. The path may go horizontally, vertically, or diagonally.

I have manually figured out the answer for lengths 2, 3, and 4, and was hoping to use that data and math modelling to figure out a general equation to use for any specified length and any specified grid size. But I haven't yet figured it out, so I wanted to pose the question to this community and maybe learn something!

Here are the answers I have calculated for lengths 2, 3, and 4:

(Explanation: For path length = 2, the 3 in cell A1 means that there are 3 possible paths of length 2 that start in cell A1, and so on)

enter image description here

For this problem, path order matters, so path AB is different than path BA, and ABC is different from CBA, and so on. So, there are 16 paths of length = 1, 84 paths of length 2, 408 paths of length 3, and 1,764 paths of length 4 (corrected by achille hui). Can we use this to figure out a general equation?

$\endgroup$
  • $\begingroup$ I put $84,408$ into oeis.org and found nothing useful $\endgroup$ – Ross Millikan Sep 20 '14 at 3:50
  • $\begingroup$ I get a different count for $n = 4$, $$\begin{array}{|c|c|c|c|} \hline 75 & 109 & 109 & 75\\ \hline 109 & 148 & 148 & 109\\ \hline 109 & 148 & 148 & 109\\ \hline 75 & 109 & 109 & 75\\ \hline \end{array}\quad\implies\verb/Total/ = 1764.$$ $\endgroup$ – achille hui Sep 20 '14 at 6:26
  • $\begingroup$ Some more data points. By brute force, some numbers of self-avoiding directed paths on an $n \times n$ grid with path length $p$ are: $$\begin{array}{r|rr} & \rlap{\quad\quad\quad\quad\quad\quad n}\\ p & 4 & 5 & 6 & 7 & 8\\ \hline 1 & 16 & 25 & 36 & 49 & 64\\ 2 & 84 & 144 & 220 & 312 & 420\\ 3 & 408 & 768 & 1240 & 1824 & 2520\\ 4 & 1764 & 3768 & 6508 & 9984 & 14196\\ 5 & 6712 & 17280 & 32520 & 52432 & 77016\\ 6 & 22672 & 74072 & 156484 & 268048 & 408764\\ 7 & 68272 & 296390 & 722384\\ 8 & 183472 & 1110000 & 3193800\\ 9 & 436984\\ 10 & 905776\\ \end{array}$$ $\endgroup$ – achille hui Sep 20 '14 at 10:01
  • $\begingroup$ Based on above numbers, an OEIS search return the series A186861 - $T(n,k)$ - Number of n-step king's tours on a kXk board. This OEIS entry is relatively new and there aren't much reference there. However, there is an empirical formula which I can't decrypt. You can take a look and see whether this will give you any insight. $\endgroup$ – achille hui Sep 20 '14 at 10:18
  • $\begingroup$ Thank you achille hui! Those extra data points will help, I think. I corrected n=4 in the question. What is the best way to tackle a math modeling problem like this? $\endgroup$ – JLee Sep 20 '14 at 14:05
5
$\begingroup$

I don't think there is an answer for this because part of the problem reduces to an open problem.

Let $\mathcal{N}_n(p)$ be the number of path of length $p$ (more precisely, covered $p$ squares) on a $n\times n$ grid. As mentioned in comment, we can compute some of these $\mathcal{N}_n(p)$ by brute force.

$$\begin{array}{r|rr} & \rlap{\quad\quad\quad\quad\quad\quad n}\\ p & 4 & 5 & 6 & 7 & 8\\ \hline 1 & 16 & 25 & 36 & 49 & 64\\ 2 & 84 & 144 & 220 & 312 & 420\\ 3 & 408 & 768 & 1240 & 1824 & 2520\\ 4 & 1764 & 3768 & 6508 & 9984 & 14196\\ 5 & 6712 & 17280 & 32520 & 52432 & 77016\\ 6 & 22672 & 74072 & 156484 & 268048 & 408764\\ 7 & 68272 & 296390 & 722384\\ 8 & 183472 & 1110000 & 3193800\\ 9 & 436984\\ 10 & 905776\\ \end{array}$$

Based on these numbers, an OEIS search return the series A186861 - T(n,k) - Number of n-step king's tours on a kXk board. It mentions there is an empirical formula for $T(n,k)$ for large $n$:

$$T(n,k) = 3T(n-1,k) - 3T(n-2,k) + T(n-3,k)\quad\text{ for large } n$$

I look back at my program computing $\mathcal{N}_n(p)$, I find the empirical formula is true.

Imagine we have an $\infty \times \infty$ grid and $p$ any positive integer.

Let $X_p$ be the collection of self avoiding path covered $p$ squares starting at origin.

Given any path $\ell \in X_p$, let $(x_1,y_1) = (0,0)$, $(x_2,y_2), \ldots, (x_p,y_p)$ be the squares visited by $\ell$.
Let $W(\ell)$ and $H(\ell)$ be the horizontal and vertical span of the path. More precisely, $$\begin{align} W(\ell) &= \max\{ x_k : 1 \le k \le p \} - \min\{ x_k : 1 \le k \le p \}\\ H(\ell) &= \max\{ y_k : 1 \le k \le p \} - \min\{ y_k : 1 \le k \le p \} \end{align}$$

To generate all possible paths on a $n\times n$ grid, we can walk through the set of path in $X_p$ and translate each of them on the $n \times n$ grid. Given any $\ell \in X_p$, the number of paths it can generate is

$$\begin{cases}(n - W(\ell))(n - H(\ell)),& n \ge \max( W(\ell), H(\ell) )\\ 0,&\text{otherwise}\end{cases}$$ As a result,

$$\mathcal{N}_n(p) = \sum_{\substack{ \ell\in X_p\\ n \ge \max( W(\ell), H(\ell) )} } (n-W(\ell))(n-H(\ell))$$

When $n \ge p$, we find $n \ge W(\ell)$ and $\ge H(\ell)$ for all $\ell \in X_p$. This leads to

$$\bbox[12pt,border: 1px solid blue;]{ \mathcal{N}_n(p) = \sum_{\ell\in X_p } (n-W(\ell))(n-H(\ell)) = \alpha_p n^2 - \beta_p n + \gamma_p \quad\text{ whenever } n \ge p } $$ where $$ \begin{cases} \alpha_p &= |X_p| = \sum\limits_{\ell \in X_p} 1\\ \beta_p &= \sum\limits_{\ell \in X_p} (W(\ell) + H(\ell))\\ \gamma_p &= \sum\limits_{\ell \in X_p} W(\ell) H(\ell) \end{cases} $$ In such case, $\mathcal{N}_n(p)$ becomes a quadratic polynomial in $n$ and the empirical formula is justified.

Following are some numbers for small $p$. $$\begin{array}{r|rrr} p & \alpha_p & \beta_p & \gamma_p\\ \hline 1 & 1 & 0 & 0\\ 2 & 8 & 12 & 4\\ 3 & 56 & 144 & 88\\ 4 & 368 & 1308 & 1108\\ 5 & 2336 & 10456 & 11160\\ 6 & 14576 & 77924 & 99292\\ 7 & 89928 & 555464 & 817760\\ 8 & 550504 & 3839372 & 6382124\\ \end{array}$$

I have tried to use this number to make an OEIS search but I cannot find anything.

In any event, it is clear the leading behavior of $\mathcal{N}_n(p)$ is controlled by the number $\alpha_p$. Numbers like $\alpha_p$ has been studied before in mathematics, statistical physics and chemsitry. It is usually under the subject Self Avoiding walk. If is also clear if we have a general formula for $\mathcal{N}_n(p)$, we will have a formula for $\alpha_p$. Unluckily, finding a formula for $\alpha_p$ is an open problem!

Quoting wiki:

There is currently no known formula for determining the number of self-avoiding walks, although there are rigorous methods for approximating them. Finding the number of such paths is conjectured to be an NP-hard problem.

My recommendation is this:

If you want to proceed mathematically, you should forget this version of problem first. You should look up the literature of self-avoiding walks for a simpler walk. For example, a walk only allow moves in horizontal and vertical direction on an infinite square lattice. Learn the basic first and see what sort of techniques are available for the simpler case.

$\endgroup$
  • $\begingroup$ Thank you for the super-detailed answer! I am still reading it and studying the problem now. I will probably mark this as the answer later, but I want to understand it better first. $\endgroup$ – JLee Sep 22 '14 at 14:47

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.