<s>[INST] Longest path in a grid I recently saw a computer programming question that asked for the longest path that one can build in a $3\times3$ unit grid connecting the vertexes, with the following rules(the same rules of a pattern password):


*

*Each vertex may be used at most once.

*A vertex cannot be skipped in a line if it is not used previously.

*If a vertex is used then it must be skipped if a line crosses it.


Now, since $9!=362880$ the problem is trivial by bruteforce. But, is there an analytical way of solving the problem?
 [/INST] I suggest to start with longest distances and then add shorter.
You have the following vertex sequence
$$
\begin{array}{cccc}
1 & \cdots & 6 & \cdots & 9 & \cdots & 3 \\
\vdots & & \vdots & & \vdots & & \vdots \\
10 & \cdots & 13 & \cdots & 16 & \cdots & 8 \\
\vdots & & \vdots & & \vdots & & \vdots \\
4 & \cdots & 15 & \cdots & 14 & \cdots & 12 \\
\vdots & & \vdots & & \vdots & & \vdots \\
7 & \cdots & 11 & \cdots & 2 & \cdots & 5 \\
\end{array}
$$
And we obtain the distance
$$
\begin{array}{ccccccccccccccc}
1 & [\sqrt{13}] & 2 & [\sqrt{10}] &
3 & [\sqrt{13}] & 2 & [\sqrt{10}] &
5 & [\sqrt{13}] & 6 & [\sqrt{10}] &
7 & [\sqrt{13}] & 8
\end{array}\\
\begin{array}{ccccccccccc}
8 & [\sqrt{2}] &
9 & [\sqrt{5}] &
10 & [\sqrt{5}] &
11 & [\sqrt{5}] &
12 & [\sqrt{5}] &
13
\end{array}\\
\begin{array}{ccccccccccc}
13 & [\sqrt{2}] &
14 & [1] &
15 & [\sqrt{2}] &
16
\end{array},\\
$$
(if I did understood the rules...)

Totaly

$$
1 + 3 \sqrt{2} + 4 \sqrt{5} + 3 \sqrt{10} + 4 \sqrt{13},
$$
or
$$
38.09595...
$$
</s>