Dominoes is a game played with rectangular tiles. Each tile (domino) is split in half vertically and contains two numbers between 0 and 6, inclusive. One tile A can be played after tile B if the left number of A is the same as the right number of B. Several consecutively played tiles are called a line. For example, the picture below shows a line containing four tiles.
You will be given a String[] tiles. Each element of tiles will be in the format "X:Y" where X and Y are digits between 0 and 6, inclusive. You should arrange these tiles into as few lines as possible. You can turn over any tile, i.e., the tile "2:5" can also be used as "5:2". Each tile should be used exactly once. Your method should return the constructed lines as a String[]. Each element should represent a single line, formatted as a dash-separated list of tiles in the order and orientation they occur in the line. If there is more than one solution possible, return the solution whose first element comes first lexicographically.
If there are still multiple solutions, return the one among them whose second element comes first lexicographically, and so on.
|