Problem 5 of the Google Code Jam 2020 qualifiers was to construct a N-by-N matrix with trace K, where each row and each column contains every number between 1 and N exactly once (aka a latin square).
The official write-up is pretty sparse, omitting the key insights of how to generate a valid trace pattern for K and how to extend the trace pattern to get a valid partial latin square, so I had to piece together the missing parts from the corresponding codeforces thread. I'm collecting this here, since I still haven't seen a complete, correct analysis.
The key insight here is that we can always get a valid "starter" for our lating square if T distinct values of the trace each occur at least T times. Then we can fill the squares spanned by each of the values by filling up the diagonals and get a valid placement for all the digits part of the trace.
For example:
Trace: A A A B B
A _ B
B A _
_ B A
B A
A B
Trace: A A A B B B C C C
A B C
C A B
B C A
B A C
C B A
A C B
C B A
A C B
B A C
From here, we can use Hall's algorithm to extend this to a full latin square, but unlike described in the writeup, we need to go number by number, rather than row by row. (see e.g. https://www.cs.du.edu/~petr/milehigh/2017/kuhl.pdf)
Now we just need to represent each K as a combination of T distinct values occuring at least T times.
Once N gets large enough, we can use a kind of counter to generate each K value:
K | Trace
------------------------
N 1 1 1 ... 1 1 1
N+1 ?
N+2 1 1 1 ... 1 2 2
...
2N-2 1 1 2 ... 2 2 2
2N-1 ?
2N 2 2 2 ... 2 2 2
We can of course generalize from trace N to trace xN by
putting x x ... x on the diagonal.
This also means that we need N >= 10 for this construction to always work.
xN: x x x x x ... x x x x x
xN+1: (x-1) (x-1) (x-1) x x ... x (x+1) (x+1) (x+1) (x+1)
xN+N-1: x x x x (x+1) ... (x+1) (x+1) (x+2) (x+2) (x+2)
Of course, (x-1) and (x+2) must not go out of bounds, which would happen for n+1 and n**2-1. Fortunately, these cases are impossible to solve anyways, so we can ignore them and output "IMPOSSIBLE".
For N < 10, I don't have a really smart idea. Probably the A A A A B C pattern from the analysis would work here as well, but the proof is not immediately obvious to me.
PS: After having written the above, I noticed that Google's original solution can also be made to work, since their trace pattern permits expanding into a valid partial latin square by expanding it according to this scheme:
A B
C A B
C A B
C A B
C B A
A C