Al Project$12024-2025$:

You will implement a $3\backslash$times $3$ board game. The aim is reaching to the goal state

where Tile #$1,$ #$2$ and #$3$ are located on the board.

Requirements

The initial and goal states will be given by user

The tiles can be moved up$,$ down, right, or left.

The game will begin by the move of Tile #$1($if required$)$ and go on with the

moves of other tiles in order.

For example:

$1^($st $)$ step: move Tile #$1$

$2^($nd $)$ step: move Tile #$2$

$3^($th $)$ step: move Tile #$3$

$4^($th $)$ step: move Tile #$1$

$5^($th $)$ step: move Tile #$2$

$6^($th $)$ step: move Tile #$3$

Distance$($cost$)$ between two neighboring states will be measured based on the move costs as given

below

right or left move $->$ cost $=2$

up of down move $->$ cost $=1$

The A$^(*)$ search will be implemented with Manhattan distance as heuristics.

The expansion will go on till $10^($th $)$ expanded node. The program will print out each expanded state and

compare it with given goal state. Can you do it in java