Article Per Year (5 Year)
p-Index From 2021 - 2026
0.23
P-Index
This Author published in this journals
All Journal Jurnal Ilmu Komputer dan Informasi
Ammar, Muhammad Tsaqif
Unknown Affiliation
Computer Science & IT Library & Information Science

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

Found 1 Documents
Search

 1 
Note on Algorithmic Investigations of Juosan Puzzles Ammar, Muhammad Tsaqif; Arzaki, Muhammad; Wulandari, Gia Septiana
Jurnal Ilmu Komputer dan Informasi Vol. 17 No. 1 (2024): Jurnal Ilmu Komputer dan Informasi (Journal of Computer Science and Informatio
Publisher : Faculty of Computer Science - Universitas Indonesia

Show Abstract | Download Original | Original Source | Check in Google Scholar | DOI: 10.21609/jiki.v17i1.1184

Abstract

We investigate several algorithmic and mathematical aspects of the Juosan puzzle—a one-player pencil-and- paper puzzle introduced in 2014 and proven NP-complete in 2018. We introduce an optimized backtracking technique for solving this puzzle by considering some invalid subgrid configurations and show that this algorithm can solve an arbitrary Juosan instance of size m × n in O(2mn) time. A C++ implementation of this algorithm successfully found the solution to all Juosan instances with no more than 300 cells in less than 15 seconds. We also discuss the special cases of Juosan puzzles of size m × n where either m or n is less than 3. We show that these types of puzzles are solvable in linear time in terms of the puzzle size and establish the upper bound for the number of solutions to the Juosan puzzle of size 1 × n. Finally, we prove the tractability of arbitrary m × n Juosan puzzles whose all territories do not have constraint numbers.
Co-Authors Gia Septiana Wulandari Muhammad Arzaki