¿Te imaginas resolver el crucigrama del New York Times sin ninguna pista? Quizás no con toda la creatividad y las nuevas palabras y frases que aparecen en los crucigramas modernos, pero con una lista de palabras fija hay algo de esperanza. En este desafío, crea una cuadrícula de crucigramas en la que esto es teóricamente posible.

El reto

Maximice el número de cuadrados blancos en una cuadrícula de crucigrama de 15x15 sombreada en blanco y negro, de modo que los cuadrados blancos se puedan llenar de letras de manera única para que cada palabra entrecruzada y hacia abajo aparezca en la lista internacional de palabras Scrabble.

Aclaraciones de construcción de rejilla

En los periódicos de EE. UU., Las cuadrículas de crucigramas generalmente se construyen de manera que cada letra se "verifica", lo que significa que es parte de una palabra "cruzada" y una palabra "abajo". En el Reino Unido y en otros lugares (especialmente en crucigramas crípticos ), este no es necesariamente el caso: si una palabra "cruzada" o "abajo" sería solo una letra, no es necesario que sea una palabra real (como "A" o "I" "). Para este desafío, siga las reglas más relajadas: las palabras de una letra no necesitan aparecer en la lista de palabras.

Hay varias otras tradiciones (en los EE. UU. Y en otros lugares), ninguna de las cuales debe seguirse en este desafío. Por ejemplo, las palabras pueden tener solo dos letras, las palabras pueden repetirse y la cuadrícula no necesita tener simetría (rotacional).

¿Es esto posible?

¡Si! Se puede escribir una secuencia de comandos breve para verificar que la solución única para la siguiente cuadrícula en blanco a la izquierda es la cuadrícula rellena a la derecha:

Se puede mostrar la cuadrícula llena en un formato legible por computadora de la siguiente manera:

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

Tu solución

La cuadrícula de arriba tiene 56 cuadrados blancos del total de 225 cuadrados en la cuadrícula de 15x15. Esto sirve como línea de base para este desafío. Las cuadrículas con menos cuadrados blancos también pueden ser interesantes por razones distintas a su puntaje, por ejemplo, si satisfacen algunas de las tradiciones estéticas mencionadas anteriormente.

Envíe su solución en el mismo formato que la línea de base legible por computadora anterior. Incluya código que verifique que hay una solución única para su grilla.

Se aprecian fragmentos de código interesantes (por ejemplo, para buscar el espacio de posibilidades) y una discusión sobre cómo encontró su cuadrícula.

La lista de palabras

La lista internacional de palabras Scrabble se conocía anteriormente como SOWPODS y ahora se llama Collins Scrabble Words (CSW). Se usa en la mayoría de los países (excepto en particular en los EE. UU.). Preferimos usar esta lista porque incluye la ortografía británica y generalmente tiene muchas más palabras que la lista de palabras estadounidense. Hay varias ediciones de esta lista que difieren ligeramente. Puede encontrar diferentes versiones de esta lista enlazadas desde Wikipedia , en Github , en el Corpus del lenguaje natural de Peter Norvig y en otros lugares, a menudo llamados "SOWPODS".

Este desafío es altamente sensible a la naturaleza amplia de la elección de la lista de palabras, pero no tanto a detalles más pequeños. Por ejemplo, el ejemplo de referencia anterior funciona con cualquier edición de CSW, pero CHno es una palabra en la lista de palabras de American Scrabble. En caso de discrepancia, preferimos usar CSW19, la edición más reciente de CSW. (Si usamos esta lista, que se lanzó este año, podemos esperar que las respuestas a este desafío sigan siendo válidas por más tiempo). Puede consultar esta lista de manera interactiva en el sitio oficial de buscador de palabras Scrabble o descargarla (así como la edición anterior, CSW15) desde el intercambio de pila de juegos de tablero y cartas o el r / scrabble de Reddit .

Tldr : la lista de palabras autorizadas para este desafío está disponible como un archivo de texto sin formato (279,496 palabras, una por línea) en el intercambio de pila de juegos de mesa y cartas .

Más discusión

Una cuestión planteada en una respuesta y comentario tempranos es por qué los crucigramas existentes (por ejemplo, en el NYT) no responden esta pregunta. Específicamente, el registro de la menor cantidad de cuadrados negros (y, por lo tanto, la mayor cantidad de cuadrados blancos) para un crucigrama publicado en el NYT ya es el registro más famoso en crucigramas. ¿Por qué no podemos usar la cuadrícula de registros ? Hay algunos problemas:

• Muchas de las respuestas en los crucigramas de NYT no aparecen en nuestra lista de palabras. Por ejemplo, la cuadrícula de registros incluye PEPCID(un nombre de marca), APASSAGETOINDIA(un nombre propio de cuatro palabras para una película y novela, escrito sin espacios) y STE(una abreviatura de "Sainte"). Parece que la cuadrícula de registros no se puede resolver con palabras Scrabble.

• Simplemente expandir la lista de palabras para incluir más palabras no necesariamente ayuda con este desafío: incluso si todas las palabras en la cuadrícula de registros aparecieran en nuestra lista de palabras, la solución no sería única sin las pistas. A menudo es posible alterar algunas letras al final de las respuestas manteniendo todo como una palabra. (Por ejemplo, la letra de la esquina inferior derecha se puede cambiar de a Da an R.) De hecho, esto es parte del proceso de construcción (humano) al escribir un crucigrama, tratando de obtener palabras "mejores".

  La razón por la cual los crucigramas ordinarios (generalmente) tienen una solución única es que las pistas ayudan a reducir las respuestas correctas. Si simplemente intenta llenar la cuadrícula con palabras sin usar pistas, es probable que no haya posibilidades o muchas posibilidades. Aquí hay un ejemplo de tres rellenos diferentes (¡usando la lista de palabras para este desafío!) Para la misma cuadrícula (una que se usa con relativa frecuencia en el NYT):

• Otra cuestión planteada en los comentarios es cierta incredulidad de que esta pregunta sea un desafío de codificación . Quizás no esté claro de inmediato, pero es difícil incluso encontrar una respuesta válida única para este desafío . Encontrar la línea de base anterior involucraba múltiples programas de búsqueda especialmente diseñados que no garantizaban encontrar una respuesta. Personalmente, ni siquiera conozco una forma general de resolver una grilla arbitraria, si quieres la respuesta en un tiempo razonable. Los programas de construcción de crucigramas existentes pueden ayudar, pero supongo (tal vez incorrectamente) que en realidad no hacen una búsqueda completa de las posibilidades. (Usé un programa de este tipo para las tres cuadrículas de lado a lado anteriores; esto funcionó porque esa cuadrícula particular permite muchas soluciones).

180 cuadrados blancos

Mi estrategia era simplemente encontrar un rectángulo más pequeño sin cuadrados negros, de modo que pueda rellenarse de manera única. Todos los 2×krectángulos tienen múltiples soluciones. Para los 3×krectángulos, hay múltiples soluciones para kentre 3 y 14, pero hay exactamente una solución para k=15.

Luego ajusto 4 de esos rectángulos en la cuadrícula. Esto significa que cada palabra aparece 4 veces en la solución, lo que generalmente está mal visto en la construcción de crucigramas, pero está bien para este desafío. Por otro lado, ¡esta solución tiene simetría izquierda / derecha y arriba / abajo!

Cuadrícula legible por computadora:

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

Aquí está el código R que utilicé para encontrar todas las soluciones para un tamaño de cuadrícula determinado. Recorrer todos los triples de palabras de 15 letras es demasiado lento. En cambio, trato de completar los rectángulos por

• establecer las dos primeras columnas (dos palabras de 3 letras)
• luego recorriendo todas las palabras de 15 letras que comienzan con las dos primeras letras que ahora están resueltas.
• para cada posible elección de las palabras de 15 letras, luego verifico si todas las palabras de 3 letras generadas están en el diccionario.

Por ejemplo, para la solución eventual, el código de poner primero en HOPy EVO, a continuación, completado en HETERNORMATIVE, OVEROPINIONATEDy POSSESSEDNESSES, y finalmente verifica todas las palabras de 3 letras ( HOP, EVO, TES, ERS, ROE, OPS, NIS, ONE, RID, MON, ANE, TAS, ITS, VEE, EDS).

Código 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)
}

Llamado como f3(15). Tomé algunas horas en mi computadora personal.

182 cuadrados blancos

Inspirado por la respuesta de Robin Ryder , traté de meter un par de cuadrados blancos más. Creo que esta solución es única, y pronto publicaré el código de verificación en consecuencia.

Cuadrícula legible por computadora:

HETERONORMATIVE
OVEROPINIONATED
POSSESSEDNESSES
B##############
INCOMMUNICATIVE
NEUROANATOMICAL
DETERMINATENESS
###############
HETERONORMATIVE
OVEROPINIONATED
POSSESSEDNESSES
B##############
INCOMMUNICATIVE
NEUROANATOMICAL
DETERMINATENESS