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 $k$-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 $k\in \mathbb{N}-\{0\}$, solving the NP-complete $(3\times 3\times \cdots \times 3)$-point problem inside $3\times 3\times \cdots \times 3$ hypercubes. In particular, using our algorithm, we explicitly draw different covering trails of minimal length $h(k)=\frac{3^k-1}{2}$, for $k=3,4,5$. Furthermore, we conjecture that, for every $k\ge 1$, it is possible to solve the $3^k$-point problem with $h(k)$ lines starting from any of the $3^k$ nodes, except from the central one. Finally, we cover a $3\times 3\times 3$ grid with a tree of size $12$.

17 pages, 12 figures. A video animation of the solution from 1 to 4 dimensions can be found on YouTube (https://www.youtube.com/watch?v=SSL9R0hQRKM)

Cited by in corpus (1)

• General uncrossing covering paths inside the axis-aligned bounding box