Data Structures and Algorithms for Problem Solving Intelligent Agents Searching for Solution to the 8-Puzzle Problem

The 8-Puzzle problem has a \(3\times 3\) grid with 8 tiles numbered from 1 to 8, in eight of the nine cells. As the tiles perfectly fits the cells, there is only one gap, which we denote as tile 0. We want to slide the tiles and change the status of the environment. The goal is to slide one tile at a time and bring the tiles to the goal state, that has zero at the northwest cell followed by 1, 2, 3, 4, 5, 6, 7, and 8 in the consecutive cells. A state of the problem is represented as a 9-tuple \((s_0, s_1, s_2,\dots , s_{i-1}, s_i = 0, s_{i+1}, s_{i+2},\dots ,s_8),\) which has the gap (zero) at the \(i\textrm{th}\) position in the \(3\times 3\) grid and \(0\le s_i\le 8\) and all the \(s_i\) ’s are distinct. The set of all such 9-tuples is the state space. In this paper we present simple data structures to formulate the problem as proposed in Artificial Intelligence domain. In the space we begin the search from the initial node. We define a heuristic function based on the distance in the Cartesian product \(P_3\Box P_3\) to the goal state. The possible moves are dependent on the position of the gap (zero). We define the transition model that takes from a given state and an action to a target state. We follow a search very similar to the depth first search using a heuristic function. We also define an algorithm for the goal state check. The algorithm uses two data structures, EXPLORED that has all explored states, and a LIFO stack FRONTIER to mark the frontier of search.