Article Per Year (5 Year)
p-Index From 2020 - 2025
0.23
P-Index
This Author published in this journals
All Journal International Journal of Computing Science and Applied Mathematics
Butrahandisya, Butrahandisya
School of Computing, Telkom University
Computer Science & IT Education Mathematics

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

Found 1 Documents
Search

 1 
Elementary Algorithmic Methods for Solving Suguru Puzzles Butrahandisya, Butrahandisya; Arzaki, Muhammad; Wulandari, Gia Septiana
(IJCSAM) International Journal of Computing Science and Applied Mathematics Vol 10, No 1 (2024)
Publisher : Institut Teknologi Sepuluh Nopember

Show Abstract | Download Original | Original Source | Check in Google Scholar | DOI: 10.12962/j24775401.v10i1.17249

Abstract

We discuss elementary algorithmic aspects of the Suguru puzzle---a single-player paper-and-pencil puzzle introduced in 2001 and confirmed NP-complete in 2022. We propose a backtracking algorithm with pruning optimizations for solving an $m \times n$ Suguru puzzles containing $R$ regions and $H$ hint cells in $O(R \cdot (mn-H+2)!)$ time. Despite this factorial asymptotic upper bound, a C++ implementation of our proposed algorithm successfully solved all Suguru instances with no more than $100$ cells using a personal computer in less than $0.5$ second. We also prove that any Suguru instance of size $m \times n$ with either $m = 1$ or $n = 1$ can be solved in linear time in terms of the puzzle size. Finally, we provide an upper bound for the number of solutions to such tractable instances.
Co-Authors Arzaki, Muhammad Wulandari, Gia Septiana