# General conjecture on the optimal covering trails for any $k$-dimensional cubic lattice

Marco Ripà

► To cite this version:

Marco Ripà. General conjecture on the optimal covering trails for any $k$-dimensional cubic lattice. 2022. hal-03841209v3

HAL Id: hal-03841209

https://hal.science/hal-03841209v3

Preprint submitted on 28 Nov 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# General conjecture on the optimal covering trails in a $k$-dimensional cubic lattice

Marco Ripà

ORCID iD: 0000-0002-6036-5541

World Intelligence Network
Rome, Italy

e-mail: marcokrt1984@yahoo.it

**Abstract:** We introduce a general conjecture involving minimum-link covering trails for any given $k$-dimensional grid $n \times n \times \cdots \times n$, belonging to the cubic lattice $\mathbb{N}^k$. In detail, if $n$ is above two, we hypothesize that the minimal link length of any covering trail, for the above-mentioned set of $n^k$ points in the Euclidean space $\mathbb{R}^k$, is equal to $h(n, k) = \frac{n^{k-1}}{n-1} + c \cdot (n-3)$, where $c = k-1$ iff $h(4, 3) = 23$, $c = 1$ iff $h(4, 3) = 22$, or even $c = 0$ iff $h(4, 3) = 21$.

**Keywords:** Conjecture, Link length, Covering Trail, Nine-dot problem, Optimization.

**2020 Mathematics Subject Classification:** Primary 05C57, 05C38; Secondary 68R10.

## 1 Introduction

In the present preprint we formulate a very general conjecture on the infamous nine-dot problem [5] extended to any given $n \times n \times \cdots \times n$ grid in the Euclidean space $\mathbb{R}^k$.

Let $\mathbb{N} - \{0\}$ be the set of (strictly) positive integers so that, for any $k \in \mathbb{N} - \{0, 1, 2\}$, we denote as $\mathbb{N}^k$ the $k$-dimensional cubic lattice $\mathbb{N}^k := \{(x_1, x_2, \ldots, x_n) : x_i \in \mathbb{N} \wedge n \ge 3\}$.

Under the well-known *nine-dot problem* rules [3], our goal is to visit all the $n^k$ nodes of the set $\mathcal{H}(n, k) := \{0, 1, 2, \ldots, n-1\} \times \{0, 1, 2, \ldots, n-1\} \times \cdots \times \{0, 1, 2, \ldots, n-1\}$ with a covering trail (i.e., any polygonal chain joining all the aforementioned points) having the minimum number of links.

Since this NP-complete problem (see [2], p. 514) has been fully solved only for a few, very special, cases (i.e., $n \le 3 \wedge k \in \mathbb{Z}^+$ [7, 9] and $n \in \mathbb{Z}^+ \wedge k \le 2$ [4]), we mainly base our approach on the proven bounds, linking the conjectured formula to recent results and many other evidences (e.g., combinatorial inference on graphical models, pattern recognition constraints, and case-by-case analysis [10]).

Let us denote by $h(n, k)$ the minimum link length of any covering trail for the set $\mathcal{H}(n, k)$.

Consequently, let us indicate a valid upper bound as $h_u(n, k)$ so that $h(n, k) \le h_u(n, k)$ holds by definition. Since $\frac{n^{k-1}}{n-1} \le h(n, k) \le h_u(n, k)$, $\forall k \ge 3$ (see [9], Theorem 2.1), let $h_u(n, k) := (h_u(n, 3) + 1) \cdot n^{k-3} - 1$ (by [10] Equation 6), so $h_u(4, 3) = 23 \Rightarrow h(4, 4) \in [85, 95]$ and $h_u(5, 3) =$
$36 \Rightarrow h(5, 5) \in [781, 924]$, while $h(n, 2) = 2 \cdot (n - 1)$, $h(2, k) = 3 \cdot 2^{k-2}$, and $h(3, k) = \frac{3^k - 1}{2}$ have been formally proven in recent years [4, 7, 8].

Now, it is natural to suppose that the general solution follows a simple recursive pattern, as it has been shown to be true for the lower order k-dimensional grids, so we can single out the formula for the link length of any optimal covering trail for the set $\mathcal{H}(n, k)$ by verifying ex-post that $h(4, 3) \neq 21$, arguing a fortiori that Conjecture 2.1 by Reference [9] always holds.

Thus, in order to finally decide whether to conjecture $h(n, k) = \frac{n^{k-1}}{n-1} + n - 3$ or $h(n, k) = \frac{n^{k-1}}{n-1} + (k-1) \cdot (n-3)$, it would be very helpful to implement an efficient computer algorithm which can find (if any) a valid 22-link covering trail for $\mathcal{H}(4, 3)$, supporting the strong claim that $h(n, k) = \frac{n^{k-1}}{n-1} + n - 3$.

In Section 4 of the present preprint, we will describe a theoretical brute force approach that is possible to take as a starting point, going for a more sophisticated Monte Carlo method.

## 2 Full table of results

In general, given any pair of strictly positive integers $(n, k)$, what we currently know on the open problem of covering the set $\mathcal{H}(n, k)$ with a minimum-link trail, is given by Equations (1) to (8).

$$h(n, 1) = 1, \forall n. \qquad (1)$$

$$h(n, 2) = 2 \cdot (n - 1), \forall n \geq 3. \qquad (2)$$

$$h(1, k) = 1, \forall k. \qquad (3)$$

$$h(2, k) = 3 \cdot 2^{k-2}, \forall k \geq 2. \qquad (4)$$

$$h(3, k) = \frac{3^k - 1}{2}, \forall k. \qquad (5)$$

$$h(n, k) \le \left( \left\lfloor \frac{3}{2} \cdot n^2 \right\rfloor - \left\lfloor \frac{n-1}{4} \right\rfloor + \left\lfloor \frac{n+1}{4} \right\rfloor - \left\lfloor \frac{n+2}{4} \right\rfloor + \left\lfloor \frac{n}{4} \right\rfloor + n-1 \right) \cdot n^{k-3} - 1, \forall n \ge 3 \land \forall k \ge 3 \qquad (6)$$

(see Equation (5) in Reference [6]).

$$h(n, k) \ge \frac{n^k - 1}{n - 1}, \forall n \ge 3 \land \forall k. \qquad (7)$$

$$h(n, k) \le (h_u(n, 3) + 1) \cdot n^{k-3} - 1, \forall n \ge 3 \land \forall k \ge 3. \qquad (8)$$

Lastly, we have that $h(4, 3) \le 23$ and $h(5, 3) \le 36$ (see Section 3, Figure 1 and Figure 2, respectively), while $h(n, k) \le \left( \left\lfloor \frac{3}{2} \cdot n^2 \right\rfloor - \left\lfloor \frac{n-1}{4} \right\rfloor + \left\lfloor \frac{n+1}{4} \right\rfloor - \left\lfloor \frac{n+2}{4} \right\rfloor + \left\lfloor \frac{n}{4} \right\rfloor + n - 1 \right) \cdot n^{k-3} - 1$ is a weak upper bound which holds for any $n, k \in \mathbb{N} - \{0, 1, 2\}$ (see Equation (6)).

Then, the proven results by Equations (1) to (8) are summarized in Table 1.
<table><caption>Table 1: Proven bounds for the general $\{0, 1, 2, \dots, n-1\} \times \{0, 1, 2, \dots, n-1\} \times \dots \times \{0, 1, 2, \dots, n-1\}$ points problem in $\mathbb{R}^k$.</caption><thead><tr><th>k<br>n</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>...</th><th>h(n&#773;, k)</th></tr></thead><tbody><tr><th>1</th><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>...</td><td>h(1, k) = 1</td></tr><tr><th>2</th><td>1</td><td>3</td><td>6</td><td>12</td><td>24</td><td>...</td><td>h(2, k) = 3 &middot; 2<sup>k&minus;2</sup>, &forall;k &ge; 2</td></tr><tr><th>3</th><td>1</td><td>4</td><td>13</td><td>40</td><td>121</td><td>...</td><td>h(3, k) = <sup>3<sup>k&minus;1</sup></sup>&frasl;<sub>2</sub></td></tr><tr><th>4</th><td>1</td><td>6</td><td>[21, 23]</td><td>[85, 95]</td><td>[341, 383]</td><td>...</td><td><sup>4<sup>k&minus;1</sup></sup>&frasl;<sub>3</sub> &le; h(4, k) &le; h<sub>u</sub>(4, k)</td></tr><tr><th>5</th><td>1</td><td>8</td><td>[31, 36]</td><td>[156, 184]</td><td>[781, 924]</td><td>...</td><td><sup>5<sup>k&minus;1</sup></sup>&frasl;<sub>4</sub> &le; h(5, k) &le; h<sub>u</sub>(5, k)</td></tr><tr><th>...</th><td>...</td><td>...</td><td>...</td><td>...</td><td>...</td><td>...</td><td>...</td></tr><tr><th>h(n, n&#773;)</th><td>1</td><td>2 &middot; (n &minus; 1),<br>&forall;n &ge; 3</td><td>h(n, 3)</td><td>h(n, 4)</td><td>h(n, 5)</td><td>...</td><td><sup>n<sup>k&minus;1</sup></sup>&frasl;<sub>n&minus;1</sub> &le; <span style="color:red;">h(n, k)</span> &le; h<sub>u</sub>(n, k),<br>&forall;n &ge; 3</td></tr></tbody></table>

### 3 Proof that $h(4, 3) \le 23$ and $h(5, 3) \le 36$

A covering trail with 23 links for the set $\mathcal{H}(4, 3)$ is $(3, 3, 1)-(1, 3, 1)-(-2, 0, 1)-(4, 0, 1)-(3, 0, 3)-(3, 3, 3)-(0, 0, 0)-(3, 0, 0)-(0, 3, 3)-(0, 0, 3)-(3, 3, 0)-(-1, 3, 0)-(2, 3, 3)-(2, -1, 3)-(-1, 2, 0)-(4, 2, 0)-(1, -1, 3)-(1, 4, 3)-(4, 1, 0)-(-1, 1, 0)-(3, 3, 2)-(3, -2, 2)-(0, 7, 2)-(0, 0, 2), Figure 1.

<figure><img src="image_2.png" /><figcaption>Figure 1: Constructive proof that $h(4, 3) \le 23$ [10].</figcaption></figure>
A covering trail with 36 links for the set $\mathcal{H}(5, 3)$ is $(2, 3, 3)-(-1, 0, 3)-(-4, 0, 3)-(-0, 4, 3)-(-5, 4, 3)-(-3, 2, 1)-(-1, 0, 1)-(-4, 5, 1)-(-4, 0, 1)-(-0, 0, 1)-(-0, 4, 1)-(-5, -1, 1)-(-3, 3, 3)-(-0, -3, 0)-(-0, 5, 0)-(-4, 1, 4)-(-1, 1, 4)-(-3, 5, 0)-(-3, 0, 0)-(-1, 4, 4)-(-4, 4, 4)-(-4, 0, 0)-(-4, 4, 0)-(-0, 0, 4)-(-5, 0, 4)-(-1, 4, 0)-(-1, -1, 0)-(-5, 3, 4)-(-0, 3, 4)-(-2, -1, 0)-(-2, 4, 0)-(-4, 2, 4)-(-0, 2, 4)-(-4, 0, 2)-(-0, 0, 2)-(-0, 4, 2)-(-4, 4, 2)$, Figure 2.

<figure><img src="image_3.png" /><figcaption>Figure 2: Constructive proof that $h(5, 3) \le 36$ [10].</figcaption></figure>

# 4 Searching for $h(4, 3)$ by brute force

Since $h(n, 2) > \frac{n^2-1}{n-1}$ for any $n > 3$ by Reference [4] and given the fact that $h(3, k) = \frac{3^k-1}{3-1}$ by [7], in the present section we will assume that $h(n, k) < \frac{n^k-1}{n-1} + n - 3$ should be false for any $n \ge 3 \land k \ge 2$ so that $h(4, 3) = 22 \lor h(4, 3) = 23$.

Then, we observe how $h(n, k) = \frac{n^k-1}{n-1}$ implies that each pair of consecutive line segments of any theoretical 21-link covering trail for $\mathcal{H}(4, 3)$ would join at least 6 of its nodes [9], while, since we disregard this (very unlikely) possibility here, we need to take into account, as a worst-case scenario, that an optimal covering trail could consist of 22 links of which at least 19 have to necessarily join 2 or more unvisited points each (e.g., it would be possible to join 4 nodes with the first link, to have a triplet of consecutive pairs of links visiting 1 + 4 new nodes for three times in a row, and to finally visit the remaining 45 nodes of $\mathcal{H}(4, 3)$ by spending the last 15 line segments available, since we could use all the 15 residual links to join 3 nodes each time, or to have some of those pairs that visit 2 nodes with one link and 4 nodes thanks to the next one, as exemplified by the polygonal chain $(0, 3, 0)-(-5, 3, 0)-(-1, 0, 0)-(-5, 0, 0)-(-1, 0, 3)-(-5, 0, 3)-(-1, 3, 3)-(-3, 3, 3))$.

The constraint above trivially follows by considering that we cannot visit all the $4^3$ nodes of $\mathcal{H}(4, 3)$ with 22 consecutive links if we spend more than three links to fit only one new point at a time, since $4^3 \le 4+3 \cdot (22-1-2 \cdot m) + (1+4) \cdot m$ if and only if $m \le 3$ (see Reference [9], proof of Theorem 2.1).
A very basic algorithm, to try to (constructively) find by brute force a 22-link covering trail for $\mathcal{H}(4, 3)$, is as follows.

1. Step 1. Take one by one each pair of elements of the set $\mathcal{H}(4, 3)$ and draw the (unique) straight line through those two points. Do the same for every pair of nodes of $\mathcal{H}(4, 3)$ and denote as $\mathcal{I}_2(4, 3)$ the set of all those crossing points.

Now, it is easy to observe that if $h(4, 3) < 23$, then it would necessarily be possible to find optimal covering trails inside the axis-aligned bounding box (AABB [8]) $[6, 9] \times [6, 9] \times [6, 9]$. Thus, the set $\mathcal{I}_2(4, 3)$ has a total of 13307 elements (i.e., $|\mathcal{I}_2(4, 3)| = 13307$) and there are 1492 maximal line segments, as shown by Reference [1].

2. Step 2. Consider only the polygonal chains of link length $q \in \{1, 2, \dots, 22\}$, having all the vertices belonging to the set $\mathcal{I}_2(4, 3)$, and such that each of their links joins at least 2 (unvisited) nodes of $\mathcal{H}(4, 3)$. Furthermore, from the above-mentioned class of trails, let us also disregard all the polygonal chains of length $q$ that do not visit at least $3 \cdot q - \lfloor \frac{q}{7} \rfloor$ nodes of $\mathcal{H}(4, 3)$.

3. Step 3. From the very efficient polygonal chains returned by Step 2, take only into account the trails with link length 21 (if we get only a void set of solutions, then abort the process, since the test is failed). By construction, they visit 60, 61, 62, or 63 nodes (otherwise, we would have found a 21-link covering trail for the set $\mathcal{H}(4, 3)$, proving that $h(4, 3) = 21$, and we do not expect that this could happen).

4. Step 4. Although Step 3 does not allow us to perform an exhaustive search (and a failed test cannot prove in any way that $h(4, 3) = 23$), we are now ready to sort the polygonal chains with 21 links (returned by Step 3) in ascending numerical order basing on how many nodes of $\mathcal{H}(4, 3)$ they visit.

5. Step 5.

(a) Case (a). If we have already found a 21-link trail joining 63 nodes, the search is over, since we will spend the last line segment to join together an endpoint of that optimal polygonal chain and the last unvisited node of $\mathcal{H}(4, 3)$. If not, let us move on to Step 5, Case (b).

(b) Case (b). If the best polygonal chains returned by Step 4 visit (exactly) 62 nodes, then we take them and start to check, one by one, whether the line that fits the pair of residual nodes intersects one of the two lines that include the first&second or the second-last&last vertices of the 21-link trail that we have originally selected. If there is an *external* match with respect to the right half-line containing the first/last link of the selected polygonal chain, then we have constructively proven that $h(4, 3) < 23$. Otherwise, let us move on to Step 5, Case (c).

(c) Case (c). There are 3 (or maybe even 4) unvisited nodes left. If they are not collinear points, then the test is failed; otherwise, they are collinear and we repeat the same pattern described in Step 5, Case (b), with only one difference: if there is no right external
match between the above mentioned fitting line and the extensions of the first/last link belonging to the 21-link trail we have selected, then the test is failed and the process stops.

If the described test fails, then we cannot improve the current bound $21 \le h(4, 3) \le 23$, and also we cannot conjecture that $h(n, k) = \frac{n^k-1}{n-1} + (k-1) \cdot (n-3)$, since the theoretical existence of a 22-link covering trail cannot be excluded by a partial search as the above.

On the contrary, if the test has succeeded, returning a 22-link covering trail for $H(4, 3)$, then a general conjecture stating that $h(n, k) = h(n, k) = \frac{n^k-1}{n-1} + n - 3$ would receive a relevant confirmation.

Lastly, to speed up the algorithm, we point out how it would be possible to run a Monte Carlo experiment looking for the longest trails with $q$ links that visit a total of $3 \cdot q + 1$ nodes of $\mathcal{H}(4, 3)$, and then going forward.

In the meantime, let us state our conjecture on $h(n, k)$ as follows.

**Conjecture 1.** For any $n \in \mathbb{N} - \{0, 1, 2\}$ and $k \in \mathbb{N} - \{0\}$, we conjecture that
$$h(n, k) = \frac{n^k-1}{n-1} + n - 3 \lor h(n, k) = \frac{n^k-1}{n-1} + (k-1) \cdot (n-3).$$

Time will tell.

# 5 Conclusion

After a dozen years spent working on this family of problems, basing our deductions on the evidence discussed in the present preprint, we are finally ready to conjecture that, if $n$ is greater than 2, then $h(n, k) = \frac{n^k-1}{n-1} + n - 3$ or $h(n, k) = \frac{n^k-1}{n-1} + (k-1) \cdot (n-3)$, since it seems to be very unlikely the evenience that, while $h(n, 2) > \frac{n^2-1}{n-1}$ if and only if $n \ge 4$ [4], at the same time, $h(n, 3)$ is not greater than $\frac{n^3-1}{n-1}$ for some $n \ge 4$ (taking also into account that, for any $k \in \mathbb{Z}^+$, $h(3, k) = \frac{3^k-1}{3-1} = \frac{3^k-1}{3-1} + (3-3) = \frac{3^k-1}{3-1} + (k-1) \cdot (3-3)$).

Consequently, we expect $h(n, k)$ to be $\frac{n^k-1}{n-1} + n - 3$ if it will be proven $h(4, 3) < 23$ or, alternatively, $h(5, 3) < 35$, whereas we can trust in $h(n, k) = \frac{n^k-1}{n-1} + (k-1) \cdot (n-3)$ after any proof that $h(4, 3) > 22$ or $h(5, 3) > 34$.

Even though our solid belief has been clearly stated in the present preprint, the research on this topic is far from being concluded, and different answers, not previously contemplated, are conceivable at present.

# Acknowledgements

The author is thankful to the MathOverflow user *Max Alekseyev*, for his valuable answer concerning the brute force algorithm described in Section 4, and to all the active followers of his YouTube channel, whose comments and constant support have contributed to improve the overall quality of this preprint.
References

[1] M. ALEKSEYEV, *Finding an optimal covering trail for the set {0,1,2,3} × {0,1,2,3} × {0,1,2,3}, MathOverflow (version: 2022-10-18)*. https://mathoverflow.net/q/432717

[2] S. BEREG, P. BOSE, A. DUMITRESCU, F. HURTADO, P. VALTR, *Traversing a set of points with a minimum number of turns*, Discrete & Computational Geometry, no. 4, **41** (2009), 513-532. https://link.springer.com/article/10.1007/s00454-008-9127-1

[3] J. M. CHEIN, R. W. WEISBERG, N. L. STREETER, S. KWOK, *Working memory and insight in the nine-dot problem*, Memory & Cognition, no. 7, **38** (2010), 883-892. https://link.springer.com/article/10.3758/MC.38.7.883

[4] B. KESZEGH, *Covering Paths and Trees for Planar Grids*, arXiv (2013). https://doi.org/10.48550/arXiv.1311.0452

[5] S. LOYD, *Sam Loyd's Cyclopedia of 5000 Puzzles, Tricks and Conundrums with Answers*, The Lamb Publishing Company, New York (1914). https://www-mathpuzzle-com translate.goog/loyd/?_x_tr_sl=en&x_trTL=it&x_tr_hl=it&x_tr pto=sc

[6] M. RIPÀ, V. BENCINI, *The n × n × n Dots Problem: An Improved 'Outside the Box' Upper Bound*, viXra (2018) (in Italian). https://vixra.org/pdf/1807.0384v2.pdf

[7] M. RIPÀ, *Solving the 106 years old 3<sup>k</sup> points problem with the clockwise-algorithm*, Journal of Fundamental Mathematics and Applications, no. 2, **3** (2020), 84-97. https://doi.org/10.14710/jfma.v3i2.8551

[8] M. RIPÀ, *General uncrossing covering paths inside the axis-aligned bounding box*, Journal of Fundamental Mathematics and Applications, no. 2, **4** (2021), 154-166. https://doi.org/10.14710/jfma.v4i2.12053

[9] M. RIPÀ, *Minimum-Link Covering Trails for any Hypercubic Lattice*, arXiv (2022). https://arxiv.org/abs/2208.01699v3

[10] M. RIPÀ, *Solving the n₁ × n₂ × n₃ Points Problem for n₃ < 6*, Optimization Online (2022). https://optimization-online.org/?p=19037