Garuda - Garba Rujukan Digital

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

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$.

Elementary Search-based Algorithms for Solving Tilepaint Puzzles Vincentius Arnold Fridolin; Muhammad Arzaki; Gia Septiana Wulandari
Indonesia Journal on Computing (Indo-JC) Vol. 8 No. 2 (2023): August, 2023
Publisher : School of Computing, Telkom University

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

This paper discusses the elementary computational aspects of Tilepaint puzzles, single-player logic puzzles introduced in 1995 and confirmed NP-complete in 2022. Two elementary search-based algorithms are proposed: the complete search technique with a bitmasking approach and the prune-and-search technique with a backtracking approach and pruning optimization. This paper shows that the asymptotic running time of these algorithms for solving an $m \times n$ Tilepaint instance containing $p$ tiles are respectively $O(2^{p} \cdot p \cdot mn)$ and $O(2^{p} \cdot mn)$, implying that the latter method is asymptotically faster by a factor of $p$. This paper also discusses tractable and intractable variants of Tilepaint puzzles. This paper shows that an $m \times n$ Tilepaint instance containing $mn$ tiles of size $1 \times 1$ is solvable in polynomial time. In contrast, this paper shows that solving general $m \times 1$ and $1 \times n$ Tilepaint puzzles remains intractable by reducing such problems from the subset-sum problem.

Utilizing GP 2 for Restaurant Recommendation Nitamayega; Gia Septiana Wulandari; Kemas Rahmat Saleh Wiharja
Indonesia Journal on Computing (Indo-JC) Vol. 9 No. 1 (2024): April, 2024
Publisher : School of Computing, Telkom University

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

The increasing diversity of food and beverage providers poses a challenge for people to find a restaurant that aligns with their preferences. Restaurant recommendation systems can address this problem by providing accurate and relevant suggestions. Although there are many previous studies have explored various recommendation methodologies, the utilization of knowledge graph implemented with GP 2 is still limited. Knowledge graphs can represent complex information in a structured way, while GP 2 is a graph-specific programming language that has a simple syntax. This research focuses on the implementation of a knowledge graph-based restaurant recommendation system with GP 2. The recommendation scheme built can provide the best accuracy, reaching 84.97%. This shows that the knowledge graph-based restaurant recommendation system with GP 2 can demonstrate the effectiveness of the system in providing accurate and relevant recommendations, showing the potential of knowledge graph and GP 2 for the development of recommendation systems in the future and being an effective solution to overcome recommendation problems.

Solving Tatamibari Puzzle Using Exhaustive Search Approach Reinhard, Enrico Christopher; Arzaki, Muhammad; Wulandari, Gia Septiana
Indonesian 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

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$.

Elementary Search-based Algorithms for Solving Tilepaint Puzzles Fridolin, Vincentius Arnold; Arzaki, Muhammad; Wulandari, Gia Septiana
Indonesian Journal on Computing (Indo-JC) Vol. 8 No. 2 (2023): August, 2023
Publisher : School of Computing, Telkom University

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

This paper discusses the elementary computational aspects of Tilepaint puzzles, single-player logic puzzles introduced in 1995 and confirmed NP-complete in 2022. Two elementary search-based algorithms are proposed: the complete search technique with a bitmasking approach and the prune-and-search technique with a backtracking approach and pruning optimization. This paper shows that the asymptotic running time of these algorithms for solving an $m \times n$ Tilepaint instance containing $p$ tiles are respectively $O(2^{p} \cdot p \cdot mn)$ and $O(2^{p} \cdot mn)$, implying that the latter method is asymptotically faster by a factor of $p$. This paper also discusses tractable and intractable variants of Tilepaint puzzles. This paper shows that an $m \times n$ Tilepaint instance containing $mn$ tiles of size $1 \times 1$ is solvable in polynomial time. In contrast, this paper shows that solving general $m \times 1$ and $1 \times n$ Tilepaint puzzles remains intractable by reducing such problems from the subset-sum problem.

Utilizing GP 2 for Restaurant Recommendation Nitamayega; Gia Septiana Wulandari; Kemas Rahmat Saleh Wiharja
Indonesian Journal on Computing (Indo-JC) Vol. 9 No. 1 (2024): April, 2024
Publisher : School of Computing, Telkom University

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

The increasing diversity of food and beverage providers poses a challenge for people to find a restaurant that aligns with their preferences. Restaurant recommendation systems can address this problem by providing accurate and relevant suggestions. Although there are many previous studies have explored various recommendation methodologies, the utilization of knowledge graph implemented with GP 2 is still limited. Knowledge graphs can represent complex information in a structured way, while GP 2 is a graph-specific programming language that has a simple syntax. This research focuses on the implementation of a knowledge graph-based restaurant recommendation system with GP 2. The recommendation scheme built can provide the best accuracy, reaching 84.97%. This shows that the knowledge graph-based restaurant recommendation system with GP 2 can demonstrate the effectiveness of the system in providing accurate and relevant recommendations, showing the potential of knowledge graph and GP 2 for the development of recommendation systems in the future and being an effective solution to overcome recommendation problems.

Title

Found 6 Documents
Search
Journal : Indonesian Journal on Computing (Indo-JC)

Abstract

Abstract

Abstract

Abstract

Abstract

Abstract

Title Search

Found 6 Documents Search Journal : Indonesian Journal on Computing (Indo-JC)

Abstract

Abstract

Abstract

Abstract

Abstract

Abstract

Title

Found 6 Documents
Search
Journal : Indonesian Journal on Computing (Indo-JC)