Auf Habré gab es einige Artikel über die Erzeugung von Kreuzworträtseln. In einem von ihnen,
"Das komplexeste Kreuzworträtsel, das von einem Computer zusammengestellt wurde", wurde von einem sehr komplexen Kreuzworträtsel gesprochen, das von einem Computer zusammengestellt wurde und manuell "ein wenig helfen musste". Der zweite Artikel,
"Algorithmus zur Erzeugung von Kreuzworträtseln", befasst sich mit dem Algorithmus, den der Autor zum Erstellen von Kreuzworträtseln entwickelt hat, und stellt fest, dass dieses "schwierigste Kreuzworträtsel" nicht erobert wurde und dass "dieser unbesiegte Höhepunkt jemanden dazu inspirieren wird, einen weiteren Sturm zu nehmen!" Nun, Sie können die Herausforderung annehmen. Was dabei herauskam, schau unter den Schnitt.
Am Anfang werde ich dieses komplizierteste Kreuzworträtsel geben:
Das erste, was Sie finden müssen, ist eine Liste von Wörtern, die beim Zusammenstellen dieses Kreuzworträtsels verwendet werden. Als solche Liste wurden zwei Dateien aus den obigen Artikeln entnommen - eine Datei mit russischen Wörtern, eine Datei mit englischen. Dann musste die Hauptfrage gelöst werden - welcher Algorithmus zum Kompilieren dieses Kreuzworträtsels verwendet werden sollte. Tatsächlich ist dieses Kreuzworträtsel nicht durch die Anzahl der Wörter, sondern durch die Anzahl der Schnittpunkte „kompliziert“. Es ist klar, dass Brute-Force-Angriffe hier nicht geeignet sind, da es zu lange dauern würde, alle Optionen zu sortieren. In dem oben genannten Artikel wurde angenommen, dass viele Heuristiken den Suchprozess beschleunigen. Dieses Kreuzworträtsel wurde jedoch weder in der russischen noch in der englischen Version zusammengestellt. Sie können weiterhin andere Heuristiken entwickeln, um die Lösung zu beschleunigen. Die meisten davon wurden jedoch bereits in SAT-Solvern erfunden und implementiert. Daher können Sie die Aufgabe in ein Formular übersetzen, das für SAT-Löser verständlich ist, und eines davon verwenden.
Was ist der SAT-Löser und welche Informationen erwartet er an der Eingabe? Ich habe im Artikel
„Lösen des Kachelproblems mit Hilfe des SAT-Lösers anhand des Pentamino-Beispiels“ berücksichtigt . Im Fall der Erzeugung eines Kreuzworträtsels ist ein etwas anderer Ansatz erforderlich, um das Problem in konjunktiver Normalform zu formulieren, die ich nun skizzieren werde.
Als erstes sortieren Sie alle Wörter in der Liste in Gruppen. Jede Gruppe enthält Wörter gleicher Länge. Natürlich können Sie für jedes Wort im Kreuzworträtselraster ein Wort aus der Gruppe mit der entsprechenden Länge auswählen. Wir verknüpfen jedes Wort aus der Gruppe, das in einem einzelnen Wort aus dem Raster geschrieben werden kann, mit einer Booleschen Variablen. Diese Variable ist wahr, wenn das angegebene Wort aus der Gruppe in dieses Wort aus dem Raster geschrieben ist, andernfalls falsch.
Lassen Sie uns nun eine Formel erstellen, die unser Problem beschreibt, dh wir werden unseren Variablen tatsächlich Einschränkungen auferlegen. Finden Sie alle Schnittpunkte von Wörtern vertikal mit Wörtern horizontal. Für jeden Schnittpunkt bestimmen wir, welche Wortpaare miteinander kombiniert werden und welche nicht. Hierbei tritt jedoch ein Problem auf, da die Anzahl solcher Paare für eine Kreuzung eine Million überschreiten kann. Daher werden wir einen anderen Ansatz verwenden. Wir sortieren die Wörter in der Gruppe, die dem Wort horizontal entspricht, nach Buchstaben, die am Schnittpunkt dieser beiden Wörter stehen. Machen Sie dasselbe für das Wort vertikal. Anscheinend haben übereinstimmende Wörter an der Kreuzung den gleichen Buchstaben. Wir führen eine zusätzliche Variable für jeden Buchstaben ein, der in mindestens einem Wort horizontal und vertikal vorkommt. Die Bedingung, dass die beiden Wörter miteinander kombiniert werden, ist nun, dass mindestens eine solche Variable wahr ist. Somit wird für jeden Schnittpunkt eine Klausel hinzugefügt, die aus Variablen besteht, die den Buchstaben entsprechen. Jetzt müssen Sie die Variablen, die einem bestimmten Buchstaben entsprechen, den Wörtern zuordnen, die diesen Buchstaben an der Position des Schnittpunkts der Wörter enthalten. Dies geschieht durch eine Reihe von Klauseln, die gewährleisten, dass die beiden Booleschen Variablen denselben Wert haben. Und schließlich müssen Sie sicherstellen, dass das Kreuzworträtsel keine identischen Wörter enthält. Dazu fügen wir für jedes Wort aus der Datenbank Klauseln der Form hinzu (nicht x_i V nicht x_j), wobei x_i die Variable ist, die seiner Instanz in einem Wort aus dem Kreuzworträtselraster entspricht, und x_j die Variable ist, die seiner Instanz in einem anderen Wort aus dem Kreuzworträtselraster entspricht.
Das Erstellen dieses „kompliziertesten Kreuzworträtsels“ mit russischen Wörtern dauert auf einem Intel 2600K 3,5 GHz mit 16 Gigabyte Speicher einige Minuten. Das Erstellen eines Kreuzworträtsels mit englischen Wörtern dauerte ungefähr zwanzig Minuten.
Danach habe ich andere Kreuzworträtsel ausprobiert. Zum Beispiel gelang es mir, ein Kreuzworträtsel aus englischen und russischen Wörtern in Form eines 6 x 6-Quadrats zu erstellen, in dem sich alle Wörter überschneiden.
Als nächstes gebe ich die resultierenden Kreuzworträtsel. Wer möchte, kann sie lösen.
Option mit russischen Wörtern:1 Horizontales Zeitlupenflugzeug mit praller Nase
6 Horizontales japanisches Saitenmusikinstrument
10 Horizontal In der skandinavischen Mythologie entstand ein Riese aus dem vorzeitigen Chaos des Weltabgrunds
14 Horizontales Exil der Gattung
15 Horizontales Mineral
16 Horizontaler tschechischer Dichter (20 c.)
17 Horizontale Insel im Golf von Guinea (Äquatorialguinea)
18 Horizontaler Mund, Lippen (veraltet)
19 Horizontaler Groll, Wut
20 Horizontal Nur eine politische Partei anwesend
23 Horizontal Irlands größter Fluss
24 Horizontale Klerikerkleidung
25 Horizontaler Fluss in Angola und Zaire, linker Nebenfluss des Kwango
27 Horizontale Marke des ungarischen Busses
32 Horizontale Stadt und Hafen in der DVRK
35 Horizontale Schwiegermutter oder Schwiegermutter
37 Horizontale Solanaceae-Pflanze
38 Horizontal Einer, der Wolle kardiert
41 Horizontaler weiblicher Name (griechisch gut, freundlich)
42 Horizontaler kanadischer künstlicher Satellit
43 Horizontaler Charakter von Webers Oper '' Free Shooter ''
44 Horizontale Stadt in der Slowakei
46 Horizontale Ausgaben
48 Horizontal gezüchtete Fische der Karpfenfamilie
50 Horizontal In der japanischen Mythologie die Gottheit vieler Reisohren
54 Horizontaler anorganischer kristalliner Leuchtstoff
59 Horizontaler iranischer Prophet, Begründer des Manichäismus (3 c.)
60 horizontale Bauernhäuser auf den Inseln Westindiens
61 Horizontal Shepherds Hunderasse (ähnlich einem Fuchs)
62 Horizontal (trans.) Blöder störrischer Dummkopf
63 Horizontale Stadt in der Region Orenburg am Ural
64 Horizontal In der griechischen Mythologie wurde ein Riesenjäger von Artemis getötet
65 Horizontaler chilenischer Sänger und Dichter
66 Horizontal Der Charakter des indischen Volkstheaters, das Bild eines ruinierten Spielers, eines Parasiten mit einem reichen Gönner
67 Horizontale Tschetschenen und Ingusch Mutter Erde
1 Vertikaler Spitzname eines der Führer des Volksaufstands von 1413 in Paris
2 Vertikales unbefriedigtes Gefühl
3 Vertikaler deutscher Paläontologe (1800-1862)
4 Vertikal Die Eroberung der von den Mauren eroberten Gebiete durch die indigene Bevölkerung der Iberischen Halbinsel
5 Vertikaler russischer Gitarrenmeister
6 Vertikaler schwedischer und russischer Militärführer, General, Mitarbeiter von Peter I. (1667-1717)
7 Vertikaler Musiker, der ein Musikinstrument spielt
8 Vertikaler Sprecher, beredter Mann
9 Vertikaler Grat in Japan, Insel Honshu
10 Vertikales koreanisches Percussion-Musikinstrument, achteckige Trommel
11 Vertikaler lettischer Dirigent (1917-1967)
12 Vertikale Herzlichkeit, Wiesel
13 Vertikal In der slawischen Mythologie der Geist, die Verkörperung des Todes
21 Vertikales Animationsgenre mit Ursprung in Japan
22 Vertikale Gewindeheizlampenkathode
26 Vertikaler See in der Region Archangelsk
28 Vertikaler Fluss in Spanien
29 Vertikal Kleiner Laubwald
30 Vertikaler seltener Gegenstand
31 Vertikaler belgischer Windmeister, Erfinder des Saxophons
32 Vertikaler kleiner Rahmen
33 Vertikales Schwarz
34 Vertikal Altes Maß für das pharmazeutische Gewicht = 62,21 mg
36 Vertikale Provinz in Saudi-Arabien
39 Vertikales Anti-Reibungsfett
40 Vertikale skulpturale Dekoration von Kapitellen, Gesimsen usw. in Form von stilisierten Stielen und Blättern einer solchen Pflanze
45 Vertikaler russischer Schriftsteller, Dichter, Filmautor, Drehbuchautor für die Filme von A. Sokurov (Moloch, Stier)
47 Vertikaler Polysulfidkautschuk, eine Art synthetischer Kautschuk
49 Vertikaler englischer Pathologe (Nobelpreis 1945)
51 Vertikal In der muslimischen Mythologie ein Geist mit besonderer Kraft
52 Vertikaler Gänseschrei
53 Vertikaler weiblicher Name (griechischer Name der Göttin des friedlichen Lebens; Frieden)
54 Vertikaler Schachgroßmeister
55 Vertikal Historisch geformte Gruppe der Menschheit, vereint durch einen gemeinsamen Ursprung
56 Vertikaler Hybrid von der Kreuzung eines einhöckrigen Kamels (Dromedar) mit einem zweibuckeligen (Bactrian), Nar
57 Vertikal Mechanischer Wert, der die Beschleunigung verursacht
58 Vertikaler japanischer Schriftsteller (1909-1989, "Notizen des Gefangenen", "Lichter auf dem Feld", "Schlacht auf Leyte")
Option mit englischen Wörtern:1 Horizontal Ein Ort, der viele Besucher anzieht
6 Horizontal Einer von mehreren Fischen der Familie Carangidae
10 Horizontal Eine Sammlung von Fakten, aus denen Schlussfolgerungen gezogen werden können
14 Horizontale Nintu)
15 Horizontale Körperbedeckung eines lebenden Tieres
16 Horizontal Ein dumpfer anhaltender (normalerweise mäßig intensiver) Schmerz
17 Horizontal Eine Reaktion des Körpergewebes auf Verletzungen oder Reizungen
18 Horizontale Gattung der Anatidae-Süßwasserenten
19 Horizontal Die Dynastie, die von 947 bis 1125 einen Großteil der Mandschurei und Nordostchinas regierte
20 Horizontal Eine weiße kristalline Verbindung, die als Analgetikum und auch als Antipyretikum verwendet wird
23 Horizontal Eine Stadt in Zentraltansania
24 Horizontaler Gott des Todes
25 Horizontal geformter und getrockneter Teig aus Mehl und Wasser und manchmal Ei
27 Horizontal Ein Mitglied der Siouan in Virginia und North Carolina
32 Horizontal Ein starkes unruhiges Verlangen
35 Horizontaler südafrikanischer Prälat und Führer des Antiapartheid-Kampfes (geboren 1931)
37 Horizontal Ein kommerzielles Dokument, mit dem jemand aufgefordert wird, etwas gegen Bezahlung zu liefern
38 Horizontale Beißmücken
41 Horizontal Eine antike Stadt in Nordportugal
42 Horizontal Eine Eskimohütte
43 Horizontaler Drehmechanismus in Form eines universell montierten Spinnrads, das Widerstand gegen Drehungen in jede Richtung bietet
44 Horizontal Die Hauptstadt von Bahrain
46 Horizontal Der Vorgang, bei dem das Haar leicht getönt wird
48 Horizontale Gattung der Majidae
50 Horizontal Eine von mehreren Pflanzen der Gattung Camassia
54 Horizontal fliegende Knurrhähne
59 Horizontal Die gesamte Ernte kann gleichzeitig geerntet werden
60 Horizontal Ein vom US-Kongress verabschiedetes Gesetz, das verhindern soll, dass Mitarbeiter im Laufe ihrer Beschäftigung verletzt werden oder an Krankheiten erkranken
61 Horizontal Ein schwerer Eisen- oder Stahlblock, auf den heiße Metalle durch Hämmern geformt werden
62 Horizontaler englischer Staatsmann, der sich der Scheidung Heinrichs VIII. Von Katharina von Aragon widersetzte und inhaftiert und enthauptet wurde
63 Horizontal Ein Mann, der eine Frau umwirbt
64 Horizontaler Baseballspieler der Vereinigten Staaten
65 Horizontal Ein geheimer Blick
66 Horizontal Kleine schlanke Möwe mit schmalen Flügeln und einem gegabelten Schwanz
67 Horizontal Bekannt für Trauben und Oliven sowie Olivenöl
1 Vertikaler französischer Revolutionsführer (geboren in der Schweiz), der führend beim Sturz der Girondisten war und von Charlotte Corday (1743-1793) in seinem Bad erstochen wurde
2 Vertikale einjährige bis mehrjährige Kräuter des Mittelmeerraums
3 Vertikale tropische südostasiatische Strauchrebe mit würzigen beerenartigen Früchten
4 Vertikale Ani
5 Vertikal Das erste Tageslicht
6 Vertikaler Titel für den ehemaligen Erbmonarchen des Iran
7 Vertikal Ein Fotograf, der eine Filmkamera bedient
8 Vertikal Eine Stadt in der Südtürkei am Seyhan
9 Vertikal Eine trockene Region mit wenig oder keiner Vegetation
10 Vertikaler surrealistischer spanischer Maler (1904-1989)
11 Vertikal Jede der verschiedenen wasserlöslichen Verbindungen mit saurem Geschmack, die Lackmusrot färben und mit einer Base unter Bildung eines Salzes reagieren können
12 Vertikal Ein Eingeborener oder Einwohner Thailands
13 Vertikal (im Gnostizismus) eine göttliche Kraft oder Natur, die vom Höchsten Wesen ausgeht und verschiedene Rollen im Betrieb des Universums spielt
21 Vertikal Ein aktiver Vulkan im Südosten Kolumbiens in den Anden
22 Vertikal Ein Lepton von sehr großer Masse
26 Vertikal Ein Mitglied der südamerikanischen Indianer, die in Brasilien und Paraguay leben
28 Vertikal Der wichtigste sensorische Nerv des Gesichts und der motorische Nerv für die Kaumuskulatur
29 Vertikal Ein Miniatur-Whirlpool oder Wirbelwind, der entsteht, wenn sich der Strom einer Flüssigkeit auf sich selbst verdoppelt
30 Vertikaler britischer Künstler und Verfasser von Unsinnsversen (1812-1888)
31 Vertikaler Schokoladenkeks mit weißer Sahnefüllung
32 Vertikal Eine ballistische Rakete, die von einem Kontinent zum anderen fliegen kann
33 Vertikal Eine dreifarbige tschadische Sprache
34 Vertikal Eine Kapazitätseinheit zur Messung von frischem Hering
36 Vertikal Groß Große saftige Hybride zwischen Mandarine und Grapefruit mit einer dicken, faltigen Haut
39 Vertikaler, glatt gewebter (oft glasierter) Stoff aus Wolle oder Wolle und Baumwolle, der vor allem für Futter, Bekleidung und Vorhänge verwendet wurde
40 Vertikal Eine Einheit des Apothekergewichts, die 480 Körnern oder einem Zwölftel Pfund entspricht
45 Vertikal Eine Stadt in Zentralbelgien
47 Vertikal Ein langer, farbenfroher Schal
49 Vertikal Ein Buch im Alten Testament, das beschreibt, wie Josua die Israeliten nach dem Tod Moses nach Kanaan (das verheißene Land) führte
51 Vertikal Ein nichtsteroidales entzündungshemmendes Arzneimittel (Handelsnamen Advil und Motrin und Nuprin) zur Linderung von Arthritis-Schmerzen sowie als Analgetikum und Antipyretikum
52 Vertikale ziegenartige Antilope in Zentral-Eurasien mit einer stumpfen Nase wie ein Rüssel
53 Vertikaler Tennisspieler der Vereinigten Staaten (geboren 1973 in Jugoslawien)
54 Vertikal Eine leichte Nässe
55 Vertikale Sukkulenten mit Rosetten von Blättern, normalerweise mit faserartigen Hanf und Ähren von auffälligen Blüten
56 Vertikale Aktivität zur Aufrechterhaltung eines guten Betriebszustands
57 Vertikal (südafrikanisch) eine Reise mit einem Ochsenwagen (insbesondere eine organisierte Migration einer Gruppe von Siedlern)
58 Vertikal Ein Bergsee (insbesondere ein von Gletschern gebildeter See)
Kreuzworträtsel 6 gegen 6 auf Russisch:1 Horizontaler sowjetischer Testpilot, Held der Sowjetunion, einer der Teilnehmer des Nonstop-Fluges Moskau - Nordpol - Vancouver
2 Horizontales Ohr
3 Horizontaler Wahrsager
4 Horizontale Stadt in Italien auf der Insel Sizilien
5 Horizontal gewelltes strukturiertes Garn, das durch Riffeln in beheizten Kammern erhalten wird
6 Horizontaler französischer Filmemacher, Drehbuchautor ("Bad Blood", "Boyfriend Meets Girl")
7 Vertikale Silbermünze des Großherzogtums Litauen aus dem 16. Jahrhundert
8 Vertikaler amerikanischer Biochemiker synthetisierte zuerst das tRNA-Gen (Nobelpreis 1968)
9 Vertikale Stadt in der Russischen Föderation, Nordossetien, am Fluss Ardon, an der ossetischen Militärstraße
10 Vertikale horizontale Nische in der Wand der Grabkammer, in der der Verstorbene aufgestellt und zugemauert oder mit einem Baldachin aufgehängt wurde
11 Vertikal Der Oberschenkel des Kadavers
12 Vertikale Stadt im Südosten Frankreichs
Kreuzworträtsel 6 gegen 6 auf Englisch:1 Horizontal Ein Mitglied des indischen Volkes in Nordkalifornien und Südoregon
2 Horizontal Ein Mitglied einer der vier Abteilungen der prähistorischen Griechen
3 Horizontal Kann süchtig machen
4 Horizontaler griechischer Lichtgott
5 Horizontal Kleine Personen- oder Kleidungs- oder Nähartikel
6 Horizontal Wertvoller Holzbaum Neuseelands mit hartem rötlichem Holz für Möbel, Brücken und Kais
7 Vertikal Eine gerade Linie, die eine Kurve an zwei oder mehr Punkten schneidet
8 Vertikal Einer von mehreren Altvögeln mit Haube und einer schlanken, nach unten gekrümmten Rechnung
9 Vertikaler amerikanischer Schriftsteller für Kinderbücher (1832-1888)
10 vertikale nordamerikanische Drosseln
11 Vertikal Eine Person, deren Beruf darin besteht, Kleidungsstücke herzustellen und zu verändern
12 Vertikale Gattung der Annonaceae
Fazit
Die Verwendung des SAT-Lösers erhöht die Komplexität der Kreuzworträtsel, die generiert werden können. Wie im vorherigen Artikel möchte ich den nächsten unbestrittenen Höhepunkt bitten - ein Kreuzworträtsel aus russischen oder englischen Wörtern in Form eines Quadrats 7 mal 7 zu bilden. Wer wird die Herausforderung annehmen?