This final project investigates some algorithmic and mathematical aspects of Yin-Yang/Shiromaru-Kuromaru puzzles.
Specifically, we discuss three algorithms for solving arbitrary Yin-Yang puzzles, namely the exhaustive search approach, the prune-and-search technique, and SAT solver.
We also discuss rule translation into propositional logic formula and the number of variables and clauses needed for the SAT Solver algorithm.
This final project shows that exhaustive search and prune-and-search algorithm 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 \times n). This final project also derives the asymptotic running time for solving Yin-Yang puzzle using SAT-Solver algorithm.
We show that the practical running time of the prune-and-search technique outperforms the conventional exhaustive search approach. We also show that SAT solver based algorithm can be faster than the prune-and-search technique. Exhaustive search and prune-and-search method has to find all potential solution before it can verify it, while SAT solver can verify the potential solution while generating it.