Lösen japanischer Farbkreuzworträtsel mit Lichtgeschwindigkeit

Japanische Kreuzworträtsel (auch Nonogramme) sind logische Rätsel, bei denen ein Pixelbild verschlüsselt wird. Sie müssen das Kreuzworträtsel mit Zahlen lösen, die sich links von den Zeilen und über den Spalten befinden.

Die Größe der Kreuzworträtsel kann bis zu 150x150 erreichen. Der Spieler verwendet eine spezielle Logik, um die Farbe jeder Zelle zu berechnen. Bei Kreuzworträtseln für Anfänger kann die Lösung einige Minuten und bei komplexen Rätseln einige zehn Stunden dauern.

Ein guter Algorithmus kann das Problem viel schneller lösen. Der Text beschreibt, wie eine Lösung geschrieben wird, die mit den am besten geeigneten Algorithmen (die im Allgemeinen zu einer Lösung führen) fast sofort funktioniert, sowie deren Optimierungen und die Verwendung von C ++ - Funktionen (die die Laufzeit um das Zehnfache reduzieren).

In der mobilen Version von Habr werden Formeln im Text möglicherweise nicht angezeigt (nicht in allen mobilen Browsern). Verwenden Sie die Vollversion oder einen anderen mobilen Browser, wenn Sie Probleme mit Formeln bemerken

Spielregel

Anfangs ist die Kreuzworträtsel-Leinwand weiß. Bei Vanille-Schwarz-Weiß-Kreuzworträtseln müssen Sie die Position der schwarzen Zellen wiederherstellen.

Bei Schwarz-Weiß-Kreuzworträtseln gibt die Anzahl der Zahlen für jede Zeile (links auf der Leinwand) oder für jede Spalte (oben auf der Leinwand) an, wie viele Gruppen schwarzer Zellen sich in der entsprechenden Zeile oder Spalte befinden, und die Zahlen selbst geben an, wie viele zusammengeführte Zellen jede dieser Gruppen enthält. Zahlenreihe $$$[3, 2, 5]$bedeutet, dass es in einer bestimmten Zeile drei aufeinanderfolgende Gruppen von gibt $$$3$, $$$2$und $$$5$schwarze Zellen in einer Reihe. Gruppen können zufällig in einer Reihe angeordnet werden, ohne die relative Reihenfolge zu verletzen (die Zahlen geben ihre Länge an und die Position muss erraten werden), sie müssen jedoch durch mindestens eine weiße Zelle getrennt sein.

Richtiges Beispiel

Bei Farbkreuzworträtseln hat jede Gruppe immer noch ihre eigene Farbe - jede außer Weiß ist eine Hintergrundfarbe. Benachbarte Gruppen unterschiedlicher Farben können nebeneinander stehen, aber für benachbarte Gruppen derselben Farbe ist immer noch eine Trennung durch mindestens eine weiße Zelle erforderlich.

Was ist kein japanisches Kreuzworträtsel?

Jedes Pixelbild kann als Kreuzworträtsel verschlüsselt werden. Es ist jedoch möglicherweise nicht möglich, es wiederherzustellen - das resultierende Puzzle kann entweder mehr als eine Lösung oder eine Lösung haben, kann jedoch nicht logisch gelöst werden. Dann müssen die verbleibenden Zellen im Spiel mithilfe der schamanischen Technologie unter Verwendung von Quantencomputern erraten werden.

Solche Kreuzworträtsel sind keine Kreuzworträtsel, sondern Graphomanie. Es wird angenommen, dass das richtige Kreuzworträtsel so ist, dass Sie auf logische Weise zu einer einzigartigen Lösung gelangen können.

Der "logische Pfad" ist die Fähigkeit, jede Zelle einzeln wiederherzustellen, wobei die Zeile / Spalte separat oder ihr Schnittpunkt betrachtet wird. Wenn dies nicht möglich ist, kann die Anzahl der in Betracht gezogenen Antwortoptionen sehr viel größer sein, als eine Person für sich selbst berechnen kann.

Das falsche Nonogramm ist die einzige Lösung, aber es ist unmöglich, es normal zu lösen. Orange markierte "unlösbare" Zellen. Entnommen aus Wikipedia.

Diese Einschränkung wird wie folgt erklärt - im allgemeinsten Fall ist das japanische Kreuzworträtsel ein NP-vollständiges Problem. Das Erraten wird jedoch nicht zu einer NP-vollständigen Aufgabe, wenn es einen Algorithmus gibt, der zu jedem Zeitpunkt eindeutig angibt, welche Zellen weiter geöffnet werden sollen. Alle Kreuzworträtsel, die von Menschen verwendet werden (mit Ausnahme der Methode Monte Carlo Versuch und Irrtum) basieren darauf.

Bei den meisten orthodoxen Kreuzworträtseln werden Breite und Höhe durch 5 geteilt, es gibt keine Zeilen, die sofort gezählt werden können (solche, bei denen entweder farbige Zellen alle Stellen verstopfen oder sie vollständig fehlen), und die Anzahl der Komplementärfarben ist begrenzt. Diese Anforderungen sind nicht erforderlich.

Das einfachste falsche Kreuzworträtsel:

|1 1| --+---+ 1| | 1| | --+---+ 

Codierte Pixelkunst, die ein Schachbrettmuster verwendet, um einen Farbverlauf zu simulieren, wird häufig nicht rückwärts aufgelöst. Es ist besser zu verstehen, ob Sie bei der Suche "Pixelart-Farbverlauf" eingeben. Der Farbverlauf ist genau wie bei diesem 2x2-Fayl-Kreuzworträtsel.

Mögliche Lösungen

Wir haben die Größe des Kreuzworträtsels, eine Beschreibung der Farben und aller Zeilen und Spalten. Wie kann ich daraus ein Bild zusammenstellen:

Vollständige Suche

Für jede Zelle sortieren wir alle möglichen Zustände und prüfen, ob sie zufriedenstellend sind. Die Komplexität einer solchen Lösung für ein Schwarz-Weiß-Kreuzworträtsel $$$O (N * M * {2} ^ {N * M})$für Farbe $$$O (N * M * {Farben} ^ {N * M})$. In Analogie zur Clownsortierung kann diese Lösung auch als Clown bezeichnet werden. Es ist für Größe 5x5 geeignet.

Backtracking

Alle möglichen Methoden zum Anordnen horizontaler Gruppen von Zellen werden aussortiert. Wir setzen eine Gruppe von Zellen in eine Reihe und stellen sicher, dass die Beschreibung der Spaltengruppen nicht beschädigt wird. Wenn es kaputt geht, setzen wir weiter auf 1 Zelle, wir überprüfen erneut. Set - gehe zur nächsten Gruppe. Wenn Sie keine Gruppe in irgendeiner Weise einfügen können, setzen wir zwei Gruppen zurück, ordnen die vorherige Gruppe neu an usw., bis wir die letzte Gruppe erfolgreich eingefügt haben.

Separat für jede Reihe

Diese Entscheidung ist viel besser und es ist wirklich wahr. Wir können jede Zeile und jede Spalte einzeln analysieren. Jede Zeile versucht, die maximalen Informationen anzuzeigen.

Der Algorithmus für jede Zelle in der Zeile lernt mehr Informationen - es kann sich herausstellen, dass es unmöglich ist, die Zelle in einer bestimmten Farbe zu färben, die Gruppen konvergieren nicht. Sie können die Zeile nicht sofort vollständig erweitern, aber die empfangenen Informationen "helfen" besser, sich für mehrere Spalten zu öffnen, und wenn wir mit der Analyse beginnen, "helfen" sie erneut den Zeilen usw. für mehrere Iterationen, bis alle Zellen eine mögliche Farbe haben.

Wirklich wahre Entscheidung

Eine Linie, zwei Farben

Das effektive Erraten der Schwarz-Weiß-Einzellinie, für die einige Zellen bereits geraten haben, ist eine sehr schwierige Aufgabe. Sie traf sich an Orten wie:

• Viertelfinale der ACM ICPC 2006 - Sie können versuchen, das Problem selbst zu lösen . Das Zeitlimit beträgt 1 Sekunde, das Limit für die Anzahl der Gruppen beträgt 400 und die Länge der Serie beträgt ebenfalls 400. Die Komplexität ist im Vergleich zu anderen Aufgaben sehr hoch.
• Internationale Olympiade in der Informatik 2016 - Bedingung , um die Aufgabe zu bestehen . Das Zeitlimit beträgt 2 Sekunden, das Limit für die Anzahl der Gruppen beträgt 100, die Länge der Zeile beträgt 200'000. Solche Einschränkungen sind übertrieben, aber das Lösen eines Problems mit ACM-Einschränkungen bringt bei diesem Problem 80/100 Punkte. Auch hier hat das Level nicht enttäuscht, Schulkinder aus aller Welt mit einem grausamen IQ-Level trainieren seit mehreren Jahren, um verschiedene Tricks zu lösen, dann gehen sie zu dieser Olympiade (nur 4 Leute aus dem Land müssen bestehen), sie entscheiden 2 Runden à 5 Stunden und im Falle eines epischen Sieges (Bronze in verschiedenen Jahren für 138-240 von 600 Punkten) bietet die Zulassung nach Oxford von klaren Unternehmen der Suchabteilung ein langes und glückliches Leben mit Dakimakura.

Monochrome einzeilige können auch auf verschiedene Arten und für gelöst werden $$$O (N * 2 ^ N)$(Auflisten aller Optionen, Überprüfen der Richtigkeit, Auswählen von Zellen, die in allen Optionen dieselbe Farbe haben) und irgendwie weniger dumm.

Die Hauptidee besteht darin, ein Analogon des Backtracking zu verwenden, jedoch ohne unnötige Berechnungen. Wenn wir irgendwie mehrere Gruppen einrichten und uns jetzt in einer Art Zelle befinden, müssen wir herausfinden, ob es möglich ist, die verbleibenden Gruppen ausgehend von der aktuellen Zelle zu platzieren.

 def EpicWin(group, cell): if cell >= last_cell: #   return group == group_size win = False #        if group < group_size #    and CanInsertBlack(cell, len[group]) #    and CanInsertWhite(cell + len[group], 1) #    and EpicWin(group + 1, cell + len[group] + 1): #    win = True can_place_black[cell .. (cell + len[group] - 1)] = True can_place_white[cell + len[group]] = True; #         if CanInsertWhite(cell, 1) and EpicWin(group, cell + 1): win = True can_place_white[cell] = True return win EpicWin(0, 0) 

Dieser Ansatz wird als dynamische Programmierung bezeichnet . Der Pseudocode wird vereinfacht und auch die berechneten Werte werden dort nicht gespeichert.

Mit den CanInsertBlack/CanInsertWhite , ob es theoretisch möglich ist, eine Gruppe mit der richtigen Größe am richtigen Ort zu platzieren. Sie müssen lediglich sicherstellen, dass sich im angegebenen Zellbereich keine „100% weiße“ Zelle (für die erste Funktion) oder „100% schwarz“ (für die zweite Funktion) befindet. So können sie für arbeiten $$$O (1)$Dies kann mit Teilbeträgen erfolgen:

 white_counter = [ 0, 0, ..., 0 ] #   n def PrecalcWhite(): for i in range(0, (n-1)): if is_anyway_white[i]: # 1,  i-  100%  white_counter[i]++ if i > 0: white_counter[i] += white_counter[i - 1] def CanInsertBlack(cell, len): #     [cell, cell + len - 1] ans = white_counter[cell + len - 1] if cell > 0: ans -= white_counter[cell - 1] #  ans -     cell  (cell + len - 1) return ans == 0 

Dieselbe Zauberei mit Teilsummen wartet auf eine Zeile der Form

 can_place_black[cell .. (cell + len[group] - 1)] = True 

Hier können wir anstelle von = True die Zahl um 1 erhöhen. Und wenn wir viele Ergänzungen an einem Segment in einem bestimmten Array vornehmen müssen $$$array$und außerdem verwenden wir dieses Array nicht vor verschiedenen Ergänzungen (sie sagen darüber, dass diese Aufgabe "offline gelöst" ist), sondern anstelle einer Schleife:

 #     for i in range(L, R + 1): array[i]++ 

Sie können dies tun:

 #     array[L]++ array[R + 1]-- #    for i in range(1, n): array[i] += array[i - 1] 

Somit funktioniert der gesamte Algorithmus in $$$O (k * n)$wo $$$k$- die Anzahl der Gruppen schwarzer Zellen, $$$n$Ist die Länge der Zeichenfolge. Und wir gehen ins Halbfinale der ACM ICPC oder holen uns die Bronze des Interneur. ACM-Lösung (Java) . IOI-Lösung (C ++) .

Eine Linie, viele Farben

Wenn wir zu mehrfarbigen Nonogrammen wechseln, deren Lösung noch unklar ist, erfahren wir eine schreckliche Wahrheit - es stellt sich heraus, dass jede Spalte von allen Spalten magisch beeinflusst wird! Dies wird anhand eines Beispiels klarer:

Quelle - Methoden zum Lösen japanischer Kreuzworträtsel

Während zweifarbige Nonogramme normalerweise darauf verzichteten, mussten sie nicht auf orthogonale Freunde zurückblicken.
Das Bild zeigt, dass im linken Beispiel die drei Zellen ganz rechts leer sind, da die Konfiguration unterbrochen wird, wenn Sie diese Zellen einfärben diese Farben, in denen Sie sich malen können nicht weiße Farbe.

Aber dieser Witz ist mathematisch entscheidbar - jeder Zelle muss eine Nummer gegeben werden, wo $$$i$Das i-te Bit bedeutet, ob diese Zelle angegeben werden kann $$$i$th Farbe. Anfangs haben alle Zellen einen Wert $$$2 ^ {Farben} - 1$. Die Entscheidung der Dynamik wird sich nicht sehr ändern.

Sie können den folgenden Effekt beobachten: Im selben linken Beispiel kann die Zelle ganz rechts je nach Version der Zeilen entweder eine blaue oder eine weiße Farbe haben.
Je nach Version der Spalten hat diese Zelle entweder eine grüne oder eine weiße Farbe.
Gemäß der Common-Sense-Version hat diese Zelle nur eine weiße Farbe. Und dann berechnen wir weiter die Antwort.

Wenn wir das Nullbit "Weiß", das erste "Blau", das zweite "Grün" betrachten, dann berechnet die Linie den Zustand für die letzte Zelle $$$011$und die Spalte $$$101$. Dies bedeutet, dass der Zustand dieser Zelle real ist $$$011 \ & 101 = 001$

 source = [...] #   result = [0, 0, ..., 0] #   len = [...] #    clrs = [...] #    def CanInsertColor(color, cell, len): for i in range(cell, cell + len): if (source[i] & (1 << color)) == 0: #     color    return False; return True def PlaceColor(color, cell, len): for i in range(cell, cell + len): result[i] |= (1 << color) #   color  OR def EpicWinExtended(group, cell): if cell >= last_cell: #   return group == group_size win = False #        if group < group_size #    and CanInsertColor(clrs[group], cell, len[group]) #    and SequenceCheck() #       ,  #         and EpicWin(group + 1, cell + len[group]): #    win = True PlaceColor(clrs[group], cell, len[group]) PlaceColor(0, cell + len[group], 1) #   -    #         #   -  0 if CanInsertWhite(0, cell, 1) and EpicWinExtended(group, cell + 1): win = True PlaceColor(0, cell, 1) return win 

Viele Linien, viele Farben

Führen Sie die im letzten Absatz beschriebenen Status aller Zeilen und Spalten ständig durch, bis keine einzige Zelle mit mehr als einem Bit vorhanden ist. In jeder Iteration aktualisieren wir nach dem Aktualisieren aller Zeilen und Spalten den Status aller Zellen in ihnen durch gegenseitiges UND.

Erste Ergebnisse

Angenommen, wir haben den Code nicht wie Spechte geschrieben, das heißt, wir kopieren keine Objekte versehentlich, anstatt als Referenz zu übergeben, wir erfinden nirgendwo Fahrräder, wir erfinden keine Fahrräder, für Bitoperationen verwenden wir __builtin_popcount und __builtin_ctz ( gcc-Funktionen ), alles ist ordentlich und sauber.

Schauen wir uns die Zeit des Programms an, das das Rätsel aus der Datei liest und es vollständig löst. Es lohnt sich, die Vorteile der Maschine zu bewerten, auf der all diese Dinge geschrieben und getestet wurden:

 RAM - 4GB  - AMD E1-2500,  1400MHz  L1 - 128KiB, 1GHz  L2 - 1MiB, 1GHz  - 2,  - 2   « SoC   »   2013    28  

Es ist klar, dass ein solcher Supercomputer gewählt wurde, weil Optimierungen einen größeren Effekt haben als auf eine fliegende Shaitan-Maschine.

Nachdem wir unseren Algorithmus mit dem kompliziertesten Kreuzworträtsel (laut nonograms.ru) ausgeführt haben, erhalten wir ein nicht sehr gutes Ergebnis - von 47 bis 60 Sekunden (dies beinhaltet das Lesen aus einer Datei und eine Lösung). Es sollte beachtet werden, dass die "Komplexität" auf der Website gut berechnet wurde - das gleiche Kreuzworträtsel in allen Versionen des Programms war auch das schwierigste, andere komplexeste Kreuzworträtsel wurden nach Meinung des Archivs in Top-Zeit gehalten.

Farbkreuzworträtsel Nummer 9596, die größte Schwierigkeit

Für schnelle Tests wurde die Funktionalität für den Benchmark erstellt. Um Daten für ihn zu erhalten, sparsil ich 4683 Farbkreuzworträtsel (ab 10906 ) und 1406 Schwarzweißkreuzworträtsel (ab 8293 ) mit nonograms.ru (dies ist eines der größten Nichtogrammarchive im Internet) unter Verwendung eines speziellen Skripts und speichere sie in einem Format, das das Programm versteht. Wir können davon ausgehen, dass es sich bei diesen Kreuzworträtseln um eine Zufallsstichprobe handelt, sodass der Benchmark angemessene Durchschnittswerte aufweist. Außerdem wurden die Zahlen von ein paar Dutzend der "komplexesten" Kreuzworträtsel (auch die größten in Größe und Anzahl der Farben) in einem Skript zum Laden mit Stiften aufgezeichnet.

Optimierung

Hier sehen Sie die möglichen Optimierungstechniken, die (1) während des Schreibens des gesamten Algorithmus vorgenommen wurden, (2) um die Arbeitszeit von einer halben Minute auf einen Bruchteil einer Sekunde zu verkürzen, (3) die Optimierungen, die weiter nützlich sein können.

Zum Zeitpunkt des Schreibens des Algorithmus

• Spezielle Funktionen für Bitoperationen, in unserem Fall __builtin_popcount zum Zählen von Einheiten in einer binären Notation einer Zahl und __builtin_ctz für die Anzahl der Nullen vor der ersten kleinsten Einheit. Solche Funktionen werden in einigen Compilern möglicherweise nicht angezeigt. Für Windows sind solche Analoga geeignet:

 #ifdef _MSC_VER # include <intrin.h> # define __builtin_popcount __popcnt #endif 

• Array-Organisation - eine kleinere Größe steht an erster Stelle. Zum Beispiel ist es besser, das Array [2] [3] [500] [1024] als [1024] [500] [3] [2] zu verwenden.
• Das Wichtigste ist die allgemeine Angemessenheit des Codes und die Vermeidung unnötiger Berechnungssorgen.

Was reduziert die Arbeitszeit

• Das -O2-Flag beim Kompilieren.
• Um eine vollständig aufgelöste Zeile / Spalte nicht erneut in den Algorithmus zu werfen, können Sie Flags für jede Zeile in einem separaten std :: vector / Array setzen, sie mit einer vollständigen Lösung markieren und nicht loslassen, wenn nichts mehr zu lösen ist.
• Die Besonderheiten einer Lösung eines dynamischen Problems mit mehreren Wiederholungen legen nahe, dass ein spezielles Array, das Flags enthält, die bereits "berechnete" Teile des Problems markieren, jedes Mal zurückgesetzt werden sollte, wenn eine neue Lösung gefunden wird. In unserem Fall ist dies ein zweidimensionales Array / Vektor, wobei die erste Dimension die Anzahl der Gruppen ist, die zweite die aktuelle Zelle (siehe den EpicWin-Pseudocode oben, wo dieses Array nicht ist, aber die Idee ist klar). Anstatt Null zu setzen, können Sie dies tun - lassen Sie uns eine "Timer" -Variable haben, und das Array besteht aus Zahlen, die die letzte "Zeit" anzeigen, als dieses Stück zum letzten Mal nachgezählt wurde. Wenn Sie eine neue Aufgabe starten, erhöht sich der "Timer" um 1. Anstatt das Boolesche Flag zu aktivieren, sollten Sie die Gleichheit des Array-Elements und des "Timers" überprüfen. Dies ist insbesondere in Fällen effektiv, in denen der Algorithmus weit von allen möglichen Zuständen entfernt ist (was bedeutet, dass das Nullsetzen des Arrays „haben wir dies bereits berücksichtigt“ einen gesunden Teil der Zeit in Anspruch nimmt).
• Ersetzen einfacher Operationen des gleichen Typs (Schleifen mit Zuweisung usw.) durch Analoga in STL oder angemesseneren Dingen. Manchmal funktioniert es schneller als ein Fahrrad.
• std::vector<bool> in C ++ komprimiert alle booleschen Werte auf einzelne Bits in Zahlen, was beim Zugriff etwas langsamer funktioniert, als wenn es ein regulärer Wert an der Adresse wäre. Wenn ein Programm solche Werte sehr, sehr oft verwendet, kann das Ersetzen von bool durch einen ganzzahligen Typ einen guten Effekt auf die Leistung haben.
• Andere Schwachstellen können über Profiler gesucht und bearbeitet werden. Ich selbst verwende Valgrind. Die Leistungsanalyse ist praktisch, um kCachegrind durchzusehen. Profiler sind in viele IDEs integriert.

Diese Änderungen haben sich als ausreichend erwiesen, um solche Daten in den Benchmark aufzunehmen:

 izaron@izaron:~/nonograms/build$ ./nonograms_solver -x ../../nonogram/source2/ -e [2018-08-04 22:57:40.432] [Nonograms] [info] Starting a benchmark... [2018-08-04 22:58:03.820] [Nonograms] [info] Average time: 0.00497556, Median time: 0.00302781, Max time: 0.215925 [2018-08-04 22:58:03.820] [Nonograms] [info] Top 10 heaviest nonograms: [2018-08-04 22:58:03.820] [Nonograms] [info] 0.215925 seconds, file 9596 [2018-08-04 22:58:03.820] [Nonograms] [info] 0.164579 seconds, file 4462 [2018-08-04 22:58:03.820] [Nonograms] [info] 0.105828 seconds, file 15831 [2018-08-04 22:58:03.820] [Nonograms] [info] 0.08827 seconds, file 18353 [2018-08-04 22:58:03.820] [Nonograms] [info] 0.0874717 seconds, file 10590 [2018-08-04 22:58:03.820] [Nonograms] [info] 0.0831248 seconds, file 4649 [2018-08-04 22:58:03.820] [Nonograms] [info] 0.0782811 seconds, file 11922 [2018-08-04 22:58:03.820] [Nonograms] [info] 0.0734325 seconds, file 4655 [2018-08-04 22:58:03.820] [Nonograms] [info] 0.071352 seconds, file 10828 [2018-08-04 22:58:03.820] [Nonograms] [info] 0.0708263 seconds, file 11824 

 izaron@izaron:~/nonograms/build$ ./nonograms_solver -x ../../nonogram/source/ -e -b [2018-08-04 22:59:56.308] [Nonograms] [info] Starting a benchmark... [2018-08-04 23:00:09.781] [Nonograms] [info] Average time: 0.0095679, Median time: 0.00239274, Max time: 0.607341 [2018-08-04 23:00:09.781] [Nonograms] [info] Top 10 heaviest nonograms: [2018-08-04 23:00:09.781] [Nonograms] [info] 0.607341 seconds, file 5126 [2018-08-04 23:00:09.781] [Nonograms] [info] 0.458932 seconds, file 19510 [2018-08-04 23:00:09.781] [Nonograms] [info] 0.452245 seconds, file 5114 [2018-08-04 23:00:09.781] [Nonograms] [info] 0.19975 seconds, file 18627 [2018-08-04 23:00:09.781] [Nonograms] [info] 0.163028 seconds, file 5876 [2018-08-04 23:00:09.781] [Nonograms] [info] 0.161675 seconds, file 17403 [2018-08-04 23:00:09.781] [Nonograms] [info] 0.153693 seconds, file 12771 [2018-08-04 23:00:09.781] [Nonograms] [info] 0.146731 seconds, file 5178 [2018-08-04 23:00:09.781] [Nonograms] [info] 0.142732 seconds, file 18244 [2018-08-04 23:00:09.781] [Nonograms] [info] 0.136131 seconds, file 19385 

Möglicherweise stellen Sie fest, dass Schwarz-Weiß-Kreuzworträtsel im Durchschnitt „härter“ sind als farbige. Dies bestätigt die Beobachtungen von Spieleliebhabern, die auch glauben, dass „Farbe“ im Durchschnitt leichter zu lösen ist.

Ohne radikale Änderungen (z. B. das Umschreiben des gesamten Codes in C oder Assembler-Einfügungen mit Fastcall und Absenken des Frame-Zeigers) können Sie auf einem sehr bescheidenen Computer eine hohe Leistung erzielen. Das Pareto-Prinzip kann auf Optimierungen angewendet werden - es stellt sich heraus, dass geringfügige Optimierungen einen starken Einfluss haben, da dieser Code kritisch ist und sehr oft aufgerufen wird.

Weitere Optimierung

Die folgenden Methoden können die Programmleistung erheblich verbessern. Einige von ihnen funktionieren nicht in allen Fällen, aber unter bestimmten Bedingungen.

• Umschreiben von Code im C-Stil und anderen 1972. Wir ersetzen ifstream durch das analoge Gegenstück, Vektoren mit Arrays, lernen alle Compileroptionen und kämpfen um jeden Prozessortaktzyklus.
• Parallelisierung. Zum Beispiel gibt es im Code ein Stück, in dem die Zeilen nacheinander aktualisiert werden, dann die Spalten:

  ... if (!UpdateGroupsState(solver, dead_rows, row_groups, row_masks)) { return false; } if (!UpdateGroupsState(solver, dead_cols, col_groups, col_masks)) { return false; } return true; 

Diese Funktionen sind unabhängig voneinander und haben außer dem variablen Solver (Typ OneLineSolver) keinen gemeinsamen Speicher. Sie können also zwei Solver-Objekte erstellen (hier ist offensichtlich nur eines Solver) und zwei Threads in derselben Funktion starten. Der Effekt ist folgender: Bei den Farbkreuzworträtseln wird das „Schwierigste“ doppelt so schnell gelöst, bei Schwarzweiß ist das gleiche um ein Drittel schneller und die durchschnittliche Zeit hat sich aufgrund der relativ hohen Kosten für die Erstellung von Threads erhöht.

Aber im Allgemeinen würde ich nicht empfehlen, es im aktuellen Programm richtig zu machen und es ruhig zu verwenden - erstens ist das Erstellen von Threads eine kostspielige Operation, Sie sollten nicht ständig Threads für Mikrosekunden-Aufgaben erstellen, und zweitens können Threads mit einer Kombination von Programmargumenten auf welche verweisen Externer Speicher, zum Beispiel beim Erstellen von Bildern einer Lösung - dies sollte berücksichtigt und gesichert werden.

Wenn die Aufgabe ernst wäre und ich viele Daten und Multi-Core-Maschinen hätte, würde ich noch weiter gehen - Sie können mehrere konstante Threads erstellen, jeder hat sein eigenes OneLineSolver-Objekt und eine andere thread-sichere Struktur, die die Verteilung der Arbeit und bei Bedarf steuert dazu gibt es einen Verweis auf die nächste Zeile / Spalte für die Lösung. Threads wenden sich nach dem Lösen eines anderen Problems erneut der Struktur zu, um etwas anderes zu lösen. Im Prinzip kann ein Nichtogrammproblem gestartet werden, ohne das vorherige zu vervollständigen, beispielsweise wenn diese Struktur in das gegenseitige UND aller Zellen eingebunden ist und dann einige Flüsse frei sind und nichts tun. Weitere Parallelisierung kann auf der GPU über CUDA erfolgen - es gibt viele Optionen.

• Verwendung klassischer Datenstrukturen. Bitte beachten Sie: Als ich den Pseudocode der Lösung für Farb-Nonogramme zeigte, funktionieren die Funktionen CanInsertColor und PlaceColor überhaupt nicht $$$O (1)$im Gegensatz zu Schwarz-Weiß-Nonogrammen. In einem Programm sieht es so aus:

 bool OneLineSolver::CanPlaceColor(const vector<int>& cells, int color, int lbound, int rbound) { // Went out of the border if (rbound >= cells.size()) { return false; } // We can paint a block of cells with a certain color if and only if it is // possible for all cells to have this color (that means, if every cell // from the block has color-th bit set to 1) int mask = 1 << color; for (int i = lbound; i <= rbound; ++i) { if (!(cells[i] & mask)) { return false; } } return true; } void OneLineSolver::SetPlaceColor(int color, int lbound, int rbound) { // Every cell from the block now can have this color for (int i = lbound; i <= rbound; ++i) { result_cells_[i] |= (1 << color); } } 

Das heißt, es funktioniert für die Leitung, z $$$O (N)$(Später wird die Bedeutung eines solchen Codes erläutert.)

Mal sehen, wie Sie die beste Komplexität erzielen können. Nehmen Sie CanPlaceColor . Diese Funktion überprüft dies unter allen Nummern des Vektors im Segment $$$[lbound, rbound]$Bitnummer $$$color$auf 1 gesetzt. Entsprechend können Sie nehmen $$$UND$alle Nummern dieses Segments und überprüfen Sie die Bitnummer $$$color$. Mit der Tatsache, dass die Operation $$$UND$kommutativ sowie Summe, Minimum / Maximum, Produkt oder Operation $$$Xor$zum schnellen Zählen $$$UND$, . :

1. SQRT-. $$$O(\sqrt{N})$, $$$O(\sqrt{N})$. .
2. . $$$O(N\log{N})$, $$$O(\log{N})$. .
3. (Sparse Table). $$$O(N\log{N})$, $$$O(1)$. .

, - ( $$$O(N)$, $$$O(1)$) , , , $$$\ varphi$, $$$\varphi(\alpha, \beta) \in \{\alpha, \beta\}$, — (, ...)

SetPlaceColor . . SQRT- ( " "). - .

- — .

, — , ? :

1. . $$$\log$, , — ( magic number , ). , $$$N=10^{5}$, $$$O(N^2)$10 , $$$O(N\log{N})$0.150 , $$$N$, . , ( ): $$$O(N\sqrt{N})$versus $$$O(N\log^2{N})$. $$$N$( ) — 15-30.
2. , .

— , - — $$$N$, . , ~25% ~11% , . - , , , .

— , . .

• . , , - . : , , "" ? , , ! . , .
• (, 1337 1000x1000) . std::bitset , — , .

, . "" . , C++ ( rope , ), hashtable , 3-6 / 4-10 /, unordered_map. , boost.

ROFL Omitting Format Language

, , , -.

ROFL — , "GNU's Not Unix". , , , , , . Omitting — (, , : — ).

, Matroska — 4 [52][4F][46][4C], , , , 3 , — , .

, MIT, — , .

GitHub . , , (, ). Magick++ args .

, ( ). nonograms.ru , , .

nonograms.ru .. KyberPrizrak , , , ! nonograms.ru, .

.