Article Per Year (5 Year)
p-Index From 2019 - 2024
0.23
P-Index
This Author published in this journals
All Journal Indonesian Journal on Computing (Indo-JC)
Enrico Christopher Reinhard
Computing Laboratory, School of Computing, Telkom University
Computer Science & IT

Published : 1 Documents Claim Missing Document
Claim Missing Document
Check
Articles

Found 1 Documents
Search

 1 
Solving Tatamibari Puzzle Using Exhaustive Search Approach Enrico Christopher Reinhard; Muhammad Arzaki; Gia Septiana Wulandari
Indonesia Journal on Computing (Indo-JC) Vol. 7 No. 3 (2022): December, 2022
Publisher : School of Computing, Telkom University

Show Abstract | Download Original | Original Source | Check in Google Scholar | DOI: 10.34818/INDOJC.2022.7.3.675

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\).
Co-Authors Gia Septiana Wulandari Muhammad Arzaki