Objectives: The main objective of this assignment is to compare the informed sea

Objectives:
The main objective of this assignment is to compare the informed search algorithm and linear space algorithms covered until now. The comparison needs to be done on different points:
Performance.
Time complexity.
Space complexity.
Problem:
In this assignment we are considering the (n2-1) -Puzzle problem.
In this problem the number of states is
Meaning that for the 8-puzzle example we have  states.
And for the 15-puzzle we have  states.
We have seen in class that the search can be accelerated with the use of pattern database.
However, these methods increase the space use by the algorithms that can make this techniques intractable for an embedded system.
In this assignment, you will study the impact of the regular  algorithms, with the use of pattern database (or not) with linear space search algorithms.
You will explain the results obtained and conclude on which algorithms are more appropriate depending on the situation.
Implementation
All the code needs to be written in Python.
First, you need to implement the -puzzle generator that has the following specification:
Generates a (n2-1) Puzzle
The size of the puzzle will be given in argument.
The position of the tiles is random.
You can save a (n2-1) puzzle.
Secondly, you need to implement the solver. It should contain the following algorithms:
DFS Branch and Bound
Depth-First Iterative-Deepening
Recursive Best-First
The solver needs to take in arguments a -puzzle previously generated.
I should be able to run your code just by doing something similar to:
python puzzle –solver –puzzle
I have some recommendations to generate results:
Save the result for each simulation.
For the same size of puzzle generates different puzzles.
You can use them to compute the average, etc.