Können Sie sich vorstellen, das Kreuzworträtsel der New York Times ohne Anhaltspunkte zu lösen? Vielleicht nicht mit all der Kreativität und den neuen Wörtern und Phrasen, die in modernen Kreuzwörtern vorkommen, aber mit einer festen Wortliste gibt es einige Hoffnung. In dieser Herausforderung erstellen Sie ein Kreuzworträtselgitter, in dem dies theoretisch möglich ist.

Die Herausforderung

Maximieren Sie die Anzahl der weißen Quadrate in einem weiß und schwarz schattierten 15x15-Kreuzworträtselgitter, sodass die weißen Quadrate eindeutig mit Buchstaben gefüllt werden können, sodass jedes Quer- und Abwärtswort in der internationalen Scrabble-Wortliste angezeigt wird.

Klärung des Netzaufbaus

In US-Zeitungen werden Kreuzworträtsel normalerweise so konstruiert, dass jeder Buchstabe "überprüft" wird, was bedeutet, dass er sowohl Teil eines "Über" -Worts als auch eines "Unter" -Worts ist. Im Vereinigten Königreich und anderswo (insbesondere bei kryptischen Kreuzwörtern ) ist dies nicht unbedingt der Fall: Wenn ein "Über" - oder "Unter" -Wort nur ein Buchstabe ist, muss es kein tatsächliches Wort sein (wie "A" oder "I") "). Befolgen Sie für diese Herausforderung die lockereren Regeln: Wörter mit einem Buchstaben müssen nicht in der Wortliste enthalten sein.

Es gibt verschiedene andere Traditionen (in den USA und anderswo), von denen keine bei dieser Herausforderung beachtet werden muss. Beispielsweise können Wörter nur zwei Buchstaben lang sein, Wörter dürfen sich wiederholen und das Gitter muss keine (Rotations-) Symmetrie aufweisen.

Ist das überhaupt möglich?

Ja! Sie können ein kurzes Skript schreiben, um zu überprüfen, ob die eindeutige Lösung für das folgende leere Raster auf der linken Seite das ausgefüllte Raster auf der rechten Seite ist:

Das ausgefüllte Raster kann wie folgt in einem computerlesbaren Format angezeigt werden:

###CH##########
###YE##########
###AM##########
CYANOCOBALAMINE
HEMOCHROMATOSES
###CH##########
###OR##########
###BO##########
###AM##########
###LA##########
###AT##########
###MO##########
###IS##########
###NE##########
###ES##########

Ihre Lösung

Das obige Raster hat 56 weiße Quadrate von insgesamt 225 Quadraten im Raster 15x15. Dies dient als Grundlage für diese Herausforderung. Gitter mit weniger weißen Quadraten können auch aus anderen Gründen als ihrer Punktzahl interessant sein, beispielsweise wenn sie einigen der oben genannten ästhetischen Traditionen entsprechen.

Bitte reichen Sie Ihre Lösung im gleichen Format ein wie die oben angegebene computerlesbare Baseline. Bitte geben Sie Code an, der bestätigt, dass es eine eindeutige Lösung für Ihr Raster gibt.

Interessante Code-Schnipsel (z. B. zum Durchsuchen des Raums der Möglichkeiten) und Diskussionen darüber, wie Sie Ihr Raster gefunden haben, werden geschätzt.

Die Wortliste

Die internationale Scrabble-Wortliste war früher als SOWPODS bekannt und heißt jetzt Collins Scrabble Words (CSW). Es wird in den meisten Ländern (mit Ausnahme der USA) verwendet. Wir ziehen es vor, diese Liste zu verwenden, da sie britische Schreibweisen enthält und im Allgemeinen wesentlich mehr Wörter enthält als die amerikanische Wortliste. Es gibt mehrere Ausgaben dieser Liste, die sich geringfügig unterscheiden. Sie können verschiedene Versionen dieser Liste finden, die von Wikipedia , auf Github , in Peter Norvigs Natural Language Corpus und anderswo verlinkt sind und oft noch als "SOWPODS" bezeichnet werden.

Diese Herausforderung hängt stark von der Breite der Wortlistenauswahl ab, weniger jedoch von kleineren Details. Das obige Baseline-Beispiel funktioniert beispielsweise mit jeder CSW-Edition, CHist jedoch kein Wort in der American Scrabble-Wortliste. Im Falle einer Diskrepanz bevorzugen wir CSW19, die neueste Ausgabe von CSW. (Wenn wir diese Liste verwenden, die in diesem Jahr veröffentlicht wurde, können wir davon ausgehen, dass Antworten auf diese Herausforderung länger gültig sind.) Sie können diese Liste interaktiv auf der offiziellen Scrabble- Website abfragen oder sie (sowie die vorherige Ausgabe, CSW15) von Board & Card Games Stack Exchange oder Reddits r / scrabble herunterladen .

Tldr : Die maßgebliche Wortliste für diese Herausforderung ist als reine Textdatei (279.496 Wörter, eines pro Zeile) über die Stapelbörse für Brettspiele und Kartenspiele verfügbar .

Weitere Diskussion

Ein Thema, das in einer frühen Antwort und einem Kommentar angesprochen wurde, ist, warum vorhandene Kreuzworträtsel (z. B. in der NYT) diese Frage nicht beantworten. Insbesondere ist der Rekord für die geringste Anzahl von schwarzen Quadraten (und damit die größte Anzahl von weißen Quadraten) für ein veröffentlichtes NYT-Kreuzworträtsel bereits der berühmteste Rekord für Kreuzworträtsel. Warum können wir das Datensatzraster nicht verwenden ? Es gibt einige Probleme:

Viele der Antworten in NYT-Kreuzwörtern erscheinen nicht in unserer Wortliste. Zum Beispiel enthält das Datensatzraster PEPCID(einen Markennamen), APASSAGETOINDIA(einen aus vier Wörtern bestehenden Eigennamen für einen Film und einen Roman, der ohne Leerzeichen geschrieben ist) und STE(eine Abkürzung für "Sainte"). Es scheint, dass das Datensatzraster mit Scrabble-Wörtern nicht lösbar ist.
Die bloße Erweiterung der Wortliste um weitere Wörter hilft bei dieser Herausforderung nicht unbedingt: Selbst wenn alle Wörter im Datensatzraster in unserer Wortliste erscheinen würden, wäre die Lösung ohne die Hinweise nicht eindeutig . Es ist oft möglich, einige Buchstaben am Ende der Antworten zu ändern, während alles ein Wort bleibt. (Beispielsweise kann der ganz rechts stehende Buchstabe von a Din a geändert werden R.) Dies ist in der Tat Teil des (menschlichen) Konstruktionsprozesses beim Schreiben eines Kreuzworträtsels, bei dem versucht wird, "bessere" Wörter zu erhalten.

Der Grund, warum gewöhnliche Kreuzworträtsel (normalerweise) eine einzigartige Lösung haben, ist, dass die Hinweise helfen, die richtigen Antworten einzugrenzen. Wenn Sie einfach versuchen, das Raster mit Wörtern zu füllen, ohne Hinweise zu verwenden, wird es wahrscheinlich keine oder viele Möglichkeiten geben. Hier ist ein Beispiel für drei verschiedene Füllungen (unter Verwendung der Wortliste für diese Herausforderung!) Für dasselbe Raster (eine, die in der NYT relativ häufig verwendet wird):

Ein weiteres Problem, das in den Kommentaren angesprochen wurde, ist der Ungläubige, dass diese Frage eine Herausforderung für die Kodierung darstellt . Vielleicht ist es nicht sofort klar, aber es ist schwierig, überhaupt eine gültige Antwort auf diese Herausforderung zu finden . Das Finden der obigen Grundlinie umfasste mehrere speziell gestaltete Suchprogramme, bei denen nicht garantiert wurde, dass sie eine Antwort finden. Ich persönlich kenne nicht einmal einen allgemeinen Weg, um ein willkürliches Raster zu lösen, wenn Sie die Antwort in angemessener Zeit wollen. Bestehende Kreuzworträtsel-Konstruktionsprogramme können helfen, aber ich gehe davon aus (möglicherweise falsch), dass sie die Möglichkeiten nicht vollständig durchsuchen. (Ich habe ein solches Programm für die drei nebeneinander angeordneten Gitter oben verwendet. Dies hat funktioniert, weil dieses bestimmte Gitter viele Lösungen zulässt.)

code-challenge optimization crossword A. Rex
quelle

Meta-Post zu dieser allgemeinen Art von Fragen: codegolf.meta.stackexchange.com/questions/18117/…

A. Rex

Grids with fewer white squares may also be interesting for reasons other than their score, for example if they satisfy some of the aesthetic traditions mentioned above.

Verzichten Sie auf die ästhetische Option (" ") - ähnlich wie bei der Vermeidung von Bonussen beim Codegolf möchte ich, dass eine Code-Herausforderung nur eine Sache betrifft. Dies bedeutet, dass alle Antworten gleich für gleich verglichen werden können. Es macht es auch klar objektiv, was bei der Wiedereröffnung von Abstimmungen helfen wird.

Trichoplax

2. Wählen Sie eine einzelne Wortliste und bestehen Sie für alle Antworten darauf. Der tldr erwähnt eine verbindliche Wortliste, aber die vorherige Diskussion kann dazu führen, dass die Leute glauben, sie könnten eine der genannten auswählen. Es kann hilfreich sein, die strengen Anforderungen an der Spitze des Beitrags zu halten und deutlich zu machen, dass andere Details nicht Teil der Spezifikation der Herausforderung sind. Lassen Sie im Idealfall alles überflüssige weg, um den Beitrag kurz und sofort eindeutig zu halten.

Trichoplax

3. Machen Sie die Angabe des Codes, mit dem die Lösung gefunden wurde, zur Voraussetzung für eine gültige Antwort.

Trichoplax

Dies ist die Art von Herausforderung, die von einem Chatroom für die Diskussion von Ansätzen profitieren kann. Wenn Sie einen Chatroom einrichten und ab dem Ende der Spezifikation einen Link zu ihm erstellen, können Sie die Diskussion dort als erste Beiträge veröffentlichen und dies in der Herausforderung für Personen erwähnen, die mehr wissen möchten.

Trichoplax

180 weiße Quadrate

Meine Strategie bestand einfach darin, ein kleineres Rechteck ohne schwarze Quadrate zu finden, damit es eindeutig ausgefüllt werden kann. Alle 2×kRechtecke haben mehrere Lösungen. Für 3×kRechtecke gibt es mehrere Lösungen kzwischen 3 und 14, aber es gibt genau eine Lösung für k=15.

Ich füge dann 4 solche Rechtecke in das Raster ein. Dies bedeutet, dass jedes Wort viermal in der Lösung vorkommt, was normalerweise bei der Kreuzworträtselkonstruktion verpönt wird, aber für diese Herausforderung in Ordnung ist. Andererseits hat diese Lösung sowohl Links- / Rechts- als auch Oben- / Unten-Symmetrie!

Computerlesbares Gitter:

HETERONORMATIVE
OVEROPINIONATED
POSSESSEDNESSES
###############
HETERONORMATIVE
OVEROPINIONATED
POSSESSEDNESSES
###############
HETERONORMATIVE
OVEROPINIONATED
POSSESSEDNESSES
###############
HETERONORMATIVE
OVEROPINIONATED
POSSESSEDNESSES

Hier ist der R-Code, mit dem ich alle Lösungen für eine bestimmte Rastergröße gefunden habe. Es ist zu langsam, alle Dreiergruppen von Wörtern mit 15 Buchstaben zu durchlaufen. Stattdessen versuche ich, Rechtecke durch Ausfüllen

Setzen der ersten beiden Spalten (zwei 3-Buchstaben-Wörter)
Durchlaufen Sie dann alle Wörter mit 15 Buchstaben, beginnend mit den ersten beiden Buchstaben, die jetzt festgelegt sind.
Für jede mögliche Wahl der 15-Buchstaben-Wörter überprüfe ich dann, ob alle generierten 3-Buchstaben-Wörter im Wörterbuch enthalten sind.

Zum Beispiel für die mögliche Lösung, zuerst den Code setzen in HOPund EVOdann in vollendet HETERNORMATIVE, OVEROPINIONATEDund POSSESSEDNESSES, und schließlich überprüft alle 3-Buchstaben - Wörter ( HOP, EVO, TES, ERS, ROE, OPS, NIS, ONE, RID, MON, ANE, TAS, ITS, VEE, EDS).

R-Code

library(fastmatch)
f = "scrabble-wordlist.txt"
d = read.table(f, skip=2, as.is=T, na.strings=NULL)

d$l = apply(d, 2, nchar)
d3 = d[d$l==3, 1]

sp = function(s) strsplit(s, "")[[1]]
cm = function(v) paste0(v, collapse="")
d3s = sapply(d3, sp)

f3 = function(l){
  m = matrix("", 3, l)

  md = sapply(d[d$l == l, 1], sp)
  nf = 0

  a1 = seq(1, 3*l, by=3); a2 = a1 + 1; a3 = a1 + 2

  for(i in 1:ncol(d3s)){
    m[, 1] = d3s[, i]

    id1 = as.matrix(md[, md[1, ] == m[1, 1]])
    id2 = as.matrix(md[, md[1, ] == m[2, 1]])
    id3 = as.matrix(md[, md[1, ] == m[3, 1]])

    if(any(ncol(id1) == 0, ncol(id2) == 0, ncol(id3) == 0)) next

    for(j in 1:ncol(d3s)){
      m[, 2] = d3s[, j]

      jd1 = as.matrix(id1[, id1[2, ] == m[1, 2]])
      jd2 = as.matrix(id2[, id2[2, ] == m[2, 2]])
      jd3 = as.matrix(id3[, id3[2, ] == m[3, 2]])

      if(any(ncol(jd1) == 0, ncol(jd2) == 0, ncol(jd3) == 0)) next

      for(k1 in 1:ncol(jd1)){
        m[1, ] = jd1[, k1]

        for(k2 in 1:ncol(jd2)){
          m[2, ] = jd2[, k2]

          for(k3 in 1:ncol(jd3)){
            m[3, ] = jd3[, k3]

            w = paste0(m[a1], m[a2], m[a3])
            if(all(w %fin% d3)){
              nf = nf + 1
              print(m)
            }
            if(nf >= 2){
              print(c(l, nf))
              return()
            }
          }
        }
      }
    }
  }

  return(nf)
}

Genannt als f3(15). Hat ein paar Stunden auf meinem PC gedauert.

Robin Ryder
quelle

@downvoter Könnten Sie einen Kommentar abgeben?

Robin Ryder

Meine Antwort wurde ebenfalls abgelehnt. 🤷

A. Rex

Erstellen Sie ein einzigartiges lösbares Kreuzworträtsel… ohne Hinweise

Die Herausforderung

Klärung des Netzaufbaus

Ist das überhaupt möglich?

Ihre Lösung

Die Wortliste

Weitere Diskussion

Antworten:

180 weiße Quadrate

R-Code

182 weiße Quadrate