PROBLEM STATEMENT
A jigsaw puzzle is a mass of flat, irregularly shaped pieces that form a
picture when fitted together. Each piece can be fitted to up to four of its
neighboring pieces. For the purpose of this problem, each piece in the puzzle
is assigned a unique number in the range from 0 to 99, inclusive. Implement a
class Jigsaw that contains a method solveJigsaw. Given a scrambled list of
pieces and the lists of each piece's neighbors, solveJigsaw produces a list of
pieces ordered according to their place in the puzzle.
DEFINITION
Class name: Jigsaw
Method name: solveJigsaw
Parameters: String[]
Return type: int[]
Method signature: int[] solveJigsaw(String[] puzzle) (make sure your method is
public)
Each String in puzzle contains information about one piece of the puzzle.
Strings are formatted as follows (quotation marks are included for clarity):
"number north east south west".
number is an integer value representing the number of this piece. Each of the
other four components - north, east, south and west, - could either be a number
of the corresponding neighbor, or a single upper-case character 'N', indicating
that this piece does not have a corresponding neighbor (i.e. this is a corner
or a border piece). There will be one space between each of the five components
(four spaces total).
The return value contains numbers of the pieces of the puzzle ordered west to
east and north to south, horizontal (west to east) direction first.
TopCoder will ensure the validity of the inputs. Inputs are valid if all of
the following criteria are met:
- puzzle will contain 1 to 50 elements, inclusive.
- Each String of puzzle will have the correct format.
- All numbers will be in the range 0 to 99, inclusive.
- puzzle will be consistent, meaning that if a piece X references a piece Y as
one of its neighbors, then the piece Y will reference X as its neighbor in the
opposite direction.
- puzzle will be rectangular, meaning that it will have exactly four corners.
- puzzle will be solvable, meaning that exactly one correct solution will exist.
EXAMPLES
1. Consider the following input:
{"17 24 29 85 26",
"71 29 60 N 85",
"85 17 71 N 13",
"60 98 N N 71",
"11 N 24 26 N",
"98 16 N 60 29",
"24 N 32 17 11",
"13 26 85 N N",
"32 N 16 29 24",
"29 32 98 71 17",
"16 N N 98 32",
"26 11 17 13 N"}
Here is how the puzzle would be constructed:
11 | 24 | 32 | 16
---+----+----+----
26 | 17 | 29 | 98
---+----+----+----
13 | 85 | 71 | 60
Your method should return {11,24,32,16,26,17,29,98,13,85,71,60}
2. When the input is:
{"17 12 N 24 36",
"16 36 24 N 11",
"36 21 17 16 32",
"32 15 36 11 N",
"21 N 12 36 15",
"15 N 21 32 N",
"24 17 N N 16",
"11 32 16 N N",
"12 N N 17 21"},
your method should return {15,21,12,32,36,17,11,16,24}
3. When the input is: {"23 N N N N"}, your method should return {23}
4. When the input is: {"12 N 13 N N","13 N N N 12"}, your method should return
{12,13}