Quelle est la difficulté d'une variante du puzzle Sudoku?

Sudoku est un puzzle bien connu qui est connu pour être NP-complet et c'est un cas spécial de problème plus général connu sous le nom de carrés latins. Une solution correcte du carré consiste à remplir chaque ligne et chaque colonne avec des nombres de à condition que chaque nombre apparaisse exactement une fois dans n'importe quelle ligne ou colonne.$N \times N$$1$$N$

Je définis un nouveau problème. L'entrée est une solution correcte du puzzle Sudoku (plus généralement le problème du carré latin). Je voudrais décider s'il y a permutation de lignes et permutation de colonnes de sorte qu'aucune ligne et aucune colonne ne contiennent de triplets consécutifs.$N \times N$

Un exemple pour une rangée sans triple consécutif est 9 5 6 2 3 8 4 7 1. Un exemple pour une rangée avec triple consécutif est 8 9 5 2 3 4 7 6 1. Le triple est 2 3 4.

Je soupçonne que le problème est NP-difficile mais je n'ai pas pu trouver de réduction.

À quel point est-il difficile de résoudre cette variante du puzzle Sudoku? Est-il NP-complet?

EDIT : Pour clarifier, la même permutation doit être appliquée aux colonnes et aux lignes.

Lorsque les permutations de lignes et de colonnes sont différentes et que les triplets consécutifs doivent augmenter: la réponse est toujours OUI.

Supposons que la matrice ait une taille $N\times N$. Considérons une permutation aléatoire des colonnes. Chaque ligne (en elle-même) est une permutation aléatoire. La probabilité que les chiffres$i,i+1,i+2$ apparaître dans des positions $t,t+1,t+2$ est $1/(N(N-1)(N-2))$. Il y a$N-2$ choix pour $t$ et $i$, et $N$différentes lignes. Par conséquent, le nombre attendu de triplets consécutifs est$N(N-2)^2/(N(N-1)(N-2)) < 1$. Nous concluons qu'il y a une certaine permutation des colonnes, sous laquelle il n'y a pas de triplets consécutifs dans aucune des lignes. Répétez maintenant le même argument pour les colonnes - notez que permuter les lignes ne peut créer un triple consécutif dans aucune d'entre elles.

Lorsque les permutations de ligne et de colonne sont les mêmes, et que les triplets consécutifs peuvent être soit croissants soit décroissants: la réponse est toujours OUI, pour assez grand $N$.

L'idée est d'utiliser la version déséquilibrée du lemme local de Lovász , via l'article de Lu et Székely Utilisation du lemme local de Lovász dans l'espace des injections aléatoires . Dans la preuve précédente, nous avons considéré les événements$X_{\ell,i,t,\sigma}$ pour $\sigma \in \{\pm 1\}$, qui pour une ligne $\ell$ (une ligne ou une colonne), indiquez que $\ell(i+\sigma\delta)=t+\delta$ pour $\delta \in \{0,1,2\}$. Ce sont des exemples des événements canoniques considérés par Lu et Székely: si la permutation aléatoire (permutant à la fois les lignes et les colonnes) est$\pi$, alors ils sont de la forme $\pi(t)=j_0,\pi(t+1)=j_1,\pi(t+2)=j_2$, où $j_\delta = \ell^{-1}(i+\sigma\delta)$. Deux événements$X_{\ell,i,t,\sigma},X_{\ell',i',t',\sigma'}$ conflit si$\{t,t+1,t+2\} \cap \{t',t'+1,t'+2\} \neq \emptyset$ ou $\{j_0,j_1,j_2\} \cap \{j'_0,j'_1,j'_2\} \neq \emptyset$(ce n'est en fait qu'une condition nécessaire). Chaque événement entre en conflit avec au plus$2N\cdot 2\cdot 2\cdot 5 - 1= 40N-1$ d'autres évènements ($2N$lignes, deux orientations, deux modes de conflit, cinq positions conflictuelles). Alors que les événements non conflictuels sont généralement dépendants, en utilisant la version déséquilibrée du lemme local de Lovász, nous pouvons ignorer cela et laisser notre graphique de dépendance inclure des bords uniquement pour les événements conflictuels. Étant donné que la probabilité que chaque événement se produise est$p = 1/(N(N-1)(N-2))$ et la taille de chaque quartier est $d \leq 40N-1$, le lemme s'applique chaque fois $ep(d+1) \leq 1$, C'est

$$40eN \leq N(N-1)(N-2).$$ Cette condition est remplie pour $N \geq 12$. Nous concluons que pour$N \geq 12$, la permutation requise existe toujours. En utilisant la récente version constructive de LLL, nous pouvons même la trouver efficacement.