Solving Tatamibari Puzzle Using Exhaustive Search Approach
DOI:
https://doi.org/10.34818/INDOJC.2022.7.3.675Keywords:
Asymptotic Analysis, Exhaustive Search Algorithms, Tatamibari PuzzleAbstract
Tatamibari is a puzzle that was first published in 2004 and was proven to be NP-complete in 2020. However, to the best of our knowledge, algorithmic investigation of the Tatamibari puzzle is relatively new and limited. There are discussions about an approach for solving the Tatamibari puzzle using the Z3 SMT solver, but there are no details regarding the steps of the algorithm as well as its explicit asymptotic upper bound. In addition, this solver requires an additional library that cannot be directly executed using standard libraries in an arbitrary imperative programming language. Hence, this paper discusses an exhaustive search approach for solving an arbitrary Tatamibari puzzle. We show that this algorithm can find all solutions to an \(m \times n\) Tatamibari instance with \(h\) hints in \(O(\max\{m^2 n^2, h^{mn-h} \cdot hmn\})\) time. We also use this algorithm to find the number of possible Tatamibari solutions in an \(m \times n\) grid for some small values of \(m\) and \(n\).
Downloads
Download data is not yet available.
References
[1] Nikoli, “Puzzle Communication Nikoli: Omopa List,†https://www.nikoli.co.jp/ja/publication/various/nikoli/omopalist/, Sep. 2022, accessed: 2022-09-19.
[2] 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
[3] A. Allen and A. Williams, “Sto-Stone is NP-Complete,†in CCCG, 2018, pp. 28–34.
[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] 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.
[6] R. A. Hearn and E. D. Demaine, Games, puzzles, and computation. CRC Press, 2009.
[7] M. Holzer, A. Klein, and M. Kutrib, “On the NP-completeness of the Nurikabe pencil puzzle and variants thereof,†in Proceedings of the 3rd International Conference on FUN with Algorithms. Citeseer, 2004, pp. 77–89.
[8] 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.
[9] A. Ishibashi, Y. Sato, and S. Iwata, “NP-completeness of two pencil puzzles: Yajilin and Country Road,†Utilitas Mathematica, vol. 88, pp. 237–246, 2012.
[10] C. Iwamoto and T. Ibusuki, “Dosun-Fuwari is NP-complete,†Journal of Information Processing, vol. 26, pp. 358–361, 2018.
[11] A. Uejima and H. Suzuki, “Fillmat is NP-complete and ASP-complete,†Journal of Information Processing, vol. 23, no. 3, pp. 310–316, 2015.
[12] 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.
[13] D. Andersson, “Hashiwokakero is NP-complete,†Information Processing Letters, vol. 109, no. 19, pp. 1145–1146, 2009.
[14] C. Iwamoto, M. Haruishi, and T. Ibusuki, “Herugolf and Makaro are NP-complete,†in 9th International Conference on Fun with Algorithms (FUN 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018.
[15] M. Holzer and O. Ruepp, “The troubles of interior design–a complexity analysis of the game Heyawake,†in International Conference on Fun with Algorithms. Springer, 2007, pp. 198–212.
[16] D. Andersson, “Hiroimono is NP-complete,†in International Conference on Fun with Algorithms. Springer, 2007, pp. 30–39.
[17] C. Iwamoto and T. Ibusuki, “Polynomial-Time Reductions from 3SAT to Kurotto and Juosan Puzzles,†IEICE Transactions on Information and Systems, vol. 103, no. 3, pp. 500–505, 2020.
[18] J. Kölker, “Kurodoko is NP-complete,†Information and Media Technologies, vol. 7, no. 3, pp. 1000–1012, 2012.
[19] C. Iwamoto and T. Ide, “Moon-or-Sun, Nagareru, and Nurimeizu are NP-complete,†IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, p. 2021DMP0006, 2022.
[20] Y. Takenaga, S. Aoyagi, S. Iwata, and T. Kasai, “Shikaku and Ripple Effect are NP-complete,†Congressus Numerantium, vol. 216, pp. 119–127, 2013.
[21] 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.
[22] C. Iwamoto and M. Haruishi, “Computational complexity of Usowan puzzles,†IEICE Transactions on Fundamentals of
Electronics, Communications and Computer Sciences, vol. 101, no. 9, pp. 1537–1540, 2018.
[23] 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.
[24] C. Iwamoto, “Yosenabe is NP-complete,†Journal of Information Processing, vol. 22, no. 1, pp. 40–43, 2014.
[25] A. Adler, J. Bosboom, E. D. Demaine, M. L. Demaine, Q. C. Liu, and J. Lynch, “Z3-based Tatamibari solver, and figures from Tatamibari NP-hardness paper,†https://github.com/jbosboom/tatamibari-solver, Feb. 2020, accessed: 2022-07-28.
[26] J. J. W. Bosboom, “Exhaustive search and hardness proofs for games,†Ph.D. dissertation, Massachusetts Institute of Technology, 2020.
[27] T. Weber, “A SAT-based Sudoku solver,†in LPAR, 2005, pp. 11–15.
[28] I. Lynce and J. Ouaknine, “Sudoku as a SAT Problem,†in AI&M, 2006.
[29] U. Pfeiffer, T. Karnagel, and G. Scheffler, “A Sudoku-Solver for Large Puzzles using SAT,†in LPAR short papers (Yogyakarta), 2010, pp. 52–57.
[30] M. Z. Musa, “Interactive Sudoku Solver Using Propositional Logic in Python,†Bachelor Thesis, Undergraduate Program of Informatics, School of Computing, Telkom University, 2018.
[31] A. Shaleh, “Solving Shikaku Using Propositional Logic Approach,†Bachelor Thesis, Undergraduate Program of Informatics, School of Computing, Telkom University, 2019.
[32] M. d. Berg and A. Khosravi, “Optimal binary space partitions in the plane,†in International Computing and Combinatorics Conference. Springer, 2010, pp. 216–225.
[33] A. Sharma, “Combinations from n arrays picking one element from each array,†https://www.geeksforgeeks.org/ combinations-from-n-arrays-picking-one-element-from-each-array/, Apr. 2022, accessed: 2022-04-27.
[34] L. Prechelt, “Are scripting languages any good? A validation of Perl, Python, Rexx, and Tcl against C, C++, and Java.†Adv. Comput., vol. 57, pp. 205–270, 2003.
[35] E. D. Demaine, “Tatamibari Font,†https://github.com/edemaine/font-tatamibari, Apr. 2022, accessed: 2022-05-11.
[2] 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
[3] A. Allen and A. Williams, “Sto-Stone is NP-Complete,†in CCCG, 2018, pp. 28–34.
[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] 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.
[6] R. A. Hearn and E. D. Demaine, Games, puzzles, and computation. CRC Press, 2009.
[7] M. Holzer, A. Klein, and M. Kutrib, “On the NP-completeness of the Nurikabe pencil puzzle and variants thereof,†in Proceedings of the 3rd International Conference on FUN with Algorithms. Citeseer, 2004, pp. 77–89.
[8] 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.
[9] A. Ishibashi, Y. Sato, and S. Iwata, “NP-completeness of two pencil puzzles: Yajilin and Country Road,†Utilitas Mathematica, vol. 88, pp. 237–246, 2012.
[10] C. Iwamoto and T. Ibusuki, “Dosun-Fuwari is NP-complete,†Journal of Information Processing, vol. 26, pp. 358–361, 2018.
[11] A. Uejima and H. Suzuki, “Fillmat is NP-complete and ASP-complete,†Journal of Information Processing, vol. 23, no. 3, pp. 310–316, 2015.
[12] 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.
[13] D. Andersson, “Hashiwokakero is NP-complete,†Information Processing Letters, vol. 109, no. 19, pp. 1145–1146, 2009.
[14] C. Iwamoto, M. Haruishi, and T. Ibusuki, “Herugolf and Makaro are NP-complete,†in 9th International Conference on Fun with Algorithms (FUN 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018.
[15] M. Holzer and O. Ruepp, “The troubles of interior design–a complexity analysis of the game Heyawake,†in International Conference on Fun with Algorithms. Springer, 2007, pp. 198–212.
[16] D. Andersson, “Hiroimono is NP-complete,†in International Conference on Fun with Algorithms. Springer, 2007, pp. 30–39.
[17] C. Iwamoto and T. Ibusuki, “Polynomial-Time Reductions from 3SAT to Kurotto and Juosan Puzzles,†IEICE Transactions on Information and Systems, vol. 103, no. 3, pp. 500–505, 2020.
[18] J. Kölker, “Kurodoko is NP-complete,†Information and Media Technologies, vol. 7, no. 3, pp. 1000–1012, 2012.
[19] C. Iwamoto and T. Ide, “Moon-or-Sun, Nagareru, and Nurimeizu are NP-complete,†IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, p. 2021DMP0006, 2022.
[20] Y. Takenaga, S. Aoyagi, S. Iwata, and T. Kasai, “Shikaku and Ripple Effect are NP-complete,†Congressus Numerantium, vol. 216, pp. 119–127, 2013.
[21] 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.
[22] C. Iwamoto and M. Haruishi, “Computational complexity of Usowan puzzles,†IEICE Transactions on Fundamentals of
Electronics, Communications and Computer Sciences, vol. 101, no. 9, pp. 1537–1540, 2018.
[23] 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.
[24] C. Iwamoto, “Yosenabe is NP-complete,†Journal of Information Processing, vol. 22, no. 1, pp. 40–43, 2014.
[25] A. Adler, J. Bosboom, E. D. Demaine, M. L. Demaine, Q. C. Liu, and J. Lynch, “Z3-based Tatamibari solver, and figures from Tatamibari NP-hardness paper,†https://github.com/jbosboom/tatamibari-solver, Feb. 2020, accessed: 2022-07-28.
[26] J. J. W. Bosboom, “Exhaustive search and hardness proofs for games,†Ph.D. dissertation, Massachusetts Institute of Technology, 2020.
[27] T. Weber, “A SAT-based Sudoku solver,†in LPAR, 2005, pp. 11–15.
[28] I. Lynce and J. Ouaknine, “Sudoku as a SAT Problem,†in AI&M, 2006.
[29] U. Pfeiffer, T. Karnagel, and G. Scheffler, “A Sudoku-Solver for Large Puzzles using SAT,†in LPAR short papers (Yogyakarta), 2010, pp. 52–57.
[30] M. Z. Musa, “Interactive Sudoku Solver Using Propositional Logic in Python,†Bachelor Thesis, Undergraduate Program of Informatics, School of Computing, Telkom University, 2018.
[31] A. Shaleh, “Solving Shikaku Using Propositional Logic Approach,†Bachelor Thesis, Undergraduate Program of Informatics, School of Computing, Telkom University, 2019.
[32] M. d. Berg and A. Khosravi, “Optimal binary space partitions in the plane,†in International Computing and Combinatorics Conference. Springer, 2010, pp. 216–225.
[33] A. Sharma, “Combinations from n arrays picking one element from each array,†https://www.geeksforgeeks.org/ combinations-from-n-arrays-picking-one-element-from-each-array/, Apr. 2022, accessed: 2022-04-27.
[34] L. Prechelt, “Are scripting languages any good? A validation of Perl, Python, Rexx, and Tcl against C, C++, and Java.†Adv. Comput., vol. 57, pp. 205–270, 2003.
[35] E. D. Demaine, “Tatamibari Font,†https://github.com/edemaine/font-tatamibari, Apr. 2022, accessed: 2022-05-11.
Downloads
Published
2022-12-31
How to Cite
Reinhard, E. C., Arzaki, M., & Wulandari, G. S. (2022). Solving Tatamibari Puzzle Using Exhaustive Search Approach. Indonesian Journal on Computing (Indo-JC), 7(3), 53–80. https://doi.org/10.34818/INDOJC.2022.7.3.675
Issue
Section
Computer Science
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
