The main weaknesses of using Manhattan distance for solving sliding tile puzzles

Abstract

Heuristics are a big improvement over blind searching in pathfinding. The node's test, run, and finish time are reasonable. Artificial intelligence (AI) uses Manhattan distance (MD), a good and simple heuristic, in various subjects to reduce the number of exploring nodes while requiring fewer calculations. The MD heuristics examined approximately 25 times fewer states than the blind search. Unfortunately, can’t reach the goal of pathfinding when the domain size increases, as it becomes similar to brute force or blind search algorithm results. Previous studies have concentrated on MD's weakness, specifically its low bound value for calculation results, and attempted to improve this value in various ways. Unfortunately, to our knowledge, none of the presented research has been able to find the optimal path for all slide tile puzzle sizes. This work discusses the detailed reasons for the low bound value and other related factors that contribute to its weakness. This paper discovered that the distribution of MD values within the domain, not lowbound values, is the critical issue that complicates the search. The MD's summation method for all tiles has an impact on the calculated duplication values. The total number of nodes in the optimal path also affects the search performance.