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
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
KEYWORD
nonn,more,hard,bref
AUTHOR
Marco Ripà, Jun 19 2023
STATUS
proposed