International Journal of Computing Science and Applied Mathematics
Vol 8, No 2 (2022)

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

Made Indrayana Putra (School of Computing, Telkom University)
Muhammad Arzaki (Computing Laboratory, School of Computing, Telkom University)
Gia Septiana Wulandari (Computing Laboratory, School of Computing, Telkom University)

Article Info

Publish Date
23 Sep 2022

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.

Copyrights © 2022




Citation Download
RIS
EndNote, Reference Manager, ProCite
BibTex
Latex, Jabref
Original Source
Download Original
Google Scholar
Check in Google Scholar
Journal Info
International Journal of Computing Science and Applied Mathematics
Website

Abbrev

ijcsam

Publisher

Institut Teknologi Sepuluh Nopember Surabaya

Subject

Computer Science & IT Education Mathematics

Description

(IJCSAM) International Journal of Computing Science and Applied Mathematics is an open access journal publishing advanced results in the fields of computations, science and applied mathematics, as mentioned explicitly in the scope of the journal. The journal is geared towards dissemination of ...