A363755 - OEIS

%I #18 Aug 01 2023 08:07:13

%S 1,6,13

%N The original n X n X n dots problem: minimal number of straight lines (connected at their endpoints) required to join all the n^3 points belonging to the set {{0,1,...,n-1} X {0,1,...,n-1} X {0,1,...,n-1}} in R^3, without any additional constraint.

%C 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.

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

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

%D Sam Loyd, Cyclopedia of Puzzles, The Lamb Publishing Company, 1914, page 301.

%H Roberto Rinaldi and Marco Ripà, <a href="https://arxiv.org/abs/2212.11216">Optimal cycles enclosing all the nodes of a k-dimensional hypercube</a>, arXiv:2212.11216 [math.CO], 2022.

%H Marco Ripà, <a href="http://dx.doi.org/10.13140/RG.2.2.12199.57769/1">Solving the n_1 <= n_2 <= n_3 Points Problem for n_3 < 6</a>, ResearchGate, 2020.

%H Marco Ripà, <a href="https://doi.org/10.14710/jfma.v3i2.8551">Solving the 106 years old 3^k points problem with the clockwise-algorithm</a>, Journal of Fundamental Mathematics and Applications, 2020, 3(2), 84-97.

%H Marco Ripà, <a href="https://arxiv.org/abs/2208.01699">Minimum-Link Covering Trails for any Hypercubic Lattice</a>, arXiv:2208.01699 [math.GM], 2022.

%H Marco Ripà, <a href="http://dx.doi.org/10.13140/RG.2.2.12769.99689">General conjecture on the optimal covering trails in a k-dimensional cubic lattice</a>, ResearchGate, 2022.

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Thinking_outside_the_box#Nine_dots_puzzle">Nine dots puzzle</a>

%F For any n >= 3, (n^3 - 1)/n - 1) <= a(n) <= floor((3*n^2)/2) - floor((n - 1)/4) + floor((n + 1)/4) - floor((n + 2)/4) + floor(n/4) + n - 2.

%e For n = 2, a(2) = 6, since it is not possible to touch the 8 vertices of a cube by spending fewer than 6 straight lines (see Theorem 2.2 in Optimal cycles enclosing all the nodes of a k-dimensional hypercube).

%Y Cf. A058992, A225227, A261547, A318165.

%K nonn,more,hard,bref

%O 1,2

%A _Marco Ripà_, Jun 19 2023