(a) Please draw the heuristic search tree for solving the famous 8 puzzle problem. The puzzle is contained in a tray that can be thought of as a grid of nine squares. The tray contains only eight tiles, which means that one of the grids is always empty. The tiles are numbered from 1 to 8. The rule of the game is that a tile can be slid into an empty slot. The initial and goal states of an 8-puzzle are shown as the follows. Please draw the heuristic search tree for solving the puzzle.Initial stateGoal state