SOLVING THE 106 YEARS OLD 3^k POINTS PROBLEM WITH THE CLOCKWISE-ALGORITHM

Abstract

In this paper, we present the clockwise-algorithm that solves the extension in 𝑘-dimensions of the infamous nine-dot problem, the well known two-dimensional thinking outside the box puzzle. We describe a general strategy that constructively produces minimum length covering trails, for any 𝑘 ∈ N−{0}, solving the NP-complete (3×3×⋯×3)-points problem inside a 3×3×⋯×3 hypercube. In particular, using our algorithm, we explicitly draw different covering trails of minimal length h(𝑘) = (3^𝑘 − 1)/2, for 𝑘 = 3, 4, 5. Furthermore, we conjecture that, for every 𝑘 ≥ 1, it is possible to solve the 3^𝑘-points problem with h(𝑘) lines starting from any of the 3^𝑘 nodes, except from the central one. Finally, we cover 3×3×3 points with a tree of size 12.