Write a program with your choice of language to solve the 15-puzzle. Your program should employ:

Depth first search

Breadth first search

Depth first search with iterative deepening

[Note] In your program you should randomly generate a solvable puzzle before solving it with the 3 searching methods. You output your result in a text file (result.txt), in which you print the following results separated by a blank line:

first print the puzzle itself as a series of numbers separated by a space (representing the blank with the number 16)

then print the solutions in the order of dfs, bfs, and dfs-id. Please use letters 'N', 'S', 'E', 'W' for each move with a space in between