In this problem, we note that there are only $4$ relevant integers for a state. These are the position of the marble ($2$ integers, for the row and column indices) and the position of the current empty position (another $2$ integers). Then, for each state, if the marble and empty position are adjacent, we can swap them.

We can also choose to swap the empty position with that of an adjacent position.

We also note that for each state, we only care about the fastest time required to reach that state. Therefore, we do Breadth-First-Search on the states. Our end state is any state where the marble is in the destination position.

Time Complexity: $\mathcal{O}(N^4)$