Wie schwer ist ein binäres Sudoku-Puzzle?

12

Sudoku ist ein bekanntes Puzzle, das NP-vollständig ist. Binary Sudoku ist eine Variante, die nur die Zahlen und 1 zulässt . Die Regeln sind wie folgt.01

  1. Jede Zeile und jede Spalte muss eine gleiche Anzahl von Nullen und Einsen enthalten.
  2. Jede Zeile und jede Spalte ist einzigartig.
  3. Keine Zeile oder Spalte enthält aufeinanderfolgende Dreiergruppen von Nullen oder Einsen ( ist eine aufeinanderfolgende Dreiergruppe von Einsen).111

Die Eingabe ist ein Quadrat, das teilweise mit Nullen und Einsen gefüllt ist. Um das Rätsel zu lösen, muss jede Zelle im N × N- Quadrat mit 0 oder 1 gefüllt sein, wobei die obigen Regeln zu beachten sind. Ich konnte kein Ergebnis für die Unlösbarkeit beim Lösen des binären Sudoku-Puzzles finden.N×NN×N01

Wie schwer ist es, das binäre Sudoku-Puzzle zu lösen? Ist es NP-vollständig?

Außerdem interessiert mich die Komplexität eines damit zusammenhängenden Problems.

Bei einem vollständig ausgefüllten Quadrat, das nur die obigen Regeln 1 und 2 einhält,N×N

Wie schwierig ist es, eine Permutation von Zeilen und Spalten zu finden, sodass das resultierende Quadrat Regel 3 entspricht?

Mohammad Al-Turkistany
quelle
Es ist nicht dasselbe Problem, also werde ich dies eher als Kommentar als als Antwort belassen, aber in meinem Artikel arxiv.org/abs/1202.5074
David
1
Als Autor einer App für binäre Rätsel (dieses Problem) kann ich Ihnen eine Beobachtung anbieten (kein Beweis): Alle in der Praxis beobachteten Instanzen dieses Rätsels können in polynomieller Zeit gelöst werden, aber es gibt Instanzen, die scheinbar nicht lösbar sind Auf diese Weise müssen Sie genau dann, wenn Sie einen Zustand erreichen, in dem keine der drei Regeln eine Zelle direkt dazu zwingt, einen bestimmten Wert anzunehmen (dh Sie müssen anscheinend "etwas ausprobieren" und möglicherweise zu diesem Punkt zurückkehren).
Harold
Hey, ich habe versucht, ein Programm zum Lösen von binären Rätseln zu entwickeln, mit der Ausnahme, dass es mir schwer fällt, die sehr harten binären Rätsel zu lösen, und ich einen Hinweis zur Lösung brauche. Mein Programm kann problemlos alle binären Probleme außer den sehr schwierigen

Antworten:

14

BEARBEITEN : Ich habe den Amateur-Beweis, den ich vor ein paar Monaten angefangen habe und nie beendet habe, schnell abgeschlossen.

Sie können es im PDF-Format auf meinem Blog herunterladen ... noch hat niemand es überprüft, daher sind Widerlegungen, Kommentare und Vorschläge willkommen.


Ich weiß nicht, ob es einen offiziellen Beweis gibt, aber vor ein paar Monaten habe ich die Geräte gebaut, um eine planare 3-CNF-Formel nachzuahmen. Die Minianwendungen OR, SPLIT und TURN lauten beispielsweise:

Bildbeschreibung hier eingeben

Ich habe die Gadgets mit einem einfachen Constraint-Solver-Programm erstellt / überprüft.

Die Eindeutigkeit jeder Zeile / Spalte (Regel 2) kann durch Markieren mit einer eindeutigen "Binärzahl" unter Verwendung eines 2x2-Blocks erreicht werden, der wie eine "Ziffer" wirkt:

01 = 0   10 = 1
10       01

Die gleiche Anzahl von Einsen und Nullen (Regel 3) kann erreicht werden, indem das gesamte Puzzle gespiegelt und die Nullen durch Einsen vertauscht werden.

  3CNF simulation    |  wall  | 3CNF sim. with  | 0000 (using 2x2 blocks)
                     |        | 0,1 inverted    | 0001
 --------------------+        +-----------------+ 0010
    wall                        wall            | ....
 --------------------+        +-----------------+ ....
  3CNF sim. with     |  wall  | 3CNF simulation |
  0,1 inverted       |        |                 |
 --------------------+--------+-----------------+
 0101 .... (using 2x2 blocks)
 0011 ....
 0000 ....

N×N

{0,1,}N×N

Marzio De Biasi
quelle
Ich denke du meinst planare Schaltung SAT?
Mohammad Al-Turkistany
Ich meine Planarer Typ 1 3CNF (der zweigliedrige Graph zwischen den 3CNF-Klauseln und -Variablen ist planar). Ein Gadget wird verwendet, um eine T / F-Zuweisung zu simulieren, ein anderes wird verwendet, um jeder Klausel ein T aufzuzwingen, 2 OR-Gadgets werden verwendet, um die zwei ORs jeder Klausel zu simulieren, und das SPLIT, um das Signal aus den Zuweisungen aufzuteilen und "zu übertragen" zu den Klauseln. Jetzt versuche ich, die Arbeit zu vervollständigen. Sobald ich fertig bin, werde ich den Link in der Antwort veröffentlichen.
Marzio De Biasi
Sie reduzieren also das NP-vollständige planare kubische zweigliedrige monotone 1-in-3-SAT-Problem. richtig?
Mohammad Al-Turkistany
Nein, "Typ 1" bedeutet die spezielle verwendete planare 3CNF-Formel (es gibt einen geringfügigen Unterschied zwischen Typ 1 und Typ 2). Ich habe eine ähnliche Reduktion verwendet, um die NP-Vollständigkeit des Puzzlespiels Tent zu beweisen . Sie können einen Blick auf dieses Papier werfen, aber ich denke, dass ich in 1-2 Tagen einen vollständigen Beweis für das Binär-Sudoku-Problem veröffentlichen werde - auch bekannt als Binär-Puzzle (ich habe gerade die Schnappschüsse der Gadgets fertiggestellt) (und ich hoffe, Sie Werfen Sie einen Blick darauf, um zu sehen, ob es wirklich funktioniert :-)
Marzio De Biasi
Viel Glück, ich kann es kaum erwarten.
Mohammad Al-Turkistany