A363755 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.

1, 6, 13

Offset

1,2

Comments

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

References

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

Links

Table of n, a(n) for n=1..3.

Roberto Rinaldi and Marco Ripà, Optimal cycles enclosing all the nodes of a k-dimensional hypercube, arXiv:2212.11216 [math.CO], 2022.

Marco Ripà, Solving the n_1 <= n_2 <= n_3 Points Problem for n_3 < 6, ResearchGate, 2020.

Marco Ripà, Solving the 106 years old 3^k points problem with the clockwise-algorithm, Journal of Fundamental Mathematics and Applications, 2020, 3(2), 84-97.

Marco Ripà, Minimum-Link Covering Trails for any Hypercubic Lattice, arXiv:2208.01699 [math.GM], 2022.

Marco Ripà, General conjecture on the optimal covering trails in a k-dimensional cubic lattice, ResearchGate, 2022.

Wikipedia, Nine dots puzzle

Formula

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.

Example

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

Crossrefs

Cf. A058992, A225227, A261547, A318165.

Sequence in context: A202383 A216423 A229336 * A070396 A359091 A130012

Adjacent sequences: A363752 A363753 A363754 * A363756 A363757 A363758

Keyword

nonn,more,hard,bref

Author

Marco Ripà, Jun 19 2023

Status

approved