Elementary Algorithmic Methods for Solving Suguru Puzzles

Butrahandisya Butrahandisya, Muhammad Arzaki, Gia Septiana Wulandari

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.

Keywords


asymptotic analysis; backtracking; Suguru puzzle; tractable subproblems

Full Text:

PDF

References


Naoki Inaba, “number block,” http://inabapuzzle.com/honkaku/nblock.html, Jul. 2001, accessed: 2023-06-19.

L. Robert, D. Miyahara, P. Lafourcade, L. Libralesso, and T. Mizuki, “Physical zero-knowledge proof and NP-completeness proof of Suguru puzzle,” Information and Computation, vol. 285, p. 104858, 2022. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0890540121001905

Z. Xu and J. Mayer, “Teaching critical thinking and problem solving skills through online puzzles and games,” in 7th International Conference on Distance Learning and Web Engineering. Citeseer, 2007, pp. 321–325.

G. Kendall, A. Parkes, and K. Spoerer, “A survey of NP-complete puzzles,” ICGA Journal, vol. 31, no. 1, pp. 13–34, 2008.

E. D. Demaine, “Playing games with algorithms: Algorithmic combinatorial game theory,” in International Symposium on Mathematical Foundations of Computer Science. Springer, 2001, pp. 18–33.

E. D. Demaine, Y. Okamoto, R. Uehara, and Y. Uno, “Computational complexity and an integer programming model of Shakashaka,” IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol. 97, no. 6, pp. 1213–1219, 2014.

N. Ueda and T. Nagao, “NP-completeness results for Nonogram via parsimonious reductions,” Department of Computer Science, Tokyo Institute of Technology, Tech. Rep., 1996.

T. Yato and T. Seta, “Complexity and completeness of finding another solution and its application to puzzles,” IEICE transactions on fundamentals of electronics, communications and computer sciences, vol. 86, no. 5, pp. 1052–1060, 2003.

M. Holzer, A. Klein, and M. Kutrib, “On the NP-completeness of the Nurikabe pencil puzzle and variants thereof,” in Proceedings of the 3rd International Conference on FUN with Algorithms. Citeseer, 2004, pp. 77–89.

M. Holzer and O. Ruepp, “The troubles of interior design–a complexity analysis of the game Heyawake,” in International Conference on Fun with Algorithms. Springer, 2007, pp. 198–212.

D. Andersson, “Hashiwokakero is NP-complete,” Information Processing Letters, vol. 109, no. 19, pp. 1145–1146, 2009.

J. K¨olker, “Kurodoko is NP-complete,” Information and Media Technologies, vol. 7, no. 3, pp. 1000–1012, 2012.

Y. Takenaga, S. Aoyagi, S. Iwata, and T. Kasai, “Shikaku and Ripple Effect are NP-complete,” Congressus Numerantium, vol. 216, pp. 119–127, 2013.

C. Iwamoto, “Yosenabe is NP-complete,” Journal of Information Processing, vol. 22, no. 1, pp. 40–43, 2014.

A. Uejima and H. Suzuki, “Fillmat is NP-complete and ASP-complete,” Journal of Information Processing, vol. 23, no. 3, pp. 310–316, 2015.

C. Iwamoto and T. Ibusuki, “Dosun-Fuwari is NP-complete,” Journal of Information Processing, vol. 26, pp. 358–361, 2018.

A. Adler, J. Bosboom, E. D. Demaine, M. L. Demaine, Q. C. Liu, and J. Lynch, “Tatamibari is NP-Complete,” in 10th International Conference on Fun with Algorithms (FUN 2021), ser. Leibniz International Proceedings in Informatics (LIPIcs), M. Farach-Colton, G. Prencipe, and R. Uehara, Eds., vol. 157. Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum f¨ur Informatik, 2020, pp. 1:1–1:24. [Online]. Available: https://drops.dagstuhl.de/opus/volltexte/2020/12762

C. Iwamoto and T. Ibusuki, “Polynomial-time reductions from 3SAT to Kurotto and Juosan puzzles,” IEICE Transactions on Information and Systems, vol. 103, no. 3, pp. 500–505, 2020.

[Online]. Available: https://www.jstage.jst.go.jp/article/transinf/E103.D/3/E103.D 2019FCP0004/pdf

E. D. Demaine, J. Lynch, M. Rudoy, and Y. Uno, “Yin-Yang Puzzles are NP-complete,” in 33rd Canadian Conference on Computational Geometry (CCCG) 2021, 2021.

C. Iwamoto and T. Ide, “Five Cells and Tilepaint are NP-Complete,”IEICE Transcations on Information and Systems, vol. 105, no. 3, pp. 508–516, 2022. [Online]. Available: https://www.jstage.jst.go.jp/article/transinf/E105.D/3/E105.D 2021FCP0001/pdf

M. I. Putra, M. Arzaki, and G. S. Wulandari, “Solving Yin-Yang Puzzles Using Exhaustive Search and Prune-and-Search Algorithms,” (IJCSAM) International Journal of Computing Science and Applied Mathematics,vol. 8, no. 2, pp. 52–65, 2022.

E. C. Reinhard, M. Arzaki, and G. S. Wulandari, “Solving tatamibari puzzle using exhaustive search approach,” Indonesia Journal on Computing (Indo-JC), vol. 7, no. 3, pp. 53–80, 2022.

T. Weber, “A SAT-based Sudoku solver,” in LPAR, 2005, pp. 11–15.

C. Bright, J. Gerhard, I. Kotsireas, and V. Ganesh, “Effective problem solving using SAT solvers,” in Maple Conference. Springer, 2019, pp. 205–219.

A. Sbrana, L. G. B. Mirisola, N. Y. Soma, and P. A. L. de Castro, “Solving NP-Complete Akari games with deep learning,” Entertainment Computing, p. 100580, 2023.

C. Bessiere, C. Carbonnel, E. Hebrard, G. Katsirelos, and T. Walsh, “Detecting and exploiting subproblem tractability,” in IJCAI: International Joint Conference on Artificial Intelligence, 2013, pp. 468–474.

D. Lichtenstein, “Planar formulae and their uses,” SIAM journal on computing, vol. 11, no. 2, pp. 329–343, 1982.

R. Neapolitan and K. Naimipour, Foundations of algorithms. Jones & Bartlett Publishers, 2010.

D. Bolton, “The multinomial theorem,” The Mathematical Gazette, vol. 52, no. 382, pp. 336–342, 1968.

K. H. Rosen, Discrete Mathematics and Its Applications, 8th ed. McGraw-Hill Higher Education, 2019.

S. Brunetti and A. Daurat, “An algorithm reconstructing convex lattice sets,” Theoretical computer science, vol. 304, no. 1-3, pp. 35–57, 2003.

J. I. Gunawan, “Understanding Unsolvable Problem,” Olympiad in Informatics, vol. 10, pp. 87–98, 2016.

J. L. (https://cs.stackexchange.com/users/91753/john l), “Possibly Tractable Variation of Suguru Puzzles,” Computer Science Stack Exchange, uRL:https://cs.stackexchange.com/q/157307 (version: 2023-02-19). [Online]. Available: https://cs.stackexchange.com/q/157307

A. Antonopoulos, E. Bakali, A. Chalki, A. Pagourtzis, P. Pantavos, and S. Zachos, “Completeness, approximability and exponential time results for counting problems with easy decision version,” Theoretical Computer Science, vol. 915, pp. 55–73, 2022.

L. Prechelt, “An empirical comparison of seven programming languages,” Computer, vol. 33, no. 10, pp. 23–29, 2000.

Otto Janko, “Suguru,” https://www.janko.at/Raetsel/Suguru/index.htm, Oct. 2022, accessed: 2022-10-11.




DOI: http://dx.doi.org/10.12962/j24775401.v10i1.17249

Refbacks

  • There are currently no refbacks.



View My Stats


Creative Commons License
International Journal of Computing Science and Applied Mathematics by Pusat Publikasi Ilmiah LPPM, Institut Teknologi Sepuluh Nopember is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Based on a work at https://iptek.its.ac.id/index.php/ijcsam.