2024 : 5 : 25
Amanj Khorramian

Amanj Khorramian

Academic rank: Assistant Professor
ORCID:
Education: PhD.
ScopusId: 63241651
Faculty: Faculty of Engineering
Address:
Phone:

Research

Title
Efficient Brute-force state space search for Yin-Yang puzzle
Type
JournalPaper
Keywords
Yin-Yang puzzle, State space search, Efficient brute force, Puzzle
Year
2024
Journal Journal of Supercomputing
DOI
Researchers Arash Ahmadi ، Amanj Khorramian

Abstract

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.