Skip to content

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

February 8, 2020

 

 

 

 

 

 

 

 

 

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 ≤ n1n2 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

F1

1

Figure 1. A trivial pattern that completely solves the 2 3 5 points puzzle.

2

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].

F2

F3

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

Table 1

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.

3

Figure 3. hu (3,3,3) = hl (3,3,3) = 14. This solution has been proved to be optimal [12-13].

4

Figure 4. The 3x3x4 puzzle has finally been solved. hu = hl = 15 and no crossing lines.

5

Figure 5. Best known upper bound of the 3x4x4 puzzle. 19 = hu = hl + 2.

6

Figure 6. An original pattern for the 4x4x4 puzzle. 23 = hu = hl + 1 [13].

7

Figure 7. Best known upper bound of the 3x3x5 puzzle. 16 = hu = hl + 1 [13].

8

Figure 8. Best known upper bound of the 3x4x5 puzzle. 20 = hu = hl + 2.

9

Figure 9. Best known upper bound of the 3x4x5 puzzle. 24 = hu = hl + 4.

10

Figure 10. Best known upper bound of the 4x4x5 puzzle. 26 = hu = hl + 2.

11

Figure 11. Best known upper bound of the 4x5x5 puzzle. 31 = hu = hl + 4.

12

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

F4

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.

Appendix I: Footnotes

[1] FoundersPIqr 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 < 6Retrieved 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 < 6In-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 < 6In-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.

Comments are closed.

%d bloggers like this: