Pouvez-vous imaginer résoudre le puzzle de mots croisés du New York Times sans aucun indice? Peut-être pas avec toute la créativité et les nouveaux mots et expressions apparaissant dans les mots croisés modernes, mais avec une liste de mots fixe, il y a de l'espoir. Dans ce défi, vous créez une grille de mots croisés dans laquelle cela est théoriquement possible.

Le défi

Maximisez le nombre de carrés blancs dans une grille de mots croisés de 15 x 15 ombrés de blanc et de noir, de sorte que les carrés blancs puissent être uniquement remplis de lettres afin que chaque mot en travers et en bas apparaisse dans la liste de mots du Scrabble international.

Clarifications de la construction de la grille

Dans les journaux américains, les grilles de mots croisés sont généralement construites de manière à ce que chaque lettre soit "vérifiée", ce qui signifie qu'elle fait partie à la fois d'un mot " croisé " et d'un mot "descendant". Au Royaume-Uni et ailleurs (en particulier dans les mots croisés cryptés ), ce n'est pas nécessairement le cas: si un mot "en travers" ou "en bas" ne serait qu'une lettre, il ne doit pas nécessairement être un mot réel (comme "A" ou "I "). Pour ce défi, suivez les règles plus détendues: les mots d'une seule lettre n'ont pas besoin d'apparaître dans la liste de mots.

Il existe diverses autres traditions (aux États-Unis et ailleurs), dont aucune n'a besoin d'être suivie dans ce défi. Par exemple, les mots ne peuvent comporter que deux lettres, les mots peuvent se répéter et la grille n'a pas besoin d'avoir une symétrie (rotationnelle).

Est-ce seulement possible?

Oui! On peut écrire un court script pour vérifier que la solution unique à la grille vierge suivante à gauche est la grille remplie à droite:

On peut afficher la grille remplie dans un format lisible par ordinateur comme suit:

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

Votre solution

La grille ci-dessus a 56 carrés blancs sur un total de 225 carrés dans la grille 15x15. Cela sert de base à ce défi. Les grilles avec moins de carrés blancs peuvent également être intéressantes pour des raisons autres que leur score, par exemple si elles satisfont certaines des traditions esthétiques mentionnées ci-dessus.

Veuillez soumettre votre solution dans le même format que la ligne de base lisible par ordinateur ci-dessus. Veuillez inclure du code qui vérifie qu'il existe une solution unique à votre grille.

Des extraits de code intéressants (par exemple pour rechercher l'espace des possibilités) et une discussion sur la façon dont vous avez trouvé votre grille sont appréciés.

La liste de mots

La liste internationale de mots du Scrabble était auparavant connue sous le nom de SOWPODS et s'appelle désormais Collins Scrabble Words (CSW). Il est utilisé dans la plupart des pays (à l'exception notamment des États-Unis). Nous préférons utiliser cette liste car elle comprend des orthographes britanniques et contient généralement beaucoup plus de mots que la liste de mots américaine. Il existe plusieurs éditions de cette liste qui diffèrent légèrement. Vous pouvez trouver différentes versions de cette liste liées à partir de Wikipedia , sur Github , dans Natural Language Corpus de Peter Norvig et ailleurs, souvent encore appelé "SOWPODS".

Ce défi est très sensible à la nature large du choix de la liste de mots, mais moins aux petits détails. Par exemple, l'exemple de base ci-dessus fonctionne avec n'importe quelle édition de CSW, mais CHn'est pas un mot dans la liste de mots American Scrabble. En cas de divergence, nous préférons utiliser CSW19, l'édition la plus récente de CSW. (Si nous utilisons cette liste, qui a été publiée cette année, nous pouvons nous attendre à ce que les réponses à ce défi restent valables plus longtemps). Vous pouvez interroger cette liste de manière interactive sur le site officiel de recherche de mots du Scrabble ou la télécharger (ainsi que l'édition précédente, CSW15) à partir du Board & Card Games Stack Exchange ou du r / scrabble de Reddit .

Tldr : la liste de mots faisant autorité pour ce défi est disponible sous forme de fichier texte (279 496 mots, un par ligne) sur le Board & Card Games Stack Exchange .

Discussion plus approfondie

Une question soulevée dans une réponse et un commentaire au début est pourquoi les mots croisés existants (par exemple, dans le NYT) ne répondent pas à cette question. Plus précisément, le record du plus petit nombre de carrés noirs (et donc le plus grand nombre de carrés blancs) pour un mot croisé NYT publié est déjà le record le plus célèbre dans les mots croisés. Pourquoi ne pouvons-nous pas utiliser la grille d'enregistrement ? Il y a quelques problèmes:

De nombreuses réponses dans les mots croisés NYT n'apparaissent pas sur notre liste de mots. Par exemple, la grille d'enregistrement comprend PEPCID(un nom de marque), APASSAGETOINDIA(un nom propre à quatre mots pour un film et un roman, écrit sans espaces) et STE(une abréviation pour "Sainte"). Il semble que la grille d'enregistrement ne soit pas résoluble avec les mots Scrabble.
Le simple fait d'élargir la liste de mots pour inclure davantage de mots n'aide pas nécessairement à relever ce défi: même si tous les mots de la grille d'enregistrement figuraient sur notre liste de mots, la solution ne serait pas unique sans les indices. Il est souvent possible de modifier certaines lettres à la fin des réponses tout en gardant tout un mot. (Par exemple, la lettre en bas à droite peut être changée de a Dà an R.) En effet, cela fait partie du processus de construction (humain) lors de l'écriture d'un mot croisé, en essayant d'obtenir de «meilleurs» mots.

La raison pour laquelle les mots croisés ordinaires ont (généralement) une solution unique est que les indices aident à affiner les bonnes réponses. Si vous essayez simplement de remplir la grille de mots sans utiliser d'indices, il est probable qu'il n'y aura pas de possibilités ou de nombreuses possibilités. Voici un exemple de trois remplissages différents (en utilisant la liste de mots pour ce défi!) Pour la même grille (celle qui est relativement fréquemment utilisée dans le NYT):

Un autre problème soulevé dans les commentaires est une certaine incrédulité que cette question est un défi de codage . Ce n'est peut-être pas immédiatement clair, mais il est difficile de trouver une seule réponse valable à ce défi . Trouver la référence ci-dessus impliquait plusieurs programmes de recherche spécialement conçus qui n'étaient pas garantis pour trouver une réponse. Je ne connais même pas personnellement un moyen général de résoudre une grille arbitraire, si vous voulez la réponse dans un délai raisonnable. Les programmes de construction de mots croisés existants peuvent aider, mais je suppose (peut-être à tort) qu'ils ne font pas réellement une recherche complète des possibilités. (J'ai utilisé un tel programme pour les trois grilles côte à côte ci-dessus; cela a fonctionné parce que cette grille particulière permet de nombreuses solutions.)

code-challenge optimization crossword A. Rex
la source

Meta post lié à ce type général de questions: codegolf.meta.stackexchange.com/questions/18117/…

A. Rex le

1. Supprimez l'option esthétique ("

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.

") - de manière similaire à éviter les bonus dans le golf de code, je préfère qu'un défi de code soit une seule chose. Cela signifie que toutes les réponses peuvent être comparées de la même manière. Cela le rend également clairement objectif, ce qui contribuera à la réouverture des votes.

trichoplax le

2. Choisissez une seule liste de mots et insistez dessus pour toutes les réponses. Le tldr mentionne une liste de mots faisant autorité, mais la discussion préalable peut amener les gens à penser qu'ils peuvent choisir n'importe lequel de ceux mentionnés. Cela peut aider à garder les exigences strictes près du haut du message et à préciser que d'autres détails ne font pas partie des spécifications du défi. Idéalement, omettez tout ce qui est superflu pour que le message soit court et sans ambiguïté.

trichoplax

3. Faites de l'inclusion du code utilisé pour trouver la solution une exigence pour une réponse valide.

trichoplax

C'est le genre de défi qui pourrait bénéficier d'un salon de discussion pour que les gens puissent discuter des approches. Si vous configurez une salle de discussion et que vous y créez un lien depuis la fin de la spécification, vous pouvez y publier la discussion en tant que messages initiaux, et le mentionner dans le défi pour les personnes qui veulent en savoir plus.

trichoplax le

180 carrés blancs

Ma stratégie consistait simplement à trouver un rectangle plus petit sans carrés noirs, de sorte qu'il puisse être rempli de manière unique. Tous les 2×krectangles ont plusieurs solutions. Pour les 3×krectangles, il existe plusieurs solutions pour kentre 3 et 14, mais il y a exactement une solution pour k=15.

Je place ensuite 4 de ces rectangles dans la grille. Cela signifie que chaque mot apparaît 4 fois dans la solution, ce qui est généralement mal vu dans la construction des mots croisés, mais OK pour ce défi. D'un autre côté, cette solution a à la fois une symétrie gauche / droite et haut / bas!

Grille lisible par ordinateur:

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

Voici le code R que j'ai utilisé pour trouver toutes les solutions pour une taille de grille donnée. La boucle sur tous les triplets de mots de 15 lettres est trop lente. Au lieu de cela, j'essaie de remplir des rectangles en

définition des deux premières colonnes (deux mots de 3 lettres)
puis en parcourant tous les mots de 15 lettres en commençant par les deux premières lettres qui sont maintenant réglées.
pour chaque choix possible des mots de 15 lettres, je vérifie ensuite si tous les mots de 3 lettres générés sont dans le dictionnaire.

Par exemple, pour la solution finale, le premier code mis en HOPet EVOpuis terminé en HETERNORMATIVE, OVEROPINIONATEDet POSSESSEDNESSES, et enfin vérifié tous les mots de 3 lettres ( HOP, EVO, TES, ERS, ROE, OPS, NIS, ONE, RID, MON, ANE, TAS, ITS, VEE, EDS).

Code R

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)
}

Appelé comme f3(15). J'ai pris quelques heures sur mon ordinateur personnel.

Robin Ryder
la source

@downvoter Pourriez-vous commenter?

Robin Ryder

Ma réponse a également été rejetée. 🤷

A. Rex

Créez des mots croisés résolument uniques… sans indices