Problem2:

Code:

Solution:

We use the EightPuzzle framework in order to solve this problem. Using the A* search, we start from a randomly selected initial state (not too random for the sake of testing and time saving) and try to reach the final state (1, 2, 3, ... , 14, 15, 0).

We implement the actions as the possible directions the blank space ( 0) can make inside the square. We remove the impossible moves from the set of actions by checking the position of the blank space. If the space is located on the top edge ( index is smaller than 4), we cannot move UP. If the space is on the bottom edge of the square ( index is bigger than 11), we cannot move DOWN. If the blank space is located on the left edge ( index is a multiple of 4) we cannot move LEFT or if it is places on the right edge( index divided by 4 gives the remainder 3) we cannot move RIGHT.