Part $1$: $(40$ pts$)$

Write a code that will scan the input file from a given path and solve it using one of the five

algorithms $($you need to code all five algorithms$).$

Input: Two command line arguments:

$1.$ File path and

$2.$ Algorithm to be used $($BFS$/$IDS$/$h$1/$h$2/$h$3).$

Output:

$1.$ Total nodes generated $($for A$*$ this includes nodes in closed list and fringe$).$

$2.$ Total time taken.

$3.$ A valid sequence of actions that will take the given state to the goal state.

a$.$ Please note that the meaning of action is important $($action is associated with the

movement of a tile, not with the movement of the blank space$).$ For example, in

Fig $1$ above, the action sequence is DRUL.

$4.$ Also note that not all puzzles are solvable $($See Appendix A$1).$ Your code should check

whether the puzzle is solvable or not before attempting to solve it$.$

A note on efficiency:

$$ Some of the algorithms may take a prohibitive amount of time. In such cases terminate

your code after a maximum of $15$ minutes.

$$ A$*$ algorithm should not run into memory or time issues if implemented properly.

Below are sample outputs for A$*$ for two heuristics h$2($Manhattan distance$)$ and h$1($misplaced

tiles$).$ Your code should work in a similar fashion for other algorithms. Please note:

$$ The exact format of the output is not important; it should capture all the information

though.

$$ Your solution can take different paths and can generate a different number of nodes.

Also, different heuristics could give different optimal paths. However, the optimal path

length should be the same.

In the following, the state in $140173.$txt is:

$531$

$\_87$

$264$