Wie schwer ist eine Variante des Sudoku-Puzzles?

8

Sudoku ist ein bekanntes Puzzle, von dem bekannt ist, dass es NP-vollständig ist, und es ist ein Sonderfall eines allgemeineren Problems, das als lateinische Quadrate bekannt ist. Eine korrekte Lösung des Quadrats besteht darin, jede Zeile und jede Spalte mit Zahlen von 1 bis N zu füllen , unter der Bedingung, dass jede Zahl in einer Zeile oder Spalte genau einmal vorkommt.N×N1N

Ich definiere ein neues Problem. Die Eingabe ist eine korrekte Lösung des Sudoku-Puzzles (allgemeiner das lateinische Quadratproblem). Ich möchte entscheiden, ob es eine Permutation von Zeilen und eine Permutation von Spalten gibt, so dass keine Zeile und keine Spalte aufeinanderfolgende Tripel enthält.N×N

Ein Beispiel für eine Reihe ohne aufeinanderfolgendes Tripel ist 9 5 6 2 3 8 4 7 1. Ein Beispiel für eine Reihe mit aufeinanderfolgendem Tripel ist 8 9 5 2 3 4 7 6 1. Das Tripel ist 2 3 4.

Ich vermute, das Problem ist NP-schwer, aber ich konnte keine Reduzierung finden.

Wie schwer ist es, diese Variante des Sudoku-Puzzles zu lösen? Ist es NP-vollständig?

BEARBEITEN : Zur Verdeutlichung muss dieselbe Permutation auf die Spalten und Zeilen angewendet werden.

Mohammad Al-Turkistany
quelle
1
Nur eine Information: Haben Sie für lateinische Quadrate ein einfaches Beispiel, wo eine solche Permutation nicht existiert?
Vor dem
Warum ist die Eingabe ein korrektes Raster? Permutationen ändern diese Eigenschaft.
Saadtaame
@saadtaame Beachten Sie, dass die Eingabe eine korrekte Lösung des lateinischen Quadratproblems ist und nicht das oben definierte Problem.
Mohammad Al-Turkistany
Ja, warum muss es eine korrekte Lösung des lateinischen Quadrats sein?
Saadtaame
@saadtaame, da alle Zeilen und Spalten im Eingabequadrat nur freie Festpunktpermutationen der Zahlen von bis N sind . 1N
Mohammad Al-Turkistany

Antworten:

4

Wenn die Zeilen- und Spaltenpermutationen unterschiedlich sind und die aufeinanderfolgenden Tripel zunehmen müssen: Die Antwort lautet immer JA.

N×Ni,i+1,i+2t,t+1,t+21/(N(N1)(N2))N2tiNN(N2)2/(N(N1)(N2))<1

N

X,i,t,σσ{±1}(i+σδ)=t+δδ{0,1,2}ππ(t)=j0,π(t+1)=j1,π(t+2)=j2jδ=1(i+σδ)X,i,t,σ,X,i,t,σ {t,t+1,t+2}{t,t+1,t+2}{j0,j1,j2}{j0,j1,j2}2N2251=40N12Np=1/(N(N1)(N2))d40N1ep(d+1)1

40eNN(N1)(N2).
N12N12
Yuval Filmus
quelle
Danke für deine Antwort. Haben Sie dieselbe Permutation auf die Zeilen und Spalten angewendet?
Mohammad Al-Turkistany
Nein, ich wende zuerst eine gute Permutation auf die Spalten und dann eine gute Permutation auf die Zeilen an. Kein Grund für sie, gleich zu sein.
Yuval Filmus
Tut mir leid, dass ich in meiner Frage nicht klar bin. Ich möchte eine einzelne Permutation, die gleichzeitig auf die Zeilen und Spalten angewendet wird.
Mohammad Al-Turkistany
2
Folgendes haben Sie geschrieben: "Entscheiden Sie, ob es eine Permutation von Zeilen und eine Permutation von Spalten gibt, so dass ...".
Yuval Filmus
Entschuldigen Sie noch einmal, dass ich in meiner Frage nicht klar bin. Wenn es Ihnen nichts ausmacht, werde ich die Frage bearbeiten, um sie klar zu machen.
Mohammad Al-Turkistany