Algorithmic Efficiency in Rubik’s Cube Solving: A Study of Timeout Rates, Solution Quality, and Heuristic Limitations

Solving the Rubik’s Cube represents a classical benchmark for evaluating search algorithms in artificial intelligence due to its well-defined state space and computational complexity. The application of search techniques to this problem offers insights into algorithmic efficiency and practical performance in constrained environments. Despite extensive research on heuristic search methods, comparative studies involving uninformed and informed search strategies applied to different cube sizes remain limited. This study addresses that gap by evaluating Depth-First Search (DFS), Breadth-First Search (BFS), and A* Search in solving the NxN Rubik’s Cube. The experiment involves a facelet-based representation of the cube and simulates randomized scrambles of increasing complexity. Each algorithm is implemented in C++ and evaluated on performance metrics including solution length, execution time, and completeness under varied depth limits and cube sizes. Results show that A* Search consistently outperforms both DFS and BFS in terms of execution speed and reliability, achieving optimal or near-optimal solutions without timeouts. BFS demonstrates optimality but suffers from scalability, while DFS offers flexibility with higher time costs. This study provides a practical and measurable comparison of search strategies, highlighting A* as the most balanced approach for real-time puzzle solving within smart systems.