Solving Yin-Yang Puzzles Using Exhaustive Search and Prune-and-Search Algorithms

Made Indrayana Putra, Muhammad Arzaki, Gia Septiana Wulandari

Abstract


We investigate some algorithmic and mathematical aspects of Yin-Yang/Shiromaru-Kuromaru puzzles. Specifically, we discuss two algorithms for solving arbitrary Yin-Yang puzzles, namely the exhaustive search approach and the prune-and-search technique. We show that both algorithms have an identical asymptotic running time of O(max{mn, 2^(mn−h)}) for finding all solutions of a Yin-Yang instance with h hints of size m x n. Nevertheless, our experiments show that the practical running time of the prune-and-search technique outperforms the conventional exhaustive search approach.

Keywords


Complexity; Exhaustive Search; Prune-and-Search; Yin-Yang Puzzles

Full Text:

PDF

References


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.

G. Moore, Paper, Pencil & You: Calm: Relaxing Brain-Training Puzzles for Stressed-Out People. Greenfinch, 2022.

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.

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

R. A. Hearn and E. D. Demaine, Games, puzzles, and computation. CRC Press, 2009.

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.

D. Andersson, “Hiroimono is NP-complete,” in International Conference on Fun with Algorithms. Springer, 2007, pp. 30–39.

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. Kolker, “Kurodoko is NP-complete,” Information and Media Technologies, vol. 7, no. 3, pp. 1000–1012, 2012.

A. Ishibashi, Y. Sato, and S. Iwata, “NP-completeness of two pencil puzzles: Yajilin and Country Road,” Utilitas Mathematica, vol. 88, pp. 237–246, 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.

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.

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 M. Haruishi, “Computational complexity of Usowan puzzles,” IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol. 101, no. 9, pp. 1537–1540, 2018.

A. Allen and A. Williams, “Sto-Stone is NP-Complete,” in CCCG, 2018, pp. 28–34.

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.

I. Lynce and J. Ouaknine, “Sudoku as a SAT Problem,” in AI&M, 2006.

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

U. Pfeiffer, T. Karnagel, and G. Scheffler, “A Sudoku-Solver for Large Puzzles using SAT,” in LPAR short papers (Yogyakarta), 2010, pp. 52–57.

M. Z. Musa, “Interactive Sudoku Solver Using Propositional Logic in Python,” Bachelor Thesis, Undergraduate Program of Informatics, School of Computing, Telkom University, 2018.

A. Shaleh, “Solving Shikaku Using Propositional Logic Approach,” Bachelor Thesis, Undergraduate Program of Informatics, School of Computing, Telkom University, 2019.

E. D. Demaine and M. Rudoy, “Tree-residue vertex-breaking: a new tool for proving hardness,” in Proceedings of the 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT2018), 2018.

B. Bollob´as, Modern graph theory. Springer Science & Business Media, 1998, vol. 184.

R. Diestel, “Graph theory 3rd ed,” Graduate texts in mathematics, vol. 173, p. 33, 2005.

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

Puzzling Stack Exchange, “How to prove yin-yang alternating 2 by 2 is not allowed,” https://puzzling.stackexchange.com/questions/115722/how-to-prove-yin-yang-alternating-2-by-2-is-not-allowed, Apr. 2022, accessed: 28-4-2022.

T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to algorithms, 3rd ed. MIT press, 2009.

N. Megiddo, “Linear-Time Algorithms for Linear Programming in R3 and Related Problems,” SIAM journal on computing, vol. 12, no. 4, pp. 759–776, 1983.

L. Prechelt, “Are scripting languages any good? A validation of Perl, Python, Rexx, and Tcl against C, C++, and Java.” Adv. Comput., vol. 57, pp. 205–270, 2003.

E. D. Demaine, “Yin-Yang Font,” https://github.com/edemaine/font-yinyang, Apr. 2022, accessed: 2022-05-11.

M. Baxter, “The burnside di-lemma: combinatorics and puzzle symmetry,” Tribute to a Mathemagician, pp. 199–210, 2005.




DOI: http://dx.doi.org/10.12962/j24775401.v8i2.13720

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.