Zone colouring: hints, no solution
Medium · Backtracking
A venue is divided into zones numbered 0 to zones - 1. Each zone gets one of three colours: red, green or blue, and the three colours are different and matter, so swapping two colours across the venue gives a different colouring. Zones that share a boundary are listed as pairs [a, b] in adjacent, and two adjacent zones must not get the same colour.
Count the number of valid colourings of the whole venue. A pair may be listed more than once. Zones that touch nothing can take any colour. If no valid colouring exists the answer is 0.
Examples
- Input
- zones = 3, adjacent = [[0, 1], [1, 2]]
- Output
- 12
- Note
- Zone 0 has 3 choices, then each next zone has 2, so 3 x 2 x 2.
- Input
- zones = 3, adjacent = [[0, 1], [1, 2], [0, 2]]
- Output
- 6
- Note
- Every zone touches the others, so all three colours are used once, in 3 x 2 x 1 ways.
Constraints
- 1 <= zones <= 14
- 0 <= number of pairs <= 91
- Each pair names two different zones from 0 to zones - 1
- The answer is at most 200000
Hint 1: a nudge
When you colour a zone, which of the zones you have already coloured can conflict with it?
Unlock the full hints and timed practice with a pass
The second and third hints and the timed, runner-checked practice are part of a pass.