In this final project, we investigate two algorithmic approaches to solve the Tatamibari puzzle and analyze it, namely, exhaustive search and SAT Solver. We also develop a polynomial time algorithm to verify whether a Tatamibari configuration is a solution. It shows that the asymptotic running time for solving the Tatamibari puzzle using exhaustive search is (O(\max{m^2n^2,h^{mn-h}\cdot hmn})) and we also derive the asymptotic running time for solving Tatamibari puzzle using SAT solver. From the experimental result, we infer that SAT solver is faster than the exhaustive search. Exhaustive search generates all possible configurations before verifying, while SAT solver generates a solution and immediately verifies it. Additionally, we also develop an algorithm to check the number of solutions for empty Tatamibari instances.
Keywords: Asymptotic Analysis, Exhaustive Search, SAT Solver, Tatamibari.