DOI: https://doi.org/10.14710/jfma.v6i2.18155

A BACKTRACKING APPROACH FOR SOLVING PATH PUZZLES

Joshua Erlangga Sakti  -  Computing Laboratory, Telkom University, Indonesia (40257)., Indonesia
*Muhammad Arzaki orcid scopus  -  Computing Laboratory, Telkom University, Indonesia (40257)., Indonesia
Gia Septiana Wulandari  -  Computing Laboratory, Telkom University, Indonesia (40257)., Indonesia

Citation Format:
Abstract

We study algorithmic aspects of the Path puzzle--a logic puzzle created in 2013 and confirmed NP-complete (Non-deterministic Polynomial-time-complete) in 2020. We propose a polynomial time algorithm for verifying an arbitrary Path puzzle solution and a backtracking-based method for finding a solution to an arbitrary Path puzzle instance.
To our knowledge, our study is the first rigorous investigation of an imperative algorithmic approach for solving Path puzzles. We prove that the asymptotic running time of our proposed method in solving an arbitrary Path puzzle instance of size $m \times n$ is $O(3^{mn})$. Despite this exponential upper bound, experimental results imply that a C++ implementation of our algorithm can quickly solve $6 \times 6$ Path puzzle instances in less than 30 milliseconds with an average of 3.02 milliseconds for 26 test cases. We finally prove that an $m \times n$ Path puzzle instance without row and column constraints is polynomially solvable in $O(\max\{m,n\})$ time.

Fulltext View|Download
Keywords: asymptotic running time; backtracking; NP-complete; Path puzzles

Article Metrics:

Article Info
Section: FUNDAMENTAL MATHEMATICS AND APPLICATIONS
Language : EN
Recent articles
MATHEMATICAL MODEL OF MEASLES DISEASE SPREAD WITH TWO-DOSE VACCINATION AND TREATMENT EXPLORING PHYSICS-INFORMED NEURAL NETWORKS FOR SOLVING BOUNDARY LAYER PROBLEMS FLOWER POLLINATION ALGORITHM (FPA): COMPARING SWITCH PROBABILITY BETWEEN CONSTANT 0.8 AND DOUBLE EXPONENTGUNAKAN DOUBLE EXPONENT More recent articles
  1. R. Kimball, Path Puzzles. Enigami Puzzles & Games, 2013. [Online]. Available:
  2. https://books.google.co.id/books?id=tDhaswEACAAJ
  3. New York Times Wordplay, “Roderick kimball’s path puzzles,” https://archive.nytimes
  4. com/wordplay.blogs.nytimes.com/2014/07/28/path-2/, Oct. 2022, accessed: 2022-11-14
  5. J. Bosboom, E. D. Demaine, M. L. Demaine, A. Hesterberg, R. Kimball, and
  6. J. Kopinsky, “Path puzzles: Discrete tomography with a path constraint is hard,”
  7. Graphs and Combinatorics, vol. 36, no. 2, pp. 251–267, 2020. [Online]. Available:
  8. https://link.springer.com/content/pdf/10.1007/s00373-019-02092-5.pdf
  9. S. Kim, “What is a puzzle,” in Game Design Workshop: A Playcentric Approach to
  10. Creating Innovative Games, 2008, pp. 35–39
  11. E. D. Demaine, “Playing games with algorithms: Algorithmic combinatorial game
  12. theory,” in International Symposium on Mathematical Foundations of Computer Science
  13. Springer, 2001, pp. 18–33
  14. G. Kendall, A. Parkes, and K. Spoerer, “A survey of NP-complete puzzles,” ICGA
  15. Journal, vol. 31, no. 1, pp. 13–34, 2008
  16. R. A. Hearn and E. D. Demaine, Games, puzzles, and computation. CRC Press, 2009
  17. R. Uehara, “Computational complexity of puzzles and related topics,” Interdisciplinary
  18. Information Sciences, pp. 1–22, 2023
  19. E. Friedman, “Corral puzzles are NP-complete,” Unpublished manuscript, August, 2002
  20. [Online]. Available: https://erich-friedman.github.io/papers/corral.pdf
  21. A. Ishibashi, Y. Sato, and S. Iwata, “NP-completeness of two pencil puzzles: Yajilin and
  22. Country Road,” Utilitas Mathematica, vol. 88, pp. 237–246, 2012
  23. D. Andersson, “Hashiwokakero is NP-complete,” Information Processing Letters, vol
  24. , no. 19, pp. 1145–1146, 2009
  25. D. Andersson, “Hiroimono is NP-complete,” in International Conference on Fun with
  26. Algorithms. Springer, 2007, pp. 30–39
  27. C. Iwamoto and T. Ibusuki, “Kurotto and Juosan are NP-complete,” in The 21st Japan
  28. Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCG3
  29. , 2018, pp. 46–48. [Online]. Available: https://link.springer.com/chapter/10.1007/
  30. -3-030-90048-9 14
  31. C. Iwamoto and T. Ibusuki, “Polynomial-time reductions from 3SAT to Kurotto and
  32. Juosan puzzles,” IEICE Transactions on Information and Systems, vol. 103, no. 3, pp
  33. –505, 2020. [Online]. Available: https://www.jstage.jst.go.jp/article/transinf/E103.D/
  34. /E103.D 2019FCP0004/ pdf
  35. D. Kr´al, V. Majerech, J. Sgalla, T. Tich´y, and G.Woegingerd, “It is tough to be a plumber,”
  36. Theoretical computer science, vol. 313, pp. 473–484, 2004
  37. B. McPhail, “Light Up is NP-complete,” Unpublished manuscript, 2005
  38. R. Kaye, “Minesweeper is NP-complete,” Mathematical Intelligencer, vol. 22, no. 2, pp
  39. –15, 2000
  40. C. Iwamoto and T. Ide, “Moon-or-Sun, Nagareru, and Nurimeizu are NP-complete,”
  41. IEICE Transactions on Fundamentals of Electronics, Communications and Computer
  42. Sciences, p. 2021DMP0006, 2022. [Online]. Available: https://www.jstage.jst.go.jp/
  43. article/transfun/advpub/0/advpub 2021DMP0006/ article/-char/ja/
  44. N. Ueda and T. Nagao, “NP-completeness results for Nonogram via parsimonious
  45. reductions,” Department of Computer Science, Tokyo Institute of Technology, Tech. Rep.,
  47. B. P. McPhail, “Complexity of puzzles: NP-Completeness results for Nurikabe and
  48. Minesweeper,” Ph.D. dissertation, Reed College, 2003
  49. M. Holzer, A. Klein, and M. Kutrib, “On the NP-completeness of the Nurikabe pencil
  50. puzzle and variants thereof,” in Proceedings of the 3rd International Conference on FUN
  51. with Algorithms. Citeseer, 2004, pp. 77–89
  52. E. Friedman, “Pearl puzzles are NP-complete,” Unpublished manuscript, August, 2002
  53. [Online]. Available: https://erich-friedman.github.io/papers/pearl.pdf
  54. Y. Takenaga, S. Aoyagi, S. Iwata, and T. Kasai, “Shikaku and Ripple Effect are NPcomplete,”
  55. Congressus Numerantium, vol. 216, pp. 119–127, 2013
  56. Y. Takayuki, “On the NP-completeness of the Slither Link puzzle,” IPSJ SIGNotes
  57. ALgorithms, 2000
  58. T. Yato and T. Seta, “Complexity and completeness of finding another solution
  59. and its application to puzzles,” IEICE transactions on fundamentals of electronics,
  60. communications and computer sciences, vol. 86, no. 5, pp. 1052–1060, 2003
  61. L. Robert, D. Miyahara, P. Lafourcade, L. Libralesso, and T. Mizuki, “Physical
  62. zero-knowledge proof and NP-completeness proof of Suguru puzzle,” Information and
  63. Computation, vol. 285, p. 104858, 2022. [Online]. Available: https://www.sciencedirect
  64. com/science/article/pii/S0890540121001905
  65. A. Adler, J. Bosboom, E. D. Demaine, M. L. Demaine, Q. C. Liu, and J. Lynch,
  66. “Tatamibari is NP-Complete,” in 10th International Conference on Fun with Algorithms
  67. (FUN 2021), ser. Leibniz International Proceedings in Informatics (LIPIcs), M. Farach-
  68. Colton, G. Prencipe, and R. Uehara, Eds., vol. 157. Dagstuhl, Germany: Schloss
  69. Dagstuhl–Leibniz-Zentrum f¨ur Informatik, 2020, pp. 1:1–1:24. [Online]. Available:
  70. https://drops.dagstuhl.de/opus/volltexte/2020/12762
  71. C. Iwamoto and T. Ide, “Five Cells and Tilepaint are NP-Complete,” IEICE Transcations
  72. on Information and Systems, vol. 105, no. 3, pp. 508–516, 2022. [Online]. Available:
  73. https://www.jstage.jst.go.jp/article/transinf/E105.D/3/E105.D 2021FCP0001/ pdf
  74. E. D. Demaine, J. Lynch, M. Rudoy, and Y. Uno, “Yin-Yang Puzzles are NP-complete,”
  75. in 33rd Canadian Conference on Computational Geometry (CCCG) 2021, 2021
  76. S. Saha and E. D. Demaine, “ZHED is NP-complete,” in Proceedings of the 34th
  77. Canadian Conference on Computational Geometry (CCCG 2022), 2022. [Online]
  78. Available: https://erikdemaine.org/papers/Zhed CCCG2022/paper.pdf
  79. E. D. Demaine, Y. Okamoto, R. Uehara, and Y. Uno, “Computational complexity and
  80. an integer programming model of Shakashaka,” IEICE Transactions on Fundamentals
  81. of Electronics, Communications and Computer Sciences, vol. 97, no. 6, pp. 1213–1219,
  83. A. Bartlett, T. P. Chartier, A. N. Langville, and T. D. Rankin, “An integer programming
  84. model for the Sudoku problem,” Journal of Online Mathematics and its Applications,
  85. vol. 8, no. 1, 2008
  86. C. Bright, J. Gerhard, I. Kotsireas, and V. Ganesh, “Effective problem solving using SAT
  87. solvers,” in Maple Conference. Springer, 2019, pp. 205–219
  88. E. C. Reinhard, M. Arzaki, and G. S. Wulandari, “Solving Tatamibari Puzzle Using
  89. Exhaustive Search Approach,” Indonesia Journal on Computing (Indo-JC), vol. 7, no. 3,
  90. pp. 53–80, 2022
  91. M. I. Putra, M. Arzaki, and G. S. Wulandari, “Solving Yin-Yang Puzzles Using
  92. Exhaustive Search and Prune-and-Search Algorithms,” (IJCSAM) International Journal
  93. of Computing Science and Applied Mathematics, vol. 8, no. 2, pp. 52–65, 2022
  94. M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of
  95. NP-Completeness. WH Freeman & Co., 1979
  96. H. Ryser, “Combinatorial properties of matrices of zeros and ones,” Canadian Journal of
  97. Mathematics, vol. 9, pp. 371–377, 1957
  98. G. T. Herman and A. Kuba, Discrete tomography: Foundations, algorithms, and
  99. applications. Springer Science & Business Media, 2012
  100. H. J. Hoogeboom, W. A. Kosters, J. N. van Rijn, and J. K. Vis, “Acyclic constraint logic
  101. and games,” ICGA Journal, vol. 37, no. 1, pp. 3–16, 2014
  102. L. Prechelt, “An empirical comparison of seven programming languages,” Computer,
  103. vol. 33, no. 10, pp. 23–29, 2000
  104. E. D. Demaine, “Path Puzzles Font,” https://github.com/edemaine/font-pathpuzzles, Oct
  105. , accessed: 2022-10-11
  106. S. Brunetti and A. Daurat, “An algorithm reconstructing convex lattice sets,”
  107. Theoretical Computer Science, vol. 304, no. 1, pp. 35–57, 2003. [Online]. Available:
  108. https://www.sciencedirect.com/science/article/pii/S0304397503000501

Last update:

No citation recorded.

Last update:

No citation recorded.