All problems

Domino Trains

Medium · backtracking

You have a set of domino tiles. Each tile is a pair [a, b] of whole numbers from 0 to 6, one at each end. A tile can be turned round, so [2, 5] can lie as 2 | 5 or as 5 | 2.

A train is a single row that uses every tile exactly once, where the two ends that touch always show the same number. For example, [1, 2] and [2, 3] make a train when laid as 1 | 2 then 2 | 3.

Write a train as the list of numbers you meet from left to right, counting a number where two tiles meet only once: the left end of the first tile, then the right end of each tile in turn. A train of n tiles is therefore a list of n + 1 numbers. Two trains are the same if they give the same list, so swapping two identical tiles, or turning a tile like [3, 3] round, does not make a new train. Reading a train from the other end gives a different list (unless it reads the same both ways), so both directions count.

Return every train, each exactly once, in ascending order, comparing the lists number by number from the left. If the tiles cannot make a train, return an empty list.

Examples

Example 1

Input: tiles = [[1, 2], [2, 3]]

Output: [[1, 2, 3], [3, 2, 1]]

Laid as 1 | 2 then 2 | 3 the train reads 1, 2, 3. Turning the whole row round gives 3, 2, 1.

Example 2

Input: tiles = [[1, 2], [3, 4]]

Output: []

No end of the first tile matches an end of the second.

Example 3

Input: tiles = [[0, 1], [1, 2], [2, 0]]

Output: [[0, 1, 2, 0], [0, 2, 1, 0], [1, 0, 2, 1], [1, 2, 0, 1], [2, 0, 1, 2], [2, 1, 0, 2]]

The three tiles form a loop, so the train can start at any of the three numbers and go round either way.

Constraints