# Solving the n_1×n_2×n_3 Points Problem for n_3 < 6

**Author: Marco Ripà**

Numbering: Issue 22.B, Idea: Outliers & Outsiders (Part Eighteen)

Place of Publication: Langley, British Columbia, Canada

Title: In-Sight: Independent Interview-Based Journal

Web Domain: http://www.in-sightjournal.com

Individual Publication Date: February 8, 2020

Issue Publication Date: May 1, 2020

Name of Publisher: In-Sight Publishing

Frequency: Three Times Per Year

Words: 1,535

**ISSN 2369-6885**

**Abstract**

**In this paper, we show enhanced upper bounds of the nontrivial n_1 × n_2 × n_3 points problem for every n_1 ≤ n_2 ≤ n_3 < 6. We present new patterns that drastically improve the previously known algorithms for finding minimum-link covering paths, solving completely a few cases (e.g., n_1 = n_2 = 3 and n_3 = 4).**

*Keywords***: **Graph theory, Topology, Three-dimensional, Creative thinking, Link, Connectivity, Outside the box, Upper bound, Point, Game.

2010 Mathematics Subject Classification: 91A43, 05C57

**Solving the n_1×n_2×n_3 Points Problem for n_3 < 6[1] ^{,}[2]**

**Please see the footnotes, bibliography, and citation style listing after the interview.**

**Symbols and images did not proportion optimally and required a manual input. A P.D.F. available if this remains a preferred format for viewing the materials. Please click here.**

### 1 Introduction

The *n*_{1 }x *n*_{2 }x *n*_{3 }points problem [12] is a three-dimensional extension of the classic *nine dots problem* appeared in Samuel Loyd’s *Cyclopedia of Puzzles* [1-9], and it is related to the well known NP-hard traveling salesman problem, minimizing the number of turns in the tour instead of the total distance traveled [1-15].

Given *n*_{1 }⋅ *n*_{2 }⋅ *n*_{3} points in ℝ^{3}, our goal is to visit all of them (at least once) with a polygonal path that has the minimum number of line segments connected at their end-points (links or generically *lines*), the so called Minimum-link Covering Path [3-4-5-8]. In particular, we are interested in the best solutions for the nontrivial *n*_{1 }x *n*_{2 }x *n*_{3}_{ }points problem, where (by definition) 1 ≤ *n*_{1} ≤ *n*_{2 }≤ *n*_{3 }and *n*_{3 }< 6.

Let *h _{l} *(n

_{1 }, n

_{2 }, n

_{3}) ≤

*h*(

*n*

_{1 },

*n*

_{2 },

*n*

_{3}) ≤

*h*(

_{u }*n*

_{1 },

*n*

_{2 },

*n*

_{3}) be the length of the covering path with the minimum number of links for the

*n*

_{1 }x

*n*

_{2 }x

*n*

_{3}

_{ }points problem, we define the best known upper bound as

*h*(

_{u }*n*

_{1 },

*n*

_{2 },

*n*

_{3}) ≥

*h*(

*n*

_{1 },

*n*

_{2 },

*n*

_{3}) and we denote as

*h*(n

_{l}_{1 }, n

_{2 }, n

_{3}) ≤

*h*(

*n*

_{1 },

*n*

_{2 },

*n*

_{3}) the current proved lower bound [12].

For the simplest cases, the same problem has already been solved [3-12].

Let *n*_{1 }= 1 and n_{2 }< n_{3}, we have that* h *(*n*_{1 }, *n*_{2 }, *n*_{3}) = *h *(*n*_{2}) = 2 ⋅ *n*_{2 }– 1, while *h *(*n*_{1 }= 1, *n*_{2 }= *n*_{3 }≥ 3) = 2 ⋅ *n*_{2 }– 2 [6]. Hence, for* n*_{1 }= 2, it can be easily proved that

Therefore, the aim of the present paper is to solve the ten aforementioned nontrivial cases where the current upper bound does not match the proved lower bound.

### 2 Improving the solution of the *n*_{1 }x *n*_{2 }x *n*_{3 }points problem for n_{3 }< 6

In this complex brain challenge, we need to stretch our pattern recognition [7-10] in order to find a plastic strategy that improves the known upper bounds [3-13] for the most interesting cases (such as the nontrivial *n*_{1 }x *n*_{2 }x *n*_{2 }points problem and the* n*_{1 }x *n*_{1 }x (*n*_{1 +1}) set of puzzles), avoiding those standardized methods which are based on fixed patterns that lead to suboptimal covering paths, as the approaches presented in [2-8-11].

The current best results are listed in Table 1, and a direct proof follows for each nontrivial upper bound shown below.

Figures 3 to 12 show the patterns used to solve the *n*_{1 }x *n*_{2 }x *n*_{3 }puzzle (case by case). In particular, by combining the (2) with the original result shown in figure 4, we obtain a formal proof for the 3x3x4 points problem.

Finally, it is interesting to note that the improved *h _{u }*(

*n*

_{1 },

*n*

_{2 },

*n*

_{3}) can lower down the upper bound of the generalized

*k*-dimensional puzzle too. As an example, we can apply the aforementioned 3D patterns to the generalized

*n*

_{1 }x

*n*

_{2 }x … x

*n*

_{k}points problem using the simple method described in [12].

Let *k *≥ 4, given *n _{k}*

_{-1}≤ … ≤

*n*

_{4 }≤

*n*

_{1 }≤

*n*

_{2 }≤

*n*

_{3}, we can conclude that

**3 ****Conclusion**

In the present paper, we have drastically reduced the gap *h _{u} *(n

_{1 }, n

_{2 }, n

_{3}) –

*h*(

_{l }*n*

_{1 },

*n*

_{2 },

*n*

_{3}) for every previously unsolved puzzle such that n

_{3 }< 6. Moreover, we can easily disprove Bencini’s claim that

*h*(3,3,4) = 17 =

_{u }*h*(3,3,4) (see [2], page 7, lines 2-3), as shown by combining (2) with the upper bound from figure 4.

_{l}We do not know if any of the patterns shown in figures 5 to 12 represent optimal solutions, since (by definition) *h _{l} *(

*n*

_{1 },

*n*

_{2 },

*n*

_{3}) ≤

*h*(

*n*

_{1 },

*n*

_{2 },

*n*

_{3}). Therefore, some open questions about

*n*

_{1 }x

*n*

_{2 }x

*n*

_{3 }points problem remain to be answered, and the research in order to cancel the gap

*h*(

_{u}*n*

_{1 },

*n*

_{2 },

*n*

_{3}) –

*h*(

_{l }*n*

_{1 },

*n*

_{2 },

*n*

_{3}), at least for every

*n*

_{3}≤ 5, is not over yet.

**References**

[1] Aggarwal, A., Coppersmith, D., Khanna, S., Motwani, R., Schieber, B. (1999). The angular-metric traveling salesman problem. *SIAM Journal on Computing* **29**, 697–711.

[2] Bencini, V. (2019). n_1 n_2 n_3 Dots Puzzle: A Method to Improve the Current Upper Bound. *viXra*, 6 Jun. 2019, http://vixra.org/pdf/1906.0110v1.pdf

[3] Bereg, S., Bose, P., Dumitrescu, A., Hurtado, F., Valtr, P. (2009). Traversing a set of points with a minimum number of turns. *Discrete & Computational Geometry ***41(4)**, 513–532.

[4] Collins, M. J. (2004). Covering a set of points with a minimum number of turns. *International Journal* of *Computational Geometry* & Applications **14(1-2)**, 105–114.

[5] Collins, M.J., Moret, M.E. (1998). Improved lower bounds for the link length of rectilinear spanning paths in grids. *Information Processing Letters* **68(6)**, 317–319.

[6] Keszegh, B. (2013). Covering Paths and Trees for Planar Grids. *arXiv*, 3 Nov. 2013, https://arxiv.org/abs/1311.0452

[7] Kihn, M. (1995). Outside the Box: The Inside Story. *FastCompany*.

[8] Kranakis, E., Krizanc, D., Meertens, L. (1994). Link length of rectilinear Hamiltonian tours in grids. *Ars Combinatoria* **38**, 177–192.

[9] Loyd, S. (1914). Cyclopedia of Puzzles. *The Lamb Publishing Company*, p. 301.

[10] Lung, C. T., Dominowski, R. L. (1985). Effects of strategy instructions and practice on nine-dot problem solving. *Journal of Experimental Psychology: Learning, Memory, and Cognition* **11****(4)**, 804–811.

[11] Ripà, M., Bencini, V. (2018). n × n × n Dots Puzzle: An Improved “Outside The Box” Upper Bound. *viXra*, 25 Jul. 2018, http://vixra.org/pdf/1807.0384v2.pdf

[12] Ripà, M. (2014). The Rectangular Spiral or the n_{1} × n_{2} × … × n_{k} Points Problem. *Notes on Number Theory and Discrete Mathematics* **20(1)**, 59-71.

[13] Ripà, M. (2019). The 3 × 3 × … × 3 Points Problem solution. *Notes on Number Theory and Discrete Mathematics* **25(2)**, 68-75.

[14] Sloane, N. J. A. (2013). *The Online Encyclopedia of Integer Sequences*. Inc. 2 May. 2013. Web. 8 Jul. 2019, http://oeis.org/A225227

[15] Stein, C., Wagner, D.P. (2001). Approximation algorithms for the minimum bends traveling salesman problem. In: Aardal K., Gerards B. (eds) *Integer Programming and Combinatorial Optimization*. IPCO 2001. LNCS, vol 2081, 406–421. Springer, Berlin, Heidelberg.

**Appendix I: Footnotes**

[1] Founder, sPIqr Society; Creator, X-Test.

[2] Individual Publication Date: February 8, 2020: http://www.in-sightjournal.com/solving-the-n_1xn_2xn_3-points-problem-for-n_3-6-ripa; Full Issue Publication Date: May 1, 2020: https://in-sightjournal.com/insight-issues/. Image Credit: Marco Ripà.

**Appendix II: Citation Style Listing**

**American Medical Association (AMA):** Ripà M. *Solving the n_1×n_2×n_3 Points Problem for n_3 < 6 *[Online].February 2020; 22(B). Available from: http://www.in-sightjournal.com/http://www.in-sightjournal.com/solving-the-n_1xn_2xn_3-points-problem-for-n_3-6-ripa.

**American Psychological Association (APA, 6 ^{th} Edition, 2010):** Ripà, M. (2020, February 8).

*Solving the n_1×n_2×n_3 Points Problem for n_3 < 6*

*.*Retrieved from http://www.in-sightjournal.com/insights-testing-cooijmans.

**Brazilian National Standards (ABNT):** RIPA, M. *Solving the n_1×n_2×n_3 Points Problem for n_3 < 6**.* *In-Sight: Independent Interview-Based Journal*. 22.B, February. 2020. <http://www.in-sightjournal.com/insights-testing-cooijmans>.

**Chicago/Turabian, Author-Date (16 ^{th} Edition): **Ripà, M. 2020. “

*Solving the n_1×n_2×n_3 Points Problem for n_3 < 6*

*.*”

*In-Sight: Independent Interview-Based Journal.*22.B. http://www.in-sightjournal.com/insights-testing-cooijmans.

**Chicago/Turabian, Humanities (16 ^{th} Edition):** Ripà, Marco “

*Solving the n_1×n_2×n_3 Points Problem for n_3 < 6*

*.*”

*In-Sight: Independent Interview-Based Journal.*22.B (February 2020). http://www.in-sightjournal.com/insights-testing-cooijmans.

**Harvard: **Ripà, M. 2020, ‘*Solving the n_1×n_2×n_3 Points Problem for n_3 < 6**‘*, *In-Sight: Independent Interview-Based Journal*, vol. 22.B. Available from: <http://www.in-sightjournal.com/insights-testing-cooijmans>.

**Harvard, Australian: **Ripà, M. 2020, ‘*Solving the n_1×n_2×n_3 Points Problem for n_3 < 6**‘*, *In-Sight: Independent Interview-Based Journal*, vol. 22.B., http://www.in-sightjournal.com/insights-testing-cooijmans.

**Modern Language Association (MLA, 7 ^{th }Edition, 2009):** Marco Ripà. “

*Solving the n_1×n_2×n_3 Points Problem for n_3 < 6*.”

*In-Sight: Independent Interview-Based Journal*22.B (2020):February. 2020. Web. <http://www.in-sightjournal.com/insights-testing-cooijmans>.

**Vancouver/ICMJE: **Ripà M. *Solving the n_1×n_2×n_3 Points Problem for n_3 < 6** *[Internet]. (2020, February 22(B). Available from: http://www.in-sightjournal.com/insights-testing-cooijmans.

**License and Copyright**

**License**

*In-Sight Publishing* and *In-Sight: Independent Interview-Based Journal* by Scott Douglas Jacobsen is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Based on a work at www.in-sightjournal.com.

**Copyright**

© Scott Douglas Jacobsen, and* In-Sight Publishing* and *In-Sight: Independent Interview-Based Journal* 2012-2020. Unauthorized use and/or duplication of this material without express and written permission from this site’s author and/or owner is strictly prohibited. Excerpts and links may be used, provided that full and clear credit is given to Scott Douglas Jacobsen, and *In-Sight Publishing* and *In-Sight: Independent Interview-Based Journal* with appropriate and specific direction to the original content. All interviewees co-copyright their interview material and may disseminate for their independent purposes.

Comments are closed.