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

本文利用 Bidirectional A * 算法及三种启发式算法（曼哈顿距离、线性位差和行走距离）解决了 Fifteen Puzzle 问题，并将这三种启发式算法混合运用，有效减少了算法生成状态数和扩展节点数，大大降低了空间复杂度，保证了最优解或接近最优解。