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

Made Indrayana Putra (Telkom University)
Muhammad Arzaki (Telkom University)
Gia Septiana Wulandari (Telkom University)

International Journal of Computing Science and Applied Mathematics-IJCSAM
Vol. 8 No. 2 (2022)

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.