Problem Statement
Bridges is a logic puzzle where the challenge is to connect a number of islands on a grid using horizontal and vertical bridges so the following conditions hold:
- The number of bridges connected to an island matches the given number for that island
- At most 2 bridges connect the same two islands
- Bridges may not cross each other, or other islands
- It is possible to go from one island to all other islands
The figure above to the left shows the puzzle layout, and the picture above to the right the unique solution. No two islands will lie next to each other, horizontally or vertically. Only puzzles that have one unique solution are valid Bridges puzzles.
Create a class Bridges containing the method solve which takes a String[] puzzle containing the puzzle, and returns a String[] containing the solution. In puzzle, empty grid squares will be represented by a period, '.', and islands by a digit between '1' and '8', inclusive (the exact number of bridges this island should have). The solution should return the same map, except that some of the empty grid squares should be replaced by single or double bridges. The characters '-' and '=' should be used for single and double horizontal bridges, respectively, and the characters '|' and 'H' for single and double vertical bridges, respectively.
Definition
- Class:
- Bridges
- Method:
- solve
- Parameters:
- String[]
- Returns:
- String[]
- Method signature:
- String[] solve(String[] islands)
- (be sure your method is public)
Constraints
- puzzle will contain between 1 and 10 elements, inclusive.
- Each element in puzzle will contain between 1 and 10 characters, inclusive.
- Each element in puzzle will contain the same number of characters.
- puzzle will only contain the character '.' and digits between '1' and '8', inclusive.
- puzzle will contain at least two islands.
- No two digits in puzzle will be adjacent to each other, horizontally or vertically.
- The puzzle will have exactly one solution.
Examples
{"3.1.3.4", ".2.4.1.", "....1.4", "5..8.3.", ".......", ".2.5..3", "2.2..1."}Returns: {"3-1.3=4", "H2=4|1H", "H..H1|4", "5==8=3H", "|..H..H", "|2=5--3", "2-2--1." }This is the example above.{"2.2.2.2.2", ".........", "2.......2", ".........", "2.2.2.2.2"}Returns: {"2-2-2-2-2", "|.......|", "2.......2", "|.......|", "2-2-2-2-2" }Since it must be possible to reach all islands from any island, only one solution is possible.{"1........1"}Returns: {"1--------1" }
Back to all problems