  Fifteen Puzzle problem is one of the most classical problems that have
captivated mathematical enthusiasts for centuries. This is mainly because of
the huge size of the state space with approximately 1013 states that have to be
explored and several algorithms have been applied to solve the Fifteen Puzzle
instances. In this paper, to deal with this large state space, Bidirectional A*
(BA*) search algorithm with three heuristics, such as Manhattan distance (MD),
linear conflict (LC), and walking distance (WD) has been used to solve the
Fifteen Puzzle problems. The three mentioned heuristics will be hybridized in a
way that can dramatically reduce the number of generated states by the
algorithm. Moreover, all those heuristics require only 25KB of storage but help
the algorithm effectively reduce the number of generated states and expand
fewer nodes. Our implementation of BA* search can significantly reduce the
space complexity, and guarantee either optimal or near-optimal solutions.1
