Question Write a program ( using any programming language) that implements \( A^{*} \) algorithm for solving \( n \)-puzzle problem ( \( <=20 \) ) that is a generalization for 8 -puzzle problem. However, Note that the \( N \) here refer to the board's size (meaning NxN matrix). As an example, when \( n=3 \), the board size would be a matrix of \( 3 \times 3 \) with numbers \( 1 \sim 8 \) in it. GOAL STATE: assume that the goal state (arrangement) is always the sequence of numbers from 1 to ( \( \left.N^{*} N\right)-1 \), starting from the very first row and column. E.g. GOAL STATE for \( \mathrm{N}=3 \) 123 456 78 propose and implement four different heuristics for this problem. Example of heuristics would be Manhattan distance or the number of displaced tiles on the board. You are asked to implement \( A^{*} \) algorithm (using any programming language) for solving n-puzzle problems ( \( <=20 \) ). - Propose and implement four different heuristics. - Run your code for solving \( n \)-puzzle problems ( \( n=8,10 \), and 20) using each of your heuristics (12 different runs). - Calculate and visualize the run time of each heuristic for each N. Use at least 10 random starts to determine the (average) run time. - You may try starting from the goal state and performing several random legal moves in order to generate a random start board arrangement. - NOTE: It is important to note that this is only a suggestion, so you might wish to start with a random arrangement. - e.g. \( \mathrm{n}=3 \) - GOAL STATE - 123 - 456 - 78_ - Initial state - move 1 (randomly choose to either move 6 down or 8 right) - 123 - 456 - 7_8 - move 2 (randomly choose to move 5 down or 7 right) - 123 - 4_6 - 758 - move 3 (randomly choose to move 2 down, 4 right, or 6 left) - 123 - 46 758 - continue.... Explain your code, your heuristics, and the results of your run in a report. Please include your code with your report. - Include instructions for running your code or a link to them.
【General guidance】The answer provided below has been developed in a clear step by step manner.Step1/1To solve the n-puzzle problem, we can use the A* algorithm, which is a search algorithm that finds the shortest path between the initial and goal state. The algorithm uses a heuristic function to estimate the cost of reaching the goal state from the current state.The first step is to represent the board as a 2D array, where each element represents a tile. The empty tile is represented by zero. We can also represent the state of the board as a tuple, where the first element is the board and the second element is the position of the empty tile.Next, we need to define a heuristic function. A heuristic function is a function that estimates the cost of reaching the goal state from the current state. We can use the following heuristics:Manhattan distance: This heuristic calculates the distance between the current position of each tile and its goal position. The total distance is the sum of the distances of all tiles.Displaced tiles: This heuristic calculates the number of tiles that are not in their goal position.Linear conflict: This heuristic calculates the number of conflicts between tiles in the same row or column that are not in their goal position. A conflict occurs when two tiles that belong to the same row or column need to move in opposite directions to reach their goal position.Pattern database: This heuristic uses precomputed values for subsets of the board. We can compute the cost of reaching the goal state for each subset and store it in a database. During the search, we can use the values from the database to estimate the cost of reaching the goal state from the current state.After defining the heuristic function, we can implement the A* algorithm. The algorithm starts with the initial state and expands the states with the lowest estimated cost. The estimated cost is the sum of the cost of reaching the current state from the initial state and the estimated cost of reaching the goal state from the current state.To generate a random start state, we can start with the goal state and perform several random legal moves. A legal move is a move that does not move the empty tile out of the board or overlap with another tile.To measure the performance of each heuristic, we can run the algorithm for different board sizes and starting states and record the time taken to reach the goal state.ExplanationRepresenting the Board:The n-puzzle problem involves a board with tiles, where the goal is to rearrange the tiles from an initial configuration to a goal configuration. To represent the board in a program, we can use a 2D array, where each element represents a tile, and the value of the element represents the number on the tile. We can also represent the empty tile as 0. For ... See the full answer