8
$\begingroup$

Sudoku is well known puzzle which is known to be NP-complete and it is a special case of more general problem known as Latin squares. A correct solution of the $N \times N$ square consists of filling every row and every column with numbers from $1$ to $N$ under the condition that every number appears exactly once in any row or any column.

I define a new problem. The input is a correct solution of $N \times N$ Sudoku puzzle (more generally Latin square problem). I would like to decide whether there is permutation of rows and permutation of columns such that no row and no column contains consecutive triples.

An examples for a row without consecutive triple is 9 5 6 2 3 8 4 7 1. An example for a row with consecutive triple is 8 9 5 2 3 4 7 6 1. The triple is 2 3 4.

I suspect the problem is NP-hard but I was not able to find a reduction.

How hard is solving this variant of Sudoku puzzle? Is it NP-complete?

EDIT : To clarify, the same permutation must be applied to the columns and the rows.

$\endgroup$
  • 1
    $\begingroup$ Just an information: for latin squares do you have an easy example where such a permutation doesn't exist? $\endgroup$ – Vor Mar 20 '13 at 14:48
  • $\begingroup$ Why is the input a correct grid? Permutations will change this property. $\endgroup$ – saadtaame Mar 20 '13 at 16:20
  • $\begingroup$ @saadtaame Note the input is a correct solution of Latin square problem and not the problem I defined above. $\endgroup$ – Mohammad Al-Turkistany Mar 20 '13 at 16:24
  • $\begingroup$ Yes, why does it have to be a correct solution of Latin square? $\endgroup$ – saadtaame Mar 20 '13 at 16:25
  • $\begingroup$ @saadtaame because all the rows and the columns in the input square are just fixed-point free permutations of the numbers from $1$ to $N$. $\endgroup$ – Mohammad Al-Turkistany Mar 20 '13 at 16:32
4
$\begingroup$

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 $N\times 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+\sigma\delta)=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+\sigma\delta)$. 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 $2N\cdot 2\cdot 2\cdot 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.

$\endgroup$
  • $\begingroup$ Thanks for your answer. Did you apply the same permutation on the rows and columns? $\endgroup$ – Mohammad Al-Turkistany Mar 21 '13 at 1:42
  • $\begingroup$ No, I first apply one good permutation on the columns, and then one good permutation on the rows. No reason for them to be the same. $\endgroup$ – Yuval Filmus Mar 21 '13 at 1:51
  • $\begingroup$ Sorry for not being clear in my question. I want a single permutation which is applied to the rows and the columns simultaneously. $\endgroup$ – Mohammad Al-Turkistany Mar 21 '13 at 1:54
  • 2
    $\begingroup$ Here's what you wrote: "decide whether there is permutation of rows and permutation of columns such that...". $\endgroup$ – Yuval Filmus Mar 21 '13 at 2:02
  • $\begingroup$ Sorry again for not being clear in my question. If you don't mind, I will edit the question to make it clear. $\endgroup$ – Mohammad Al-Turkistany Mar 21 '13 at 2:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.