For the autumn parade, 2n lantern carriers walk in a single line. There are two lanterns with each
number 1, 2, ..., n, and the organisers want the two lanterns numbered k to have exactly k
other lanterns between them, for every k.
Write lantern_parade(n) that returns the line as a list of 2n numbers, or None if no line with
this property exists. Any valid line is accepted.
Examples
Input: n = 3
Output: [3, 1, 2, 1, 3, 2] (its mirror image is the other valid answer)
Explanation: one lantern between the 1s, two between the 2s, three between the 3s.
Input: n = 4
Output: [4, 1, 3, 1, 2, 4, 3, 2] (the only answer apart from its mirror image)
Input: n = 1
Output: None
Explanation: the line is only two lanterns long, so the 1s cannot have a lantern between them.
Constraints
1 <= n <= 24- each test must finish in well under a second; for some
nthere is no valid line, and trying every arrangement to find that out takes far too long oncenpasses about 12
Goals
- Choose the order of decisions in a backtracking search so the hardest ones come first
- Use a counting argument to prove that some sizes have no answer at all