Elementary Algorithmic Methods for Solving Suguru Puzzles - Butrahandisya Butrahandisya; Muhammad Atzaki; Gia Septiana Wulandari (LPPM Institut Teknologi Sepuluh Nopember, 2024)
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 × n Suguru puzzles containing R regions and H hint cells in O(R · (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 × 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.