Puzzle Solving with A* Search

The 8-puzzle, also known as the sliding puzzle, was invented in the 1870s by Noyes Palmer Chapman and became widely popular after being marketed by Sam Loyd, who falsely claimed its invention. Initially seen as a simple yet challenging game, it later gained significance in the field of computer science and artificial intelligence as a classic problem for exploring search algorithms like A*.

Objective

Let's implement the A* search algorithm to solve a classic puzzle: the 8-puzzle. This exercise will help you understand how A* can be applied to solve problems where the goal is to arrange tiles in a specific order.

Puzzle Overview

The 8-puzzle consists of a 3x3 grid with 8 numbered tiles and one empty space. The goal is to move the tiles around until they are in a specific order. The puzzle starts in a scrambled state, and you need to move tiles to reach the goal state.