This task was a special one. It is designed just for the purpose of intriguing people to read this solution. If you are familiar with A* and Bidirectional Search, you can skip this part. If you are not, then this task was designed to get you familiar with them.

The solution to this task can be a simple state search. Let one ordering of numbers represent a state. We can search the shortest path from the starting state to the finish state using any search algorithm. BFS and DFS however, were not fast enough or were memory expensive.

One possible solution was Bidirectional BFS. Bidirectional BFS is a special type of search. It can be described as two BFS searches, one from the starting, one from the finishing state. The advantage of bidirectional BFS is smaller time complexity compared to normal BFS. While normal BFS is ~\mathcal O(b^d)~, bidirectional BFS is only ~\mathcal O(b^{d/2})~ where ~b~ is the branching factor and ~d~ is the distance from start to finish. The problem with bidirectional BFS is that the search starting from the finishing state needs to perform backward movements. In some problems, this can be quite hard to calculate. In this problem, however, the backward movements were identical to the forward moves.

The other solution was A*. A* is a heuristic search that takes into account not only the distance of a state from start but the expected distance to the finish. The most important part of A* is how we calculate this expected distance. The function that calculates this expected distance (called the heuristic function) must be optimistic, and monotone. Optimistic means that for any state ~X~, the function ~H(X)~ must be smaller than or equal to the true path from ~X~ to the finish state. Monotone means that for states ~X~ and ~Y~ where ~dist(X, Y)~ is the distance from ~X~ to ~Y~, ~H(X)~ must be smaller than or equal to ~H(Y) + dist(X, Y)~. If the heuristic is not optimistic, A* will return a wrong answer. It will overestimate the shortest path and miss it. If it is not monotone, A* needs to be able to revisit nodes.