Dao was a simple two-player board game designed by Jeff Pickering and Ben van Buskirk at 1999. A variation of it, called S-Dao, is a one-player game. In S-Dao, the game board is a 4 * 4 square with 16 cells. There are 4 black stones and 4 white stones placed on the game board randomly in the beginning. The player is given a final position and asked to play the game using the following rules such that the final position is reached using the minimum number of moves:
1. You first move a white stone, and then a black stone. You then alternatively move a white stone and a black stone.
2. A stone can be moved horizontally, vertically or diagonally. A stone must be moved in a direction until the boarder or another stone is encountered. There is no capture or jump.
3. During each move, you need to move a stone of the right color. You cannot pass.
An example of a sequence of legal moves is shown in the following figure. This move sequence takes 4 moves. This is not a sequence of legal moves
using the least number of moves assume the leftmost board is the initial position and the rightmost board is the final position. A sequence of moves using only 3 moves is shown below.
Given an initial position and a final position, your task is to report the minimum number of moves from the initial position to the final position.