Given $i$ keyed-$PRP$ labels $\ell_{i,x}$ from a $2^{256} \times 2^{256}$ Sudoku (Latin-square), how difficult is it for an adversary to solve?

There's a keyed-permutation I'm playing with, $\ell_{i,x} = \pi_i(x_i)$, which is a bijection $X \leftrightarrow X$, where $|X| = 2^{256}$, and whose evaluations on plaintext inputs $x_i$ perfectly fill out a Latin-square, $L$, when an appropriate incrementing function, $\pi_{i+1} = \pi_i\mathrm{.step()}$, is applied on the inner-state.

Each $x_i$ is the $i$-th block of some plaintext. Each row in $L$ is the enumerated list of all evaluations $\pi_i(x_i)$ for each $x_i \in X$ for the static step $i$ of the row. Each column in $L$ is the enumerated list of all evaluations $\pi_i(x_i)$ for the static $x$ of the column for each step $i < 2^{256}$. When $L$ is completed, every label only appears once in each row and column, and in total, each label appears $2^{256}$ times. However, in execution, ignoring the obvious computational limitations, $L$ is never completed, as only one $\ell_{i, x}$ is ever evaluated at each step $i$.

\begin{array}{|c|c|c|c|c|c|c|} \hline \\ \space\space\space\space\space\space i \space\space \backslash \space x & 0 & 1 & \space\space\space \cdots \space\space\space\space & 2^{256}-2 & 2^{256}-1 \\ \hline 0 & & \ell_{0, 1} \\ \hline 1 & & & & & \ell_{1, 2^{256}-1} \\ \hline \\ \vdots & & & \ddots \\ \\ \hline 2^{256}-3 & & \ell_{2^{256}-3, 1} \\ \hline 2^{256}-2 & \ell_{2^{256}-2, 0} \\ \hline 2^{256}-1 & & & & \ell_{2^{256}-1, 2^{256}-2} \\ \hline \end{array}

^{Fig. 1 | Example distribution of how labels $\ell_{i, x}$, as evaluations of $\pi$ on non-unique inputs $x$ at step $i$, may map to a partial Latin-square.}

There's tons of confusing, seemingly contradictory statements about the hardness of solving Latin-squares. From it being reducible to 3SAT, to it being $\mathcal{O}(1)$, to isotopies being distinguishable in $\mathcal{O}(n^{\log_2(n)})$, I can't wrap my head around how solvable a concrete instance like this is. So, assuming only a simplified case where $\pi$ is some ideal random permutation, I'd like to know the following:

1. How many labels $\ell_{i, x}$, with unknown $x_i$, does an adversary need for $L$ to be at all uniquely solvable?
2. How does hardness scale as more $\ell_{i, x}$ are revealed?
3. What's $\mathbf{NP}$ got to do with the hardness of this Latin-square?
4. And, is a similar Latin-cube problem easier or harder?

A best attempt at answering my own question, provided for archival purposes.

Preliminary research insights:

• Regarding ERT12, without fully understanding how to translate the findings:

  A. If the problem is massaged into one without sub-grid constraints, it can be represented by $(|X| \times 2 \cdot |X| + |X|^2)$ constraints in +$1$-in-$k$-SAT form, which is $(3 k^2)$ constraints, where $k = |X|$.

  B. Adding $i$-many $\ell_{i,x}$ clues / labels reduces the constraints to $c = (3 k^2 - 3 i)$.

  C. Any +$1$-in-$k$-SAT form problem can be written as a "$k$-SAT problem and $\frac{1}{2}k(k-1)$ of $2$-SAT problems." So, that would be $c$-many $k$-SAT problems and $\frac{1}{2}ck(k - 1)$-many of the $2$-SAT problems.

  D. Assuming $r$-many runs of an $\mathcal{O}{(y)}$ algorithm can be denoted as $r \cdot \mathcal{O}{\left( y \right)}$, then $r \cdot \mathcal{O}{\left( g(n) \right)}$ $\in $ $\mathcal{O}(r \cdot g(n))$;

  E. And, Assuming $n = c$ ^{(unjustified??...)}

  F. If $\mathcal{O}{\left( k\mathrm{-SAT} \right)}$ $\in $ $\mathcal{O}(f(n))$, then $c \cdot \mathcal{O}{\left( k\mathrm{-SAT} \right)}$ $\in $ $\mathcal{O}(c \cdot f(c))$

  G. If $\mathcal{O}{\left( 2\mathrm{-SAT} \right)}$ $\in $ $\mathcal{O}(n^2)$, then $\frac{1}{2} ck(k-1) \cdot \mathcal{O}{\left( 2\mathrm{-SAT} \right)} \in \mathcal{O}{\left(k^2 c \cdot c^2 \right)}$

  H. So, if $s(L_i)$ is an algorithm $s$ which solves $L$ given $i$ labels, then

$$\mathcal{O}{\left( s(L_i) \right)} \in \mathcal{O}{\left( (k^2 - i) f(k^2 - i) + k^2(k^2 - i)^3 \right)}$$

• And, IP01 offers:

  A. If $f(n)$ is an exponential function of the form $2^{\delta n}$, where $\delta > 0$, then as $k \to \infty$, $\delta$ is proven to be "strictly increasing infinitely often" ($-§$Intro):

  B. Then, the polynomial terms are negligible, giving

$$\mathcal{O}{\left(s(L_i)\right)} \in \mathcal{O}{\left((k^2 - i) \space 2^{\delta \left( k^2 - i \right)} \right)}$$

Best-case scenario for solver: \begin{bmatrix} ? & \ell_{0,1} & \ell_{0,2} & \ell_{0,3} \\ \ell_{1,0} & ? & \ell_{1,2} & \ell_{1,3} \\ \ell_{2,0} & \ell_{2,1} & ? & \ell_{2,3} \\ \ell_{3,0} & \ell_{3,1} & \ell_{3,2} & ? \\ \end{bmatrix}

Worst-case scenario for solver: \begin{bmatrix} \ell_{0,0} & \ell_{0,1} & \ell_{0,2} & \ell_{0,3} \\ \ell_{1,0} & ? & ? & \ell_{1,3} \\ \ell_{2,0} & ? & ? & \ell_{2,3} \\ \ell_{3,0} & \ell_{3,1} & \ell_{3,2} & \ell_{3,3} \\ \end{bmatrix}

In the best-case, there's no ambiguity to the puzzle. Each row and column is missing at most one label. Surprisingly, the complexity for solving is still $\mathcal{O}(m \cdot k)$. This is seen from the solving algorithm: "for each row, $m$, missing a label, create a copy of set $X \to C$, then remove each existing label in the row from the set $C$, the remaining label fills in the blank space."

In the worst-case for a solver, the clues leave a sub-square in the center of the larger Latin-square, whose rows & columns are missing the same labels. It can be seen that the sub-square is itself a Latin-square whose sides are of length $\sqrt{\left(k^2 - i\right)}$ with no provided clues. So, in the worst-case, the solution to the puzzle is perfectly concealed.