Solving Tatamibari Puzzle Using Exhaustive Search Approach

  • Enrico Christopher Reinhard Computing Laboratory, School of Computing, Telkom University
  • Muhammad Arzaki Computing Laboratory, School of Computing, Telkom University
  • Gia Septiana Wulandari Computing Laboratory, School of Computing, Telkom University
Abstract views: 322 , 675 downloads: 321
Keywords: Asymptotic Analysis, Exhaustive Search Algorithms, Tatamibari Puzzle

Abstract

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.
Published
2022-12-31
How to Cite
Reinhard, E. C., Arzaki, M., & Wulandari, G. S. (2022). Solving Tatamibari Puzzle Using Exhaustive Search Approach. Indonesia Journal on Computing (Indo-JC), 7(3), 53-80. https://doi.org/10.34818/INDOJC.2022.7.3.675
Section
Computer Science