cp's OEIS Frontend

A generalization of the well-known "Nine Dots Problem", where the regular axis-aligned bounding box (RAABB:=[0, n] X [0, n] X [0, n]) has been declared.

From Marco Ripà, Aug 10 2020: (Start)

In particular, if we loosen the constraint on the allowed AABB, covering paths characterized by a shorter link-length can be found, such as 5 <= a(2) <= 6, where the aforementioned upper bound has been discovered by Koki Goma in August 2021, providing the self-crossing covering path (0,0,0)-(2,2,0)-(1/2,1/2,3/2)-(2,-1,0)-(0,1,0)-(0,1,1)-(0,0,1).

Moreover, the above pattern suggests different uncrossing covering paths of the same link-length, such as (1,0,0)-(0,0,0)-(2,2,2)-(1/2,-1,1/2)-(-1/2,1,3/2)-(1,1,0)-(1,1,0) and also the (self-crossing) covering path (1,0,0)-(0,0,0)-(0,1,0)-(3/2,1,3/2)-(1/2,-1,1/2)-(-1/2,1,3/2)-(1,1,0) which is entirely contained inside a box of 1.5 X 2 X 2 units^3 but which does not match the RAABB. (End)

The most natural mathematical generalization of the well-known "Nine Dots Problem" by Sam Loyd (published in Cyclopedia of puzzles, p. 301, in 1914) is an NP-hard challenge with no AABB, no constraint about visiting any vertex more than once or self-crossing lines, no restriction on the turning angles available.

This problem has been solved for n < 4 (see links), while it has been proved that a(4) is 21, 22, or 23, since a covering trail (for the n = 4 case) having 23 links is given by (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).

A covering trail for the n = 5 case with a link-length of 36 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).

For any n > 2, is it possible to construct an "inside the box" covering tree for any n X n X n set of points consisting of n^2 + n lines if n is even and n^2 + n + 1 lines if n is odd.

In the special case of any 2 X 2 X ... X 2 points problem (k-times n), every optimal covering tree has (exactly) 2^(k-1) rectilinear segments, thus 2^(3-1) = 4 lines for the 2 x 2 x 2 case.

If n = 3, then the (outside the box) solution is a(3) = 12, since such a connected arrangement of line segments has already been shown to exist, and this explicit upper bound matches 3^3 + 3. - Marco Ripà, Aug 25 2020

Let n >= 5, we know that it is impossible to cover more than n^3 points with n^2 segments (trivial), and we need at least n segments to obtain a connected graph (otherwise, we cannot join more than n + h*(n - 1) points with h + 1 connected lines). Thus, assuming n > 2, the general lower bound is confirmed to be n^2 + n, therefore a(n even) = 4, 20, 42, 72, ...