En Habré había algunos artículos sobre la generación de crucigramas. En uno de ellos,
"El crucigrama más complejo compilado por una computadora", se decía sobre un crucigrama muy complejo compuesto por una computadora, que "tenía que ayudar un poco" manualmente. El segundo artículo,
"Algoritmo de generación de crucigramas", habla sobre el algoritmo creado por el autor para componer crucigramas, y señala que este "crucigrama más difícil" ha permanecido sin conquistar y dijo que "¡tal vez este pico no conquistado inspirará a alguien a tomar otra tormenta!" Bueno, puedes aceptar el desafío. Lo que salió de eso, mira debajo del corte.
Al principio daré este crucigrama más complicado:
Lo primero que necesita encontrar es una lista de palabras que se utilizan para compilar este crucigrama. Como tal, se tomaron dos archivos de los artículos anteriores: un archivo con palabras en ruso y otro con inglés. Luego fue necesario resolver la pregunta principal: qué algoritmo usar para compilar este crucigrama. En realidad, este crucigrama no es "complicado" por el número de palabras, sino por el número de sus intersecciones. Está claro que el ataque de fuerza bruta no es adecuado aquí, ya que tomaría demasiado tiempo clasificar todas las opciones. En el artículo mencionado anteriormente, se consideró que muchas heurísticas aceleraron el proceso de búsqueda, sin embargo, este crucigrama nunca se compiló ni en la versión rusa ni en la inglesa. Puede continuar con otras heurísticas para acelerar la solución, pero la mayoría de ellas ya se han inventado e implementado en solucionadores SAT. Por lo tanto, puede traducir la tarea a un formulario que sea comprensible para los solucionadores de SAT y usar uno de ellos.
¿Qué es el solucionador SAT y qué información espera en la entrada que consideré en el artículo
"Resolver el problema de mosaico con la ayuda del solucionador SAT utilizando el ejemplo de pentamino" . En el caso de generar un crucigrama, se necesita un enfoque ligeramente diferente para formular el problema en forma conjuntivamente normal, que ahora esbozaré.
Lo primero que debe hacer es ordenar todas las palabras de la lista en grupos. Cada grupo contendrá palabras de la misma longitud. Obviamente, para cada palabra en la cuadrícula de crucigramas, puede seleccionar una palabra del grupo con la longitud correspondiente. Asociamos cada palabra del grupo que se puede escribir en una sola palabra de la cuadrícula con una variable booleana. Esta variable será verdadera si la palabra dada del grupo está escrita en esta palabra desde la cuadrícula y falsa en caso contrario.
Ahora elaboremos una fórmula que describa nuestro problema, es decir, en realidad impondremos restricciones a nuestras variables. Encuentra todas las intersecciones de palabras verticalmente con palabras horizontalmente. Para cada intersección, determinamos qué pares de palabras se combinan entre sí y cuáles no. Sin embargo, aquí surge un problema, ya que el número de tales pares puede exceder el millón para una intersección. Por lo tanto, utilizaremos un enfoque diferente. Ordenamos las palabras en el grupo que corresponde a la palabra horizontalmente por letra, que se encuentra en la intersección de estas dos palabras. Haz lo mismo para la palabra verticalmente. Aparentemente, las palabras coincidentes tendrán la misma letra en la intersección. Introducimos una variable adicional para cada letra que aparece en al menos una palabra horizontal y verticalmente. Ahora, la condición de que las dos palabras se combinen entre sí es que al menos una de esas variables sea verdadera. Por lo tanto, para cada intersección, se agregará una cláusula que consiste en variables correspondientes a las letras. Ahora necesita asociar las variables correspondientes a una letra en particular con las palabras que contienen esta letra en la posición de la intersección de las palabras. Esto se realiza mediante un conjunto de cláusulas que garantizan que las dos variables booleanas tendrán el mismo valor. Y finalmente, debe asegurarse de que no haya palabras idénticas en el crucigrama. Para hacer esto, para cada palabra de la base de datos agregamos cláusulas de la forma (no x_i V no x_j), donde x_i es la variable correspondiente a su instancia en una palabra de la cuadrícula de crucigramas, y x_j es la variable correspondiente a su instancia en otra palabra de la cuadrícula de crucigramas.
La generación de este "crucigrama más complicado" usando palabras rusas lleva varios minutos en un Intel 2600K 3.5 GHz con 16 gigabytes de memoria. Crear un crucigrama usando palabras en inglés tomó unos veinte minutos.
Después de eso, probé otros crucigramas. Por ejemplo, logré componer un crucigrama de palabras en inglés y ruso en forma de un cuadrado de 6 por 6, donde todas las palabras se cruzan.
A continuación, doy los crucigramas resultantes. Los que lo deseen pueden resolverlos.
Opción con palabras rusas:1 avión horizontal de cámara lenta con una nariz abultada
6 Instrumentos musicales de cuerda japoneses horizontales
10 Horizontal En la mitología escandinava, un gigante que emergió del caos prematuro del abismo mundial
14 Exilio horizontal del género
15 minerales horizontales
16 horizontal poeta checo (20 c.)
17 Isla horizontal en el golfo de Guinea (Guinea Ecuatorial)
18 Boca horizontal, labios (anticuados)
19 Resentimiento horizontal, ira
20 Horizontal Solo un partido político presente
23 Horizontal el río más grande de Irlanda
24 Ropa de clérigo horizontal
25 Río Horizontal en Angola y Zaire, afluente del río Kwango
27 Marca horizontal del autobús húngaro
32 Ciudad horizontal y puerto en RPDC
35 Horizontal Suegra o suegra
37 planta de solanáceas horizontales
38 Horizontal Uno que se dedica a cardar lana
41 Nombre femenino horizontal (griego bueno, amable)
42 satélite artificial horizontal canadiense
43 Personaje horizontal de la ópera de Weber '' Free Shooter ''
44 Ciudad horizontal en Eslovaquia
46 Gasto horizontal
48 peces de cultivo horizontal de la familia de las carpas
50 Horizontal En la mitología japonesa, la deidad de muchas orejas de arroz
54 Fósforo cristalino inorgánico horizontal
59 Profeta horizontal iraní, fundador del maniqueísmo (3 c.)
60 hogares campesinos horizontales en las islas de las Antillas
61 Raza de perros de pastor horizontal (similar a un zorro)
62 Horizontal (trans.) Estúpido necio terco
63 Ciudad horizontal en la región de Orenburg en el rio Ural
64 Horizontal En la mitología griega, un cazador gigante asesinado por Artemisa
65 horizontal cantante y poeta chileno
66 Horizontal El personaje del teatro folklórico indio, la imagen de un playman arruinado, un parásito con un rico mecenas
67 chechenos horizontales e ingush madre tierra
1 Sobrenombre vertical de uno de los líderes del levantamiento popular de 1413 en París
2 Sentimiento vertical insatisfecho
3 paleontólogo alemán vertical (1800-1862)
4 Vertical La conquista de los territorios capturados por los moros por la población indígena de la Península Ibérica
5 maestro de guitarra rusa vertical
6 Líder militar vertical sueco y ruso, general, asociado de Pedro I (1667-1717)
7 Músico vertical tocando un instrumento musical
8 Altavoz vertical, hombre elocuente
9 Cresta vertical en Japón, isla de Honshu
10 instrumentos musicales de percusión coreana vertical, tambor octogonal
11 Conductor vertical letón (1917-1967)
12 Cordialidad vertical, comadreja
13 Vertical En la mitología eslava, el espíritu, la encarnación de la muerte.
21 género de animación vertical que se originó en Japón
22 Cátodo de lámpara calefactora de hilo vertical
26 Lago vertical en la región de Arkhangelsk
28 Río vertical en España
29 Vertical Pequeño bosque de árboles caducifolios
30 Artículo raro vertical
31 Windmaster belga vertical, inventor del saxofón
32 marco vertical pequeño
33 vertical negro
34 Vertical Medida anterior de peso farmacéutico = 62.21 mg
36 Provincia vertical en Arabia Saudita
39 Grasa vertical antifricción
40 Decoración escultórica vertical de capiteles, cornisas, etc. en forma de tallos y hojas estilizados de dicha planta
45 Vertical escritor ruso, poeta, dramaturgo, guionista de las películas de A. Sokurov ('' Moloch '', '' Taurus '')
47 Caucho de polisulfuro vertical, un tipo de caucho sintético
49 Patólogo Vertical Inglés (Premio Nobel 1945)
51 Vertical En la mitología musulmana, un genio con poder especial
52 grito de ganso vertical
53 Nombre femenino vertical (nombre griego de la diosa de la vida pacífica; paz)
54 Gran maestro de ajedrez vertical
55 Vertical Grupo de la humanidad formado históricamente, unido por un origen común
56 Híbrido vertical al cruzar un camello de una sola joroba (Dromedar) con una de dos jorobas (Bactriana), Nar
57 Valor mecánico vertical que causa aceleración
58 Escritor japonés vertical (1909-1989, `` Notas del prisionero '', `` Luces en el campo '', `` Batalla en Leyte '')
Opción con palabras en inglés:1 Horizontal Un lugar que atrae a muchos visitantes.
6 Horizontal Cualquiera de una serie de peces de la familia Carangidae
10 Horizontal Una colección de hechos de los cuales se pueden sacar conclusiones
14 Nintu horizontal)
15 Cubierta horizontal del cuerpo de un animal vivo
16 Horizontal Un dolor sordo persistente (generalmente moderadamente intenso)
17 Horizontal Respuesta de los tejidos corporales a lesiones o irritaciones.
18 Género tipo horizontal de los patos de agua dulce Anatidae
19 Horizontal La dinastía que gobernó gran parte de Manchuria y el noreste de China desde 947 hasta 1125
20 Horizontal Un compuesto cristalino blanco utilizado como analgésico y también como antipirético.
23 Horizontal Una ciudad en el centro de Tanzania
24 Dios horizontal de la muerte
25 Masa en forma horizontal y seca hecha de harina y agua y a veces huevo
27 Horizontal Un miembro del pueblo siouan de Virginia y Carolina del Norte
32 Horizontal Un fuerte deseo inquieto
35 Prelado horizontal sudafricano y líder de la lucha antiapartheid (nacido en 1931)
37 Horizontal Un documento comercial utilizado para solicitar a alguien que proporcione algo a cambio del pago
38 mosquitos horizontales
41 Horizontal Una ciudad antigua en el norte de Portugal
42 Horizontal Una cabaña esquimal
43 Mecanismo de rotación horizontal en forma de rueca universalmente montada que ofrece resistencia a los giros en cualquier dirección
44 Horizontal La capital de Bahrein
46 Horizontal El acto de dar un ligero tinte al cabello.
48 Tipo horizontal género de los Majidae
50 Horizontal Cualquiera de varias plantas del género Camassia
54 Perniles voladores horizontales
59 Horizontal Todo el cultivo se puede cosechar a la vez
60 Horizontal Una ley aprobada por el Congreso de los EE. UU. Para evitar que los empleados se lesionen o contraigan enfermedades en el curso de su empleo
61 Horizontal Un bloque pesado de hierro o acero sobre el cual los metales calientes se forman martillando
62 estadista inglés horizontal que se opuso al divorcio de Enrique VIII de Catalina de Aragón y fue encarcelado y decapitado
63 Horizontal Un hombre que corteja a una mujer
64 jugador de béisbol horizontal de Estados Unidos
65 Horizontal Una mirada secreta
66 Horizontal Pequeña gaviota delgada que tiene alas estrechas y una cola bifurcada
67 Horizontal Conocido por uvas y aceitunas y aceite de oliva.
1 Líder revolucionario francés vertical (nacido en Suiza) que lideró el derrocamiento de los girondinos y fue apuñalado en su baño por Charlotte Corday (1743-1793).
2 hierbas anuales verticales a perennes de la región mediterránea
3 Vertical Arbusto tropical del sudeste asiático enredadera con frutos picantes similares a bayas
4 Ani vertical
5 Vertical La primera luz del día
6 Título vertical para el ex monarca hereditario de Irán
7 Vertical Un fotógrafo que opera una cámara de cine
8 Vertical Una ciudad en el sur de Turquía en el río Seyhan
9 Vertical Una región árida con poca o ninguna vegetación.
10 Pintor español surrealista vertical (1904-1989)
11 Vertical Cualquiera de varios compuestos solubles en agua que tengan un sabor agrio y sean capaces de tornar rojo tornasol y reaccionar con una base para formar una sal.
12 Vertical Un nativo o habitante de Tailandia
13 Vertical (en el gnosticismo) un poder divino o naturaleza que emana del Ser Supremo y desempeña varios roles en la operación del universo
21 Vertical Un volcán activo en el sureste de Colombia en los Andes.
22 Vertical Un leptón de gran masa
26 Vertical Un miembro de los indios sudamericanos que viven en Brasil y Paraguay
28 Vertical El nervio sensorial principal de la cara y el nervio motor para los músculos de la masticación.
29 Vertical Un torbellino o torbellino en miniatura resultante cuando la corriente de un fluido se duplica sobre sí misma
30 Artista británico vertical y escritor de versos sin sentido (1812-1888)
31 Galleta vertical de chocolate con relleno de crema blanca
32 Vertical Un misil balístico que es capaz de viajar de un continente a otro.
33 Vertical Un lenguaje chadic de tres tonos
34 Vertical Una unidad de capacidad utilizada para medir arenque fresco
36 Vertical Grande Gran híbrido jugoso entre mandarina y pomelo que tiene una piel gruesa y arrugada
39 Tejido de lana o lana y algodón de tejido liso vertical (a menudo esmaltado), utilizado especialmente anteriormente para forros, prendas y cortinas
40 Vertical Una unidad de peso de boticario igual a 480 granos o una doceava parte de una libra
45 Vertical Una ciudad en el centro de Bélgica
47 Vertical Un chal largo de colores brillantes
49 Vertical Un libro en el Antiguo Testamento que describe cómo Josué llevó a los israelitas a Canaán (la tierra prometida) después de la muerte de Moisés.
51 Vertical Medicamento antiinflamatorio no esteroideo (nombres comerciales Advil y Motrin y Nuprin) utilizado para aliviar el dolor de la artritis y como analgésico y antipirético.
52 Antílope vertical parecido a una cabra de Eurasia central que tiene una nariz rechoncha como una trompa
53 Tenista vertical de los Estados Unidos (nacido en Yugoslavia en 1973)
54 Vertical Una ligera humedad
55 plantas suculentas verticales que tienen rosetas de hojas generalmente con fibra como el cáñamo y espigas de flores llamativas
56 Actividad vertical involucrada en mantener algo en buen estado de funcionamiento
57 Vertical (sudafricano) un viaje en carreta de bueyes (especialmente una migración organizada por un grupo de colonos)
58 Vertical Un lago de montaña (especialmente uno formado por glaciares)
Crucigrama 6 contra 6 en ruso:1 piloto de prueba soviético horizontal, héroe de la Unión Soviética, uno de los participantes del vuelo sin escalas Moscú - Polo Norte - Vancouver
2 orejas horizontales
3 adivinador horizontal
4 Ciudad horizontal en Italia en la isla de Sicilia
5 Hilados texturizados ondulados horizontales obtenidos por corrugación en cámaras calentadas
6 Cineasta francés horizontal, guionista ('' Bad Blood '', '' Boyfriend Meets Girl '')
7 Moneda de plata vertical del Gran Ducado de Lituania del siglo XVI.
8 Bioquímico estadounidense vertical, sintetizó por primera vez el gen tRNA (Premio Nobel 1968)
9 Ciudad vertical en la Federación de Rusia, Osetia del Norte, en el río Ardon, en el camino militar de Osetia
10 Nicho horizontal vertical en la pared de la cámara funeraria, donde el difunto fue puesto y amurallado o colgado con un dosel
11 Vertical El muslo de la carcasa
12 Ciudad vertical en el sureste de Francia
Crucigrama 6 contra 6 en inglés:1 Horizontal Un miembro del pueblo indio del norte de California y el sur de Oregón
2 Horizontal Un miembro de una de las cuatro divisiones de los griegos prehistóricos.
3 Horizontal puede volverse adictivo
4 dios griego horizontal de la luz
5 Horizontal Pequeños artículos personales o de ropa o de costura
6 Árbol de madera valioso horizontal de Nueva Zelanda que produce madera dura rojiza utilizada para muebles y puentes y muelles
7 Vertical Una línea recta que corta una curva en dos o más puntos.
8 Vertical Cualquiera de varias aves con cresta del Viejo Mundo con un pico delgado y curvado hacia abajo
9 novelista vertical estadounidense conocido por los libros infantiles (1832-1888)
10 pájaros azules verticales de América del Norte
11 Vertical Una persona cuya ocupación es hacer y alterar prendas
12 Género tipo vertical de las Annonaceae
Conclusión
El uso del solucionador SAT aumenta la complejidad de los crucigramas que se pueden generar. Al igual que en el artículo anterior, quiero preguntarle al siguiente pico sin oposición: hacer un crucigrama de palabras rusas o inglesas en forma de un cuadrado de 7 por 7. ¿Quién aceptará el desafío?