We propose an algorithm comprising some new techniques to efficiently search the entire state space of the Yin-Yang puzzle which is an NP-complete problem, by skipping invalid solutions ranges. The algorithm features efficient memory usage and parallel execution. More than 99% of the state space for most of the puzzle’s board sizes is skipped. It speeds up the process of finding valid solutions significantly. We were able to find all valid solutions in the space of more than 18 million billion states using a regular desktop PC. Another research about the Yin-Yang puzzle has examined the largest full-empty Yin-Yang board of size \(5\times 6\). Our proposed algorithm significantly improves performance. Using four parallel threads, it is 357 times faster than the regular and modified BFS and DFS algorithms used in that research, and it performs 192 times faster using a single thread. Our algorithm also consumes over 26,000 times less memory than the other algorithms.
