TY - JOUR
AU - Reinhard, Enrico Christopher
AU - Arzaki, Muhammad
AU - Wulandari, Gia Septiana
PY - 2022/12/31
Y2 - 2024/08/13
TI - Solving Tatamibari Puzzle Using Exhaustive Search Approach
JF - Indonesia Journal on Computing (Indo-JC)
JA - IndoJC
VL - 7
IS - 3
SE - Computer Science
DO - 10.34818/INDOJC.2022.7.3.675
UR - https://socj.telkomuniversity.ac.id/ojs/index.php/indojc/article/view/675
SP - 53-80
AB - 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\).
ER -