Ich versuche, dieses Problem zu lösen: "Sie haben eine 8x8-Tabelle auf einem Computerbildschirm mit allen Quadraten, die zu weiß gefärbt sind. In jedem Schritt werden Sie jedes Quadrat und als Ergebnis alle Quadrate in derselben Zeile und Spalte auswählen - einschließlich das ausgewählte Quadrat selbst ändert seine Farben (weiß wird schwarz und schwarz wird weiß). Was ist die Mindestanzahl von Schritten, um ein Standard-Schachbrett zu erhalten? "
Dafür habe ich das Schachbrett in 64 Teile (8x8) aufgenommen und alle Kombinationen dieses 64s-Clusters von 1 bis 64 berechnet. (Ich weiß, die Antwort liegt zwischen 1 und 64).
Meine Methode besteht darin, vom Ende (Schachbrett) bis zu ganzem Weiß zu beginnen. Also fülle ich das Board mit Einsen (schwarz) und Nullen (weiß) und konstruiere das Schachbrett in der Funktion fillchessboard () erfolgreich. Und ich kann Zeile und Spalte perfekt umschalten, das ursprüngliche Quadrat, das ich wähle, ist eingeschaltet.
Wenn Sie prüfen, ob alle Karten weiß sind, wählen Sie checkboard (). Diese Funktion gibt den Indikator als 0 zurück, wenn alle Karten weiß sind, 1 wenn nicht. Ich fange von kleinen Kombinationen zu größeren Kombinationen an und überprüfe das Brett in jedem Schritt. Wenn der Indikator zum ersten Mal als 0 zurückkehrt, ist es die kleinste Iterationszahl, die die Tafel weiß macht und die Antwort der Frage ist.
Bis jetzt funktioniert mein Code und in 10 Stunden kann ich bis zur 10. Iteration gehen. Es wird jedoch immer mehr Zeit brauchen, damit die 11. Iteration ungefähr 10 Stunden dauert und die 12. Iteration 20 Stunden und so weiter. Meine Frage ist, gibt es irgendeine Methode für diese Anweisungen schneller und effektiver? Ich kann nicht eine Woche warten, um das zu lösen. Ich würde jede Hilfe schätzen. Danke!
Zuerst ein paar Namen:
c_{i,j} ist die Zelle am Schnittpunkt der Zeile i und der Spalte j . cross_{i,j} ist die Menge: { c_{r,c} / r=i or c=j } . Es ist das cross aller Zellen aus der Zeile i union column j . Es enthält eine ungerade Anzahl von Zellen. odd(cross_{i,j}) ist eine Funktion, die 0 zurückgibt, wenn es eine gerade Anzahl von schwarzen Zellen in cross_{i,j} gibt, und 1, wenn es eine ungerade Anzahl von schwarzen Zellen gibt. Betrachten wir den Effekt der Auswahl der Zelle c_{i,j} :
cross_{i,j} wechseln und so wird der Wert von odd(cross_{i,j}) geändert. odd(cross_{k,l}) für (k,l) \neq (i,j) nicht. Der Grund für Punkt 2 ist, dass es für den Schnittpunkt von cross_{k,l} mit cross_{i,j} nur 3 Fälle gibt:
k und eine Zelle für die Spalte l . Also ändert sich bei jeder Möglichkeit eine gerade Anzahl von Zellen und der Wert von odd(cross_{k,l}) ändert sich nicht.
Die einzige Möglichkeit, den Wert von odd(cross_{i,j}) zu ändern, besteht darin, c_{i,j} auszuwählen.
Am Ende des Spiels gibt es 32 Kreuze , die den Wert gewechselt haben. Also ist die minimale Anzahl von Schritten für jede Lösung 32.
Nun zeigen die vorherigen Überlegungen, dass die Auswahl der 32 interessierenden Zellen den endgültigen Schachbrett-Zustand ergibt.
Das ist also eine minimale Lösung.
Tut mir leid, aber hier gibt es no Programmierung:)
Dies ist keine Lösung, sondern einige Hinweise, die helfen sollten, die Komplexität (aber nicht die Schwierigkeit) des Problems zu reduzieren.
Das Schachbrett hat 2 ^ 64 verschiedene Zustände.
Es gibt einige Eigenschaften eines Schachbretts, die Ihnen helfen werden, die Anzahl interessanter Zustände zu reduzieren.
Jede Bewegung wirft 15 Steine (eine ungerade Zahl). Da Sie mit einer geraden Anzahl von weißen Steinen beginnen und enden, wissen Sie, dass die Gesamtzahl der Züge gerade ist.
Auch die Reihenfolge, in der Sie die Züge ausführen, ist irrelevant. Wenn Sie dasselbe Quadrat zweimal auswählen, wird die vorherige Drehung umgekehrt. Wir müssen also nur herausfinden, welche der 64 Kacheln ausgewählt werden soll.
So können wir 64 Bits verwenden, um die Lösung darzustellen, und jedes Bit repräsentiert entweder eine ausgewählte Kachel oder eine nicht ausgewählte Kachel. Wir könnten eine 64-Bit-lange verwenden, um eine mögliche Lösung zu speichern.
Wenn Sie eine 64-Bit-Länge verwenden, um den Status der Karte zu speichern, ist jeder Schritt ein XOR mit einer Zahl, die die richtigen 15 Kacheln (eine Zahl mit diesen 15 gesetzten Bits) umkehrt.
Ein Schachbrett ist symmetrisch. Es spielt keine Rolle, ob Sie es drehen oder spiegeln. Der Staat wäre derselbe. Dies reduziert die Komplexität weiter, weil es beweist, dass, wenn X eine Lösung ist, das Komplement von X auch eine Lösung ist. Wenn also keine Lösung mit 32 Stücken gefunden wurde, gibt es keine Lösung.
Meine Intuition (oder eher die Symmetrie) legt nahe, dass die Lösung, falls eine existiert, ein Vielfaches von 8 sein und entweder 8, 16 oder 32 sein sollte, wobei 16 am wahrscheinlichsten ist. Ich habe dafür jedoch keinen Beweis. Ich sollte ziemlich leicht beweisen können, dass es in 8 Zügen keine Lösung gibt (und Sie haben dies mit roher Gewalt bewiesen - vorausgesetzt, Ihr Programm ist korrekt).