Class Name: SlidingPuzzle
Method Name: minMoves
Parameters: String, String, String
Returns: int
The method signature is (be sure your method is public):
int minMoves(String top, String middle, String bottom)
You are to implement a class SlidingPuzzle that contains a method minMoves.
The minMoves method takes as parameters 3 strings representing a board. Each
string will have exactly 3 characters. Each character in the string is either
a digit from 1-8 inclusive, or a space. There are no duplicate characters in
any string, or between the strings. Every digit from 1-8, and the space
character is used exactly once somewhere in the 3 strings. TopCoder will insure
the validity of the input strings.
The strings represent a sliding block puzzle with 8 numbered blocks and one
missing block represented by a space. Your method minMoves is to take the
board specified by the 3 inputted strings, and return the minimum number of
moves necessary to transition to the goal state (discussed below). If the goal
state cannot be reached, then your function should return -1.
The first string (top) represents the top row of the 3x3 puzzle. The first
character specifies the number of the block in the top left corner. The second
character in the first string specifies the number on the middle block of the
top row. Finally, the third character of the first string specifies the number
on the top right block of the puzzle. Similarly the second string (middle)
describes the middle row of the 3x3 puzzle, and the third string (bottom)
describes the bottom row of the 3x3 puzzle. The space character will appear as
one of the characters in the 3 strings. The space represents the absence of a
block in that particular position.
For example, given the following 3 strings,
top="172"
middle="584"
bottom=" 63"
the cooresponding board would look like:
[ "172", "584", " 63" ] the cooresponding board would look like:
-----------
| 1 | 7 | 2 |
|---+---+---|
| 5 | 8 | 4 |
|---+---+---|
| | 6 | 3 |
-----------
The minMoves method must determine and return the minimum number of moves
necessary to convert the board to the goal position, or -1 if the goal position
cannot be reached. The goal position looks like:
-----------
| 1 | 2 | 3 |
|---+---+---|
| 4 | 5 | 6 |
|---+---+---|
| 7 | 8 | |
-----------
A valid move is one where you slide a box that is above, below, to the left, or
to the right of the empty space into the position of the empty space. Diagonal
moves are not allowed.
Given the first board above, [ "172", "584", " 63" ], there are 2 valid moves.
----------- -----------
| 1 | 7 | 2 | | 1 | 7 | 2 |
|---+---+---| |---+---+---|
| | 8 | 4 | and | 5 | 8 | 4 |
|---+---+---| |---+---+---|
| 5 | 6 | 3 | | 6 | | 3 |
----------- -----------
Examples:
["357", "2 4", "618"] --> 24
["846", "215", " 37"] --> 26
["145", "273", " 68"] --> 24
["172", "584", " 63"] --> 20
["412", " 53", "786"] --> 5
["412", " 37", "856"] --> -1
["542", "713", " 86"] --> 10