Elementary Search-based Algorithms for Solving Tilepaint Puzzles
Abstract views: 143
,
750 downloads: 144
Keywords:
complete search, complexity, prune-and-search, Tilepaint puzzle, tractable subproblems, reduction
Abstract
This paper discusses the elementary computational aspects of Tilepaint puzzles, single-player logic puzzles introduced in 1995 and confirmed NP-complete in 2022. Two elementary search-based algorithms are proposed: the complete search technique with a bitmasking approach and the prune-and-search technique with a backtracking approach and pruning optimization. This paper shows that the asymptotic running time of these algorithms for solving an $m \times n$ Tilepaint instance containing $p$ tiles are respectively $O(2^{p} \cdot p \cdot mn)$ and $O(2^{p} \cdot mn)$, implying that the latter method is asymptotically faster by a factor of $p$. This paper also discusses tractable and intractable variants of Tilepaint puzzles. This paper shows that an $m \times n$ Tilepaint instance containing $mn$ tiles of size $1 \times 1$ is solvable in polynomial time. In contrast, this paper shows that solving general $m \times 1$ and $1 \times n$ Tilepaint puzzles remains intractable by reducing such problems from the subset-sum problem.
Downloads
Download data is not yet available.
References
[1] conceptispuzzles, “Cross-a-pix history,†https://www.conceptispuzzles.com/index.aspx?uri=puzzle/cross-a-pix/
history#:~:text=SingleClue%20Cross%2Da%2DPix%20are,by%20Toshiharu%20Yamamoto%20in%20Japan., Nov. 2022, accessed: 2022-11-21.
[2] W. Ting-Sheng, “Enhancing Problem-Solving Ability through a Puzzle-Type Logical Thinking Game,†Scientific Programming, vol. 2022, pp. 1–9, 03 2022.
[3] E. D. Demaine, “Playing games with algorithms: Algorithmic combinatorial game theory,†in International Symposium on Mathematical Foundations of Computer Science. Springer, 2001, pp. 18–33.
[4] G. Kendall, A. Parkes, and K. Spoerer, “A survey of NP-complete puzzles,†ICGA Journal, vol. 31, no. 1, pp. 13–34, 2008.
[5] R. A. Hearn and E. D. Demaine, Games, puzzles, and computation. CRC Press, 2009.
[6] C. Iwamoto and T. Ide, “Five cells and tilepaint are NP-complete,†IEICE Transactions on Information and Systems, vol. 105, no. 3, pp. 508–516, 2022.
[7] C. Iwamoto and T. Ibusuki, “Computational Complexity of Two Pencil Puzzles: Kurotto and Juosan,†in Discrete and Computational Geometry, Graphs, and Games: 21st Japanese Conference, JCDCGGG 2018, Quezon City, Philippines, September 1-3, 2018, Revised Selected Papers 21. Springer, 2021, pp. 175–185.
[8] R. Kaye, “Minesweeper is NP-complete,†Mathematical Intelligencer, vol. 22, no. 2, pp. 9–15, 2000.
[9] C. Iwamoto and T. Ide, “Moon-or-Sun, Nagareru, and Nurimeizu are NP-complete,†IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol. 105, no. 9, pp. 1187–1194, 2022.
[10] N. Ueda and T. Nagao, “NP-completeness results for Nonogram via parsimonious reductions,†Department of Computer Science, Tokyo Institute of Technology, Tech. Rep., 1996.
[11] J. Bosboom, E. D. Demaine, M. L. Demaine, A. Hesterberg, R. Kimball, and J. Kopinsky, “Path puzzles: Discrete tomography with a path constraint is hard,†Graphs and Combinatorics, vol. 36, no. 2, pp. 251–267, 2020. [Online].
[12] T. Yato and T. Seta, “Complexity and completeness of finding another solution and its application to puzzles,†IEICE transactions on fundamentals of electronics, communications and computer sciences, vol. 86, no. 5, pp. 1052–1060, 2003.
[13] L. Robert, D. Miyahara, P. Lafourcade, L. Libralesso, and T. Mizuki, “Physical zero-knowledge proof and NP-completeness proof of Suguru puzzle,†Information and Computation, vol. 285, p. 104858, 2022. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0890540121001905
[14] A. Adler, J. Bosboom, E. D. Demaine, M. L. Demaine, Q. C. Liu, and J. Lynch, “Tatamibari is NP-Complete,†in 10th International Conference on Fun with Algorithms (FUN 2021), ser. Leibniz International Proceedings in Informatics (LIPIcs), M. Farach-Colton, G. Prencipe, and R. Uehara, Eds., vol. 157. Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2020, pp. 1:1–1:24. [Online]. Available: https://drops.dagstuhl.de/opus/volltexte/2020/12762
[15] E. D. Demaine, J. Lynch, M. Rudoy, and Y. Uno, “Yin-Yang Puzzles are NP-complete,†in 33rd Canadian Conference on Computational Geometry (CCCG) 2021, 2021.
[16] E. D. Demaine, Y. Okamoto, R. Uehara, and Y. Uno, “Computational complexity and an integer programming model of Shakashaka,†IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol. 97, no. 6, pp. 1213–1219, 2014.
[17] T. Weber, “A SAT-based Sudoku solver,†in LPAR, 2005, pp. 11–15.
[18] I. Lynce and J. Ouaknine, “Sudoku as a SAT Problem,†in AI&M, 2006.
[19] C. Bright, J. Gerhard, I. Kotsireas, and V. Ganesh, “Effective problem solving using SAT solvers,†in Maple Conference. Springer, 2019, pp. 205–219.
[20] M. I. Putra, M. Arzaki, and G. S. Wulandari, “Solving Yin-Yang Puzzles Using Exhaustive Search and Prune-and-Search Algorithms,†(IJCSAM) International Journal of Computing Science and Applied Mathematics, vol. 8, no. 2, pp. 52–65, 2022.
[21] E. C. Reinhard, M. Arzaki, and G. S. Wulandari, “Solving Tatamibari Puzzle Using Exhaustive Search Approach,†Indonesia Journal on Computing (Indo-JC), vol. 7, no. 3, pp. 53–80, Dec. 2022. [Online]. Available: https://socj.telkomuniversity.ac.id/ojs/index.php/indojc/article/view/675
[22] H. Ryser, “Combinatorial Properties of Matrices of Zeros and Ones,†Canadian Journal of Mathematics, vol. 9, pp. 371–377, 1957.
[23] G. T. Herman and A. Kuba, Discrete tomography: Foundations, algorithms, and applications. Springer Science & Business Media, 2012.
[24] C. Bessiere, C. Carbonnel, E. Hebrard, G. Katsirelos, and T.Walsh, “Detecting and exploiting subproblem tractability,†in IJCAI: International Joint Conference on Artificial Intelligence, 2013, pp. 468–474.
[25] J. Dreier, S. Ordyniak, and S. Szeider, “CSP Beyond Tractable Constraint Languages,†in 28th International Conference on Principles and Practice of Constraint Programming (CP 2022). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2022.
[26] M. R. Garey and D. S. Johnson, Computers and intractability. W. H. Freeman San Francisco, 1979, vol. 174.
[27] R. Neapolitan and K. Naimipour, Foundations of algorithms. Jones & Bartlett Publishers, 2010.
[28] B. Aspvall, M. F. Plass, and R. E. Tarjan, “A linear-time algorithm for testing the truth of certain quantified boolean formulas,†Information processing letters, vol. 8, no. 3, pp. 121–123, 1979.
[29] S. Brunetti and A. Daurat, “An algorithm reconstructing convex lattice sets,†Theoretical Computer Science, vol. 304, no. 1, pp. 35–57, 2003. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0304397503000501
[30] A. P. Stolk, “Discrete tomography for integer-valued functions,†Ph.D. dissertation, Leiden University, 2011.
[31] S. Asif, M. Coulombe, E. D. Demaine, M. L. Demaine, A. Hesterberg, J. Lynch, and M. Singhal, “Tetris is NP-hard even with O(1) Rows or Columns,†Journal of Information Processing, vol. 28, pp. 942–958, 2020.
[32] B. Barak, “Introduction to theoretical computer science,†https://introtcs.org/public/lec_12_NP.html, 2023, accessed: 2023-3-27.
[33] K. Abrahamson, “The subset sum problem,†http://www.cs.ecu.edu/karl/6420/spr16/Notes/NPcomplete/ss.html, 2016,
accessed: 2023-6-19.
[34] L. Prechelt, “An empirical comparison of seven programming languages,†Computer, vol. 33, no. 10, pp. 23–29, 2000.
[35] Otto Janko, “Tairupainto,†https://www.janko.at/Raetsel/Tairupeinto/index.htm, Oct. 2022, accessed: 2022-10-11.
history#:~:text=SingleClue%20Cross%2Da%2DPix%20are,by%20Toshiharu%20Yamamoto%20in%20Japan., Nov. 2022, accessed: 2022-11-21.
[2] W. Ting-Sheng, “Enhancing Problem-Solving Ability through a Puzzle-Type Logical Thinking Game,†Scientific Programming, vol. 2022, pp. 1–9, 03 2022.
[3] E. D. Demaine, “Playing games with algorithms: Algorithmic combinatorial game theory,†in International Symposium on Mathematical Foundations of Computer Science. Springer, 2001, pp. 18–33.
[4] G. Kendall, A. Parkes, and K. Spoerer, “A survey of NP-complete puzzles,†ICGA Journal, vol. 31, no. 1, pp. 13–34, 2008.
[5] R. A. Hearn and E. D. Demaine, Games, puzzles, and computation. CRC Press, 2009.
[6] C. Iwamoto and T. Ide, “Five cells and tilepaint are NP-complete,†IEICE Transactions on Information and Systems, vol. 105, no. 3, pp. 508–516, 2022.
[7] C. Iwamoto and T. Ibusuki, “Computational Complexity of Two Pencil Puzzles: Kurotto and Juosan,†in Discrete and Computational Geometry, Graphs, and Games: 21st Japanese Conference, JCDCGGG 2018, Quezon City, Philippines, September 1-3, 2018, Revised Selected Papers 21. Springer, 2021, pp. 175–185.
[8] R. Kaye, “Minesweeper is NP-complete,†Mathematical Intelligencer, vol. 22, no. 2, pp. 9–15, 2000.
[9] C. Iwamoto and T. Ide, “Moon-or-Sun, Nagareru, and Nurimeizu are NP-complete,†IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol. 105, no. 9, pp. 1187–1194, 2022.
[10] N. Ueda and T. Nagao, “NP-completeness results for Nonogram via parsimonious reductions,†Department of Computer Science, Tokyo Institute of Technology, Tech. Rep., 1996.
[11] J. Bosboom, E. D. Demaine, M. L. Demaine, A. Hesterberg, R. Kimball, and J. Kopinsky, “Path puzzles: Discrete tomography with a path constraint is hard,†Graphs and Combinatorics, vol. 36, no. 2, pp. 251–267, 2020. [Online].
[12] T. Yato and T. Seta, “Complexity and completeness of finding another solution and its application to puzzles,†IEICE transactions on fundamentals of electronics, communications and computer sciences, vol. 86, no. 5, pp. 1052–1060, 2003.
[13] L. Robert, D. Miyahara, P. Lafourcade, L. Libralesso, and T. Mizuki, “Physical zero-knowledge proof and NP-completeness proof of Suguru puzzle,†Information and Computation, vol. 285, p. 104858, 2022. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0890540121001905
[14] A. Adler, J. Bosboom, E. D. Demaine, M. L. Demaine, Q. C. Liu, and J. Lynch, “Tatamibari is NP-Complete,†in 10th International Conference on Fun with Algorithms (FUN 2021), ser. Leibniz International Proceedings in Informatics (LIPIcs), M. Farach-Colton, G. Prencipe, and R. Uehara, Eds., vol. 157. Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2020, pp. 1:1–1:24. [Online]. Available: https://drops.dagstuhl.de/opus/volltexte/2020/12762
[15] E. D. Demaine, J. Lynch, M. Rudoy, and Y. Uno, “Yin-Yang Puzzles are NP-complete,†in 33rd Canadian Conference on Computational Geometry (CCCG) 2021, 2021.
[16] E. D. Demaine, Y. Okamoto, R. Uehara, and Y. Uno, “Computational complexity and an integer programming model of Shakashaka,†IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol. 97, no. 6, pp. 1213–1219, 2014.
[17] T. Weber, “A SAT-based Sudoku solver,†in LPAR, 2005, pp. 11–15.
[18] I. Lynce and J. Ouaknine, “Sudoku as a SAT Problem,†in AI&M, 2006.
[19] C. Bright, J. Gerhard, I. Kotsireas, and V. Ganesh, “Effective problem solving using SAT solvers,†in Maple Conference. Springer, 2019, pp. 205–219.
[20] M. I. Putra, M. Arzaki, and G. S. Wulandari, “Solving Yin-Yang Puzzles Using Exhaustive Search and Prune-and-Search Algorithms,†(IJCSAM) International Journal of Computing Science and Applied Mathematics, vol. 8, no. 2, pp. 52–65, 2022.
[21] E. C. Reinhard, M. Arzaki, and G. S. Wulandari, “Solving Tatamibari Puzzle Using Exhaustive Search Approach,†Indonesia Journal on Computing (Indo-JC), vol. 7, no. 3, pp. 53–80, Dec. 2022. [Online]. Available: https://socj.telkomuniversity.ac.id/ojs/index.php/indojc/article/view/675
[22] H. Ryser, “Combinatorial Properties of Matrices of Zeros and Ones,†Canadian Journal of Mathematics, vol. 9, pp. 371–377, 1957.
[23] G. T. Herman and A. Kuba, Discrete tomography: Foundations, algorithms, and applications. Springer Science & Business Media, 2012.
[24] C. Bessiere, C. Carbonnel, E. Hebrard, G. Katsirelos, and T.Walsh, “Detecting and exploiting subproblem tractability,†in IJCAI: International Joint Conference on Artificial Intelligence, 2013, pp. 468–474.
[25] J. Dreier, S. Ordyniak, and S. Szeider, “CSP Beyond Tractable Constraint Languages,†in 28th International Conference on Principles and Practice of Constraint Programming (CP 2022). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2022.
[26] M. R. Garey and D. S. Johnson, Computers and intractability. W. H. Freeman San Francisco, 1979, vol. 174.
[27] R. Neapolitan and K. Naimipour, Foundations of algorithms. Jones & Bartlett Publishers, 2010.
[28] B. Aspvall, M. F. Plass, and R. E. Tarjan, “A linear-time algorithm for testing the truth of certain quantified boolean formulas,†Information processing letters, vol. 8, no. 3, pp. 121–123, 1979.
[29] S. Brunetti and A. Daurat, “An algorithm reconstructing convex lattice sets,†Theoretical Computer Science, vol. 304, no. 1, pp. 35–57, 2003. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0304397503000501
[30] A. P. Stolk, “Discrete tomography for integer-valued functions,†Ph.D. dissertation, Leiden University, 2011.
[31] S. Asif, M. Coulombe, E. D. Demaine, M. L. Demaine, A. Hesterberg, J. Lynch, and M. Singhal, “Tetris is NP-hard even with O(1) Rows or Columns,†Journal of Information Processing, vol. 28, pp. 942–958, 2020.
[32] B. Barak, “Introduction to theoretical computer science,†https://introtcs.org/public/lec_12_NP.html, 2023, accessed: 2023-3-27.
[33] K. Abrahamson, “The subset sum problem,†http://www.cs.ecu.edu/karl/6420/spr16/Notes/NPcomplete/ss.html, 2016,
accessed: 2023-6-19.
[34] L. Prechelt, “An empirical comparison of seven programming languages,†Computer, vol. 33, no. 10, pp. 23–29, 2000.
[35] Otto Janko, “Tairupainto,†https://www.janko.at/Raetsel/Tairupeinto/index.htm, Oct. 2022, accessed: 2022-10-11.
Published
2023-08-30
How to Cite
Fridolin, V. A., Arzaki, M., & Wulandari, G. S. (2023). Elementary Search-based Algorithms for Solving Tilepaint Puzzles. Indonesia Journal on Computing (Indo-JC), 8(2), 36-64. https://doi.org/10.34818/INDOJC.2023.8.2.750
Section
Computer Science
Copyright (c) 2023 Vincentius Arnold Fridolin, Muhammad Arzaki, Gia Septiana Wulandari
This work is licensed under a Creative Commons Attribution 4.0 International License.
- Manuscript submitted to IndoJC has to be an original work of the author(s), contains no element of plagiarism, and has never been published or is not being considered for publication in other journals.Â
- Copyright on any article is retained by the author(s). Regarding copyright transfers please see below.
- Authors grant IndoJC a license to publish the article and identify itself as the original publisher.
- Authors grant IndoJC commercial rights to produce hardcopy volumes of the journal for sale to libraries and individuals.
- Authors grant any third party the right to use the article freely as long as its original authors and citation details are identified.
- The article and any associated published material is distributed under the Creative Commons Attribution 4.0License
