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$
9
  • 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, 2013 at 14:48
  • $\begingroup$ Why is the input a correct grid? Permutations will change this property. $\endgroup$
    – mrk
    Mar 20, 2013 at 16:20
  • $\begingroup$ @saadtaame Note the input is a correct solution of Latin square problem and not the problem I defined above. $\endgroup$ Mar 20, 2013 at 16:24
  • $\begingroup$ Yes, why does it have to be a correct solution of Latin square? $\endgroup$
    – mrk
    Mar 20, 2013 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$ Mar 20, 2013 at 16:32

1 Answer 1

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$
9
  • $\begingroup$ Thanks for your answer. Did you apply the same permutation on the rows and columns? $\endgroup$ Mar 21, 2013 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$ Mar 21, 2013 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$ Mar 21, 2013 at 1:54
  • 2
    $\begingroup$ Here's what you wrote: "decide whether there is permutation of rows and permutation of columns such that...". $\endgroup$ Mar 21, 2013 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$ Mar 21, 2013 at 2:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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