Marco Ripà



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.


Nine dot-Problem; Optimization; Thinking outside the box, Polygonal path; Clockwise-algorithm.

Full Text:



M. Kihn, “Outside the Box: The Inside Story”, FastCompany, 1995.

S. Loyd, “Cyclopedia of Puzzles”, The Lamb Publishing Company, p. 301, 1914.

J. M. Chein, R. W. Weisberg, N. L. Streeter and S. Kwok, “Working memory and insight in the nine-dot problem”, Memory & Cognition, vol. 38, pp. 883–892, 2010.

C. T. Lung and R. L. Dominowski, “Effects of strategy instructions and practice on nine-dot problem solving”, Journal of Experimental Psychology: Learning, Memory, and Cognition, vol. 11, no. 4, pp. 804–811, 1985.

S. Bereg, P. Bose, A. Dumitrescu, F. Hurtado and P. Valtr, “Traversing a set of points with a minimum number of turns”, Discrete & Computational Geometry, vol. 41, no. 4, pp. 513–532, 2009.

M. J. Collins, “Covering a set of points with a minimum number of turns”, International Journal of Computational Geometry & Applications, vol. 14, no. 1-2, pp. 105–114, 2004.

E. Kranakis, D. Krizanc and L. Meertens, “Link length of rectilinear Hamiltonian tours in grids”, Ars Combinatoria, vol. 38, pp. 177–192, 1994.

M. Ripà and P. Remirez, “The Nine Dots Puzzle extended to n X n X ... X n Points, viXra, 5 Sep. 2013.

A. Aggarwal, D. Coppersmith, S. Khanna, R. Motwani and B. Schieber, “The angular-metric traveling salesman problem”, SIAM Journal on Computing, vol. 29, pp. 697–711, 1999.

C. Stein and D. P. Wagner, “Approximation algorithms for the minimum bends traveling salesman problem. In: K. Aardal, & B. Gerards (Eds.), Integer Programming and Combinatorial Optimization, LNCS, vol. 2081, pp. 406–421. Berlin: Springer, 2001.

B. Chitturi and J. Pai, “Minimum-Link Rectilinear Covering Tour is NP-hard in R^4”, arXiv, 1 Oct. 2018.

M. J. Collins and M. E. Moret, “Improved lower bounds for the link length of rectilinear spanning paths in grids”, Information Processing Letters, vol. 68, no. 6, pp. 317–319, 1998.

M. Ripà, “Solving the n_1 ≤ n_2 ≤ n_3 Points Problem for n_3 < 6, ResearchGate, 25 Jun. 2020.


B. Keszegh, “Covering Paths and Trees for Planar Grids”, arXiv, 3 Nov. 2013.

A. Dumitrescu and C. Tóth, “Covering Grids by Trees”, 26th Canadian Conference on Computational Geometry, 2014.

M. Hohenwarter, M. Borcherds, G. Ancsin, B. Bencze, M. Blossier, J. Elias, K. Frank, L. Gal, A. Hofstaetter, F. Jordan, B. Karacsony, Z. Konecny, Z. Kovacs, W. Kuellinger, E. Lettner, S. Lizelfelner, B. Parisse, C. Solyom-Gecse and M. Tomaschko, “GeoGebra - Dynamic Mathematics for Everyone - version 6.0.507.0-w”, International GeoGebra Institute, 16 Oct. 2018.


  • There are currently no refbacks.


Department of Mathematics, Faculty of Science and Mathematics, Diponegoro University

Mailing address: Jl. Prof Soedarto, SH, Tembalang, Semarang, Indonesia 50275

Telp./Fax             : (+6224) 70789493 / (+62224) 76480922

Website              :

E-mail                :


Indexed in: