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 n1 x n2 x n3 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 n1 ⋅ n2 ⋅ n3 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 n1 x n2 x n3 points problem, where (by definition) 1 ≤ n1 ≤ n2 ≤ n3 and n3 < 6.
Let hl (n1 , n2 , n3) ≤ h (n1 , n2 , n3) ≤ hu (n1 , n2 , n3) be the length of the covering path with the minimum number of links for the n1 x n2 x n3 points problem, we define the best known upper bound as hu (n1 , n2 , n3) ≥ h (n1 , n2 , n3) and we denote as hl (n1 , n2 , n3) ≤ h (n1 , n2 , n3) the current proved lower bound [12].
For the simplest cases, the same problem has already been solved [3-12].
Let n1 = 1 and n2 < n3, we have that h (n1 , n2 , n3) = h (n2) = 2 ⋅ n2 – 1, while h (n1 = 1, n2 = n3 ≥ 3) = 2 ⋅ n2 – 2 [6]. Hence, for n1 = 2, it can be easily proved that
Figure 1. A trivial pattern that completely solves the 2 3 5 points puzzle.
Figure 2. Another example of a trivial case: the 2 5 5 points puzzle.
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 n1 x n2 x n3 points problem for n3 < 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 n1 x n2 x n2 points problem and the n1 x n1 x (n1 +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.
Table 1: Current solutions for the n1 x n2 x n3 points problem, where n1 ≤ n2 ≤ n3 ≤ 5.
Figures 3 to 12 show the patterns used to solve the n1 x n2 x n3 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.
Figure 3. hu (3,3,3) = hl (3,3,3) = 14. This solution has been proved to be optimal [12-13].
Figure 4. The 3x3x4 puzzle has finally been solved. hu = hl = 15 and no crossing lines.
Figure 5. Best known upper bound of the 3x4x4 puzzle. 19 = hu = hl + 2.
Figure 6. An original pattern for the 4x4x4 puzzle. 23 = hu = hl + 1 [13].
Figure 7. Best known upper bound of the 3x3x5 puzzle. 16 = hu = hl + 1 [13].
Figure 8. Best known upper bound of the 3x4x5 puzzle. 20 = hu = hl + 2.
Figure 9. Best known upper bound of the 3x4x5 puzzle. 24 = hu = hl + 4.
Figure 10. Best known upper bound of the 4x4x5 puzzle. 26 = hu = hl + 2.
Figure 11. Best known upper bound of the 4x5x5 puzzle. 31 = hu = hl + 4.
Figure 12. Best known upper bound of the 5x5x5 puzzle. 36 = hu = hl + 3.
Finally, it is interesting to note that the improved hu (n1 , n2 , n3) 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 n1 x n2 x … x nk points problem using the simple method described in [12].
Let k ≥ 4, given nk-1 ≤ … ≤ n4 ≤ n1 ≤ n2 ≤ n3, we can conclude that
3 Conclusion
In the present paper, we have drastically reduced the gap hu (n1 , n2 , n3) – hl (n1 , n2 , n3) for every previously unsolved puzzle such that n3 < 6. Moreover, we can easily disprove Bencini’s claim that hu (3,3,4) = 17 = hl (3,3,4) (see [2], page 7, lines 2-3), as shown by combining (2) with the upper bound from figure 4.
We do not know if any of the patterns shown in figures 5 to 12 represent optimal solutions, since (by definition) hl (n1 , n2 , n3) ≤ h (n1 , n2 , n3). Therefore, some open questions about n1 x n2 x n3 points problem remain to be answered, and the research in order to cancel the gap hu (n1 , n2 , n3) – hl (n1 , n2 , n3), at least for every n3 ≤ 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 n1 × n2 × … × nk 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.
[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, 6th 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 (16th 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 (16th 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, 7th 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.
In-Sight Publishing 
Comments are closed.