Sliding Tile Puzzle

In this classic toy, eight numbered tiles sit in a 3 by 3 frame with one empty square. A move slides one tile that is next to the empty square (above it, below it, left or right of it) into the empty square. The puzzle is solved when the tiles read 1 to 8 in order, row by row, with the empty square at the bottom right:

123
456
78.

board is a list of 3 strings, with '.' for the empty square. Write fewest_slides(board) that returns the fewest moves that solve the puzzle, 0 if it is already solved, or -1 if it can never be solved (half of all arrangements cannot).

Examples

fewest_slides(['123', '456', '78.'])   # returns 0
fewest_slides(['123', '456', '7.8'])   # returns 1
fewest_slides(['.12', '453', '786'])   # returns 4
fewest_slides(['123', '456', '87.'])   # returns -1

In the third example the 1 and the 2 slide left, the 3 slides up and the 6 slides up. The last board has the 7 and the 8 swapped, and no series of slides can ever swap two tiles while leaving the rest in place.

Constraints

• The board holds the digits 1 to 8 once each and one '.'.
• The hardest boards need 31 moves.