[Solved]: How hard is a variant of Sudoku puzzle?

When the row and column permutations are different and the consecutive triples have to be increasing: The answer is always YES. Suppose the matrix has size $Ntimes N$. Consider a random permutation of the columns. Each row (by itself) is a random permutation. The probability that the numbers $i,i+1,i+2$ appear in positions $t,t+1,t+2$ is $1/(N(N-1)(N-2))$. There are $N-2$ choices for $t$ and $i$, and $N$ different rows. Therefore the expected number of consecutive triples is $N(N-2)^2/(N(N-1)(N-2)) < 1$. We conclude that there is some permutation of the columns, under which there are no consecutive triples in any of the rows. Now repeat the same argument for the columns – note that permuting the rows cannot create a consecutive triple in any of them. When the row and column permutations are the same, and consecutive triples can be either increasing or decreasing: The answer is still YES, for large enough $N$. The idea is to use the lopsided version of the Lovász local lemma, via Lu and Székely’s paper Using Lovász local lemma in the space of random injections. In the earlier proof, we considered events $X_{ell,i,t,sigma}$ for $sigma in {pm 1}$, which for a line $ell$ (either a row or a column), state that $ell(i+sigmadelta)=t+delta$ for $delta in {0,1,2}$. These are examples of the canonical events considered by Lu and Székely: if the random permutation (permuting both rows and columns) is $pi$, then they are of the form $pi(t)=j_0,pi(t+1)=j_1,pi(t+2)=j_2$, where $j_delta = ell^{-1}(i+sigmadelta)$. Two events $X_{ell,i,t,sigma},X_{ell’,i’,t’,sigma’}$ conflict if ${t,t+1,t+2} cap {t’,t’+1,t’+2} neq emptyset$ or ${j_0,j_1,j_2} cap {j’_0,j’_1,j’_2} neq emptyset$ (this is actually only a necessary condition). Each event conflicts with at most $2Ncdot 2cdot 2cdot 5 – 1= 40N-1$ other events ($2N$ lines, two orientations, two ways to conflict, five conflicting positions). While non-conflicting events are in general dependent, using the lopsided version of the Lovász local lemma we can ignore this, and let our dependency graph include edges only for conflicting events. Since the probability that each event happens is $p = 1/(N(N-1)(N-2))$ and the size of each neighborhood is $d leq 40N-1$, the lemma applies whenever $ep(d+1) leq 1$, that is $$ 40eN leq N(N-1)(N-2). $$ This condition is satisfied for $N geq 12$. We conclude that for $N geq 12$, the required permutation always exists. Using the recent constructive version of LLL, we can even find it efficiently.