Write in c$++$ as max optimized as possible this task for AI subject : The game starts with a square board consisting of tiles numbered from $1$ to N and one empty tile, represented by the number $0.$ The goal is to arrange the tiles in numerical order. Movement is done by sliding a tile into the position of the empty tile, where tiles from above, below, left, or right can be moved.

The input consists of the number N $$ the total number of numbered tiles $(8,15,24,$ etc.$),$ a number I $$ the index of the position of the zero in the solution $($if $-1,$ the default index is set to the bottom$-$right corner$),$ followed by the current configuration of the board. Using the IDA$*$ algorithm and the "Manhattan distance" heuristic, the following should be output:

On the first line, the length of the "optimal" path from the start to the target state.

The corresponding steps $($one per line$),$ which are performed to reach the final state. The steps are: left, right, up$,$ and down.

Note that not every input puzzle configuration is solvable. Whether the puzzle is solvable can be checked as described here. For an unsolvable puzzle, the output should be $-1($i$.$e$.,$ no path$).$

$**$ Please include an option to print the time taken to find the path $($excluding the time taken to print the solution$)$ in seconds, with a precision of at least two decimal places. Printing the time should not be included when running the automatic tests.

$***$ In the attached files, you can find example input$-$output configurations for $8$ Puzzle and $15$ Puzzle, basic test puzzles for the current task, and a desktop tool for Windows to test the task.

Sample input:

$8$

$-1$

$123$

$456$

$078$

Sample output:

$2$

left

left