# The Fifteen Puzzle- A New Approach through Hybridizing Three Heuristics Methods

arXiv: https://arxiv.org/abs/2302.02985 · HTML: https://mlsanity.com/paper/2302.02985/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 52 references that are in the map.
- First posted on arXiv 6 Jan 2023.

## Builds on (most cited first, 6 of 6)

- [Fitness Dependent Optimizer: Inspired by the Bee Swarming Reproductive Process](https://mlsanity.com/paper/1904.05226/) (2019)
- [A simple proof that the (n2-1)-puzzle is hard](https://mlsanity.com/paper/1707.03146/) (2017)
- [Exploiting Learned Policies in Focal Search](https://mlsanity.com/paper/2104.10535/) (2021)
- [Effective problem solving using SAT solvers](https://mlsanity.com/paper/1906.06251/) (2019)
- [A new evolutionary algorithm: Learner performance based behavior algorithm](https://mlsanity.com/paper/2009.11182/) (2020)
- [ANA: Ant Nesting Algorithm for Optimizing Real-World Problems](https://mlsanity.com/paper/2112.05839/) (2021)

## Built on by (most cited first, 1 of 1)

- [Algorithmic Prompt-Augmentation for Efficient LLM-Based Heuristic Design for A* Search](https://mlsanity.com/paper/2601.19622/) (2026)

## Abstract (arXiv)

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