<![CDATA[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\).]]>
Copyrights © 2022
