The Fifteen Puzzle—A New Approach through Hybridizing Three Heuristics Methods

Dler O. Hasan, Aso M. Aladdin, Hardi Sabah Talabani, Tarik Ahmed Rashid, Seyedali Mirjalili

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)

Abstract

The Fifteen Puzzle problem is one of the most classical problems that has captivated mathematics 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 manage this large state space, the 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 problem. The three mentioned heuristics will be hybridized in a way that can dramatically reduce the number of states generated by the algorithm. Moreover, all these heuristics require only 25 KB of storage, but help the algorithm effectively reduce the number of generated states and expand fewer nodes. Our implementation of the BA* search can significantly reduce the space complexity, and guarantee either optimal or near-optimal solutions.

Original languageEnglish
Article number11
JournalComputers
Volume12
Issue number1
DOIs
Publication statusPublished - Jan 2023

Keywords

  • bidirectional search
  • Fifteen Puzzle
  • heuristic search
  • inadmissible heuristic function
  • metaheuristic
  • unidirectional search

Fingerprint

Dive into the research topics of 'The Fifteen Puzzle—A New Approach through Hybridizing Three Heuristics Methods'. Together they form a unique fingerprint.

Cite this