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

Marco Ripà


DOI: https://doi.org/10.14710/jfma.v3i2.8551

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.

Keywords


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

Full Text:

PDF

References


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. https://vixra.org/pdf/1307.0021v4.pdf

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. https://arxiv.org/abs/1810.00529

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. https://www.researchgate.net/publication/

_Solving_the_n_1_n_2_n_3_Points_Problem_for_n_3_6

B. Keszegh, “Covering Paths and Trees for Planar Grids”, arXiv, 3 Nov. 2013. https://arxiv.org/abs/1311.0452

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. https://www.geogebra.org


Refbacks

  • There are currently no refbacks.


Publisher:

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              : www.math.fsm.undip.ac.id

E-mail                : admin.math@live.undip.ac.id

 

Indexed in:

GOOGLE SCHOLAR CROSSREF SINTA PORTAL GARUDA SCILIT DIMENSIONS