Please USE PYTHON!

You will implement a 3x3 board game. The aim is reaching to the goal state where Tile #1, #2 and #3 are located on the board. 3x3 BOARD Tile 2 Tiki 3 Tie3 Rules of Game: 1. The initial and goal states will be given by user 2. The tiles can be moved up, down, right, or left. 3. 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: 1st step: move Tile #1 2nd step: move Tile #2 3th step: move Tile #3 4th step: move Tile #1 5th step: move Tile #2 6th step: move Tile #3 4. Distance(cost) between two neighboring states will be measure based on the move costs as given below Tile #1: right or left move cost =2 up of down move cost =1 Tile #2: right or left move cost =1 up of down move cost =2 Tile #3: right or left move cost =3 up of down move cost =4 5. User will choose one of the searching strategies: uniform cost and A* search (use Manhattan distance as heuristics). 6. The expansion will go on till 20th expanded node. The program will print out each expanded state and compare it with given goal state. 7. You are free to use any programming language for implementation. You must prepare a report that includes a definition of the game (due date 13.01.2022). You must give an example execution for each algorithm, provide the generated tree (all states and costs must be given) that is generated, show the contents of fringe in each step. And you must be ready to present your work on 13.01.2022. Below is an example tree that shows possible states (costs are not calculated) INITIAL STATE FO GOAL STATE Move I move 2 move 3 3 12 US 25