A Tale of Two Searches: Bidirectional Search Algorithm that Meets in the Middle

Abstract

The Sliding Tiles problem (also known as n-puzzle) is quite popular as a problem testbed in AI. This problem is basically a game on a square grid, containing several tiles numbered consecutively from 1 to n and one blank space, such that n+1 is a square number. The blank space allows the movement of an adjacent tile to the blank position, thereby swapping the positions of the blank space and the tile. The objective of the n-puzzle is to arrive at a desired tile configuration (the end or goal state) starting from a given configuration (the start state), in a minimum number of moves.