### Problem Statement

In "The Game of Eight", you are given a 3x3 board containing 8 squares labelled 1 through 8, and one empty space. The initial state of the board is given in the String[] board, where '.' represents the empty space. In each turn, you pick any square which is horizontally or vertically adjacent to an empty space and move it to the empty space (see example 0 for clarification). Your goal is to arrange the squares so the board looks like this:

```{"123",
"456",
"78."}
```

Return the minimum number of moves necessary to achieve this goal, or -1 if it's impossible.

### Definition

 Class: GameOfEight Method: fewestMoves Parameters: String[] Returns: int Method signature: int fewestMoves(String[] board) (be sure your method is public)

### Constraints

-board will contain exactly 3 elements.
-Each element of board will contain exactly 3 characters.
-Each character of each element of board will be a digit ('1' - '8') or a dot ('.').
-Each number between 1 and 8 will appear exactly once on the board.

### Examples

0)

 ```{"123", "485", "76."}```
`Returns: 4`
 The optimal solution is the following: ```123 123 123 123 123 485 --> 485 --> 4.5 --> 45. --> 456 76. 7.6 786 786 78. ```
1)

 ```{"123", "456", "78."}```
`Returns: 0`
2)

 ```{".23", "456", "781"}```
`Returns: -1`

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=7995

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13677&pm=7995

mateuszek

#### Testers:

PabloGilberto , Olexiy , Mike Mirzayanov , ivan_metelsky

#### Problem categories:

Graph Theory, Simple Search, Iteration