write a c$++$ code for the following: The $15$ puzzle also known as the $16$ puzzle, Gem puzzle, Boss puzzle and Mystic

square is a sliding puzzle made up of a wooden square frame and tiles. There are fifteen tiles

that make up the four by four tiled square with one empty space. To solve the puzzle the tiles

must be arranged in numerical order as seen in Figure $1.$

Of all the solvable configurations, the worst case will result in at most $80$ moves being made to

solve the puzzle, if the most efficient algorithm is used.

$1$

You are required to code a C$++$ program that can solve any solvable configuration of the $15$

puzzle. There are many algorithms that could be used to solve this puzzle. It is up to you to

understand and implement one such algorithm.

The only constraint is the number of moves your algorithm is allowed to make. A maximum of

$1000$ moves per puzzle is allowed. After this limit has been reached, no more moves can be

made for that specific puzzle and the puzzle remains unsolved. The $1$ shows where the open block is for the given configuration. In this case you would have

three $15$ puzzles to solve as seen in figure $2.$

Each input file follows this format and the number of puzzles will not be specified.

$3$

One output file should be created that contains results for all given puzzles. This output file must

be called output.txt$.$ This file should contain information for each puzzle including the puzzle

number, whether your algorithm solved it$,$ the number of moves made as well as each consecutive

move. If the puzzle is not solved and $1000$ moves are made, do not write all consecutive moves to

the output file. The output should follow the following format:

puzzle number, solved$/$not solved, moves taken:

$...$

all moves made

$...$

Moves will be written in the format of $\{$row column direction$\}$ where direction is a single character

and can be $$U$($up$),$D$($down$),$L$($left$)$ and $$R$($right$).$ The top left block is at position $00$ and

the bottom right block is at position $33.$ he requirements of the project are as follow:

$$ No global variables may be used $-$ this will result in an automatic failure of the project

$$ Use of at least one class and by extension at least one user defined function.

$$ Reading in and writing to files. Puzzle solvability check,

$2.$ Efficient algorithm $($i$.$e$.$ minimum number of moves made to solve a puzzle$).$

Each feature will increase the coding mark and will give you more to write about in the final report.

If you are implementing a solvability check, this should be added to your output file. You will

include an extra field stating if the puzzle is solvable or is not solvable. There is no provision for user input to your program, it must act on and produce files without any human interaction