Write this in C++. Thanks!

Consider the 8-puzzle: 8 tiles each numbered 1-8 on a 3x3 grid, with one space empty. Any adjacent tile can be moved into the empty square (in effect swapping the locations of that tile and the empty square). This can be done by moving an adjacent tile vertically or horizontally (not diagonally). Thus the number of possible moves is at least 2 (if the empty square is in a corner) and at most 4 (if its in the center). The goal is to begin with some arbitrary arrangement and end with the tiles in the followingarrangement:

1 2 3

4 5 6

7 8 E (where E denotes the empty square.)

One complication is that permutations of the game board fall into 2 disjoint sets of odd or even parity, only one of which can reach the goal. Thus, half of all possible tile arrangements cannot lead to a solution. (These states arent reachable by a physical puzzle.) Your program must correctly detect whether a solution is possible or not. You can either do this by finding the parity (plenty of sources online about how to do that), or by brute-force of directly showing that no solution exists (simpler, but slower).

Your input file is a simple text file. The first element, on a line by itself, is the number of puzzles contained in the file. After that will be the specified number of puzzles in the above format (3 lines of 3 characters each, each character will be a digit 1-8 or an upper case E). Each puzzle is separated from the next by a blank line. Your program will be tested on a different data file with the same format.

Given a puzzle, your program must find a solution if it exists. You should use A* search to find the solution. Recall that A* finds the shortest path by repeatedly selecting the best candidate, determined by which has the lowest value for f(n)=g(n)+h(n).

where g(n) is the actual distance from the start state to that node, and h(n) is the heuristic (estimated) cost from that node to the goal. For your heuristic function h(x), use the sum of the Manhattan (city-block) distances for each tile from where it needs to be.

For each puzzle, your program should print a list of the moves that should be made to reach the solution. If there is no solution for a puzzle, your program should print a short message to that effect.

Again, please write in C++. and try to create the program that reads a file of puzzles and code that handles it. Thanks a ton.

a sample .txt file to import could be....

7 5 4

3 6 2

E 8 1

NOTE: the space in between each number line is NOT meant to be a blank line. the second row is immediately after the first line of numbers. The puzzle ends after the third row and we continue to the next puzzle thanks to a blank line.