BBFS-STT: An efficient algorithm for number rotation puzzle

• It introduces a novel intellectual game, NRP, which is rarely addressed so far.
• It presents a novel and efficient solving algorithm, BBFS-STT.
• It develops a game application of NRP including automatically and manually solving.

This paper introduces a quite novel intellectual game, number rotation puzzle (NRP), and deeply compares NRP with 8-puzzle. It comprehensively discusses some issues relevant to solving NRP, such as state representation, state duplicate detection, transition relation between states, solvability judging, and optimal solution. Upon these work, this paper proposes a solving algorithm based on bidirectional breadth-first search (BBFS) and states transition table, which is called BBFS-STT. It takes full advantage of transition relation between states, as well as advantages of BBFS. BBFS-STT achieves high time efficiency and well stability. In addition, this paper designs a game application of NRP, whose prominent feature is that users can seamlessly switch between automatically solving and manually solving modes. Finally, this article carries out experimental analysis on the proposed algorithm, as well as comparison with some search algorithms, i.e., depth-limited DFS, traditional BFS, and A∗. Experimental results show that the proposed BBFS-STT outperforms these three search algorithms. The average time required for solving an instance of NRP is only 0.80592 ms when the test environment is configured as: Apple A6, 1.00 GHz; 1 GB memory. BBFS-STT meets the requirements of real-time solving and demonstration for NRP.