by python and C++

P.1. (20+20 points) Slider puzzle problems provide an opportunity to experiment with representation and search as a paradigm to solve Al problems. You are required to describe the 8-Puzzle problem and implement it using the programming language of your choice. You must use the following search algorithms: a) Depth first with iterative deepening. Depth bound would be provided by the user or the program would set it up to its default value. b) Best first search. Use at least two different admissible heuristics (other than those discussed in the class) and compare their performance. Notes: 12 45 7 8 1. The goal state for the puzzle is: 2. You need to verify for every instance of the problem if the initial configuration given by the user is solvable. A configuration is solvable if its parity is 'even'. Parity may be defined as the number of inversions where a larger tile appears before a smaller' tile, when the configuration is linearized in, e.g.row-major format. For example, consider the following initial state for which the parity is 'even' (4 inversions). 1 3 425 Row-major layout: 1,3,4,2,5,7,8,6 Inversions: 3-2, 4-2, 7-6, 8-6 (Total 4 inversions) 786 Figure 1: A random initial state