A Game on the Chessboard

On the chessboard of size 4x4 there are 8 white and 8 black stones, i.e. one
stone on each field. Such a configuration of stones is called a game
position. Two stones are adjacent if they are on fields with a common side
(i.e. they are adjacent in either horizontal or vertical direction but not
diagonal). It means that each stone has at most 4 neighbours. The only legal
move in our game is exchanging any two adjacent stones. Your task is to find
the shortest sequence of moves transforming a given starting game position
into a given final game position.

Input:

The starting game position is described in the first 4 lines of input file
GAME.IN. There are 4 symbols in each line, which define the colour of each
stone in the row from the left to the right.  The lines describe the rows of
the chessboard from the top to the bottom. Symbol `0' means a white stone and
symbol `1' a black one. There is no space symbol separating the symbols in the
line. The fifth line is empty. The next 4 following lines describe the final
game position in the same way.

Output:

The first line of output file GAME.OUT contains the number of the moves.

Example:

GAME.IN
		1111
		0000
		1110
		0010

		1010
		0101
		1010
		0101

GAME.OUT (one of the correct solutions)
		4