Sur Habré, il y avait quelques articles sur la génération de mots croisés. Dans l'un d'eux,
«Les mots croisés les plus complexes compilés par un ordinateur», il était question d'un mot croisé très complexe composé par un ordinateur, qui «devait aider un peu» manuellement. Le deuxième article,
«Crossword Puzzle Generation Algorithm», parle de l'algorithme créé par l'auteur pour composer des mots croisés, et note que ce «puzzle de mots croisés le plus difficile» est resté invaincu et a déclaré que «peut-être ce pic non conquis inspirera quelqu'un à prendre une autre tempête!» Eh bien, vous pouvez accepter le défi. Ce qui en est sorti, regardez sous la coupe.
Au début, je donnerai ce puzzle de mots croisés le plus compliqué:
La première chose que vous devez trouver est une liste de mots qui sont utilisés pour compiler ce puzzle de mots croisés. Comme une telle liste a été prise deux fichiers des articles ci-dessus - un fichier avec des mots russes, un fichier avec l'anglais. Il a ensuite fallu résoudre la question principale - quel algorithme utiliser pour compiler ce puzzle de mots croisés. En fait, ce puzzle de mots croisés n'est pas «compliqué» par le nombre de mots, mais par le nombre de leurs intersections. Il est clair que l'attaque par force brute ne convient pas ici, car il faudrait trop de temps pour trier toutes les options. Dans l'article susmentionné, de nombreuses heuristiques ont été considérées pour accélérer le processus de recherche, cependant, ce puzzle de mots croisés n'a jamais été compilé dans la version russe ou anglaise. Vous pouvez continuer à proposer d'autres heuristiques pour accélérer la solution, mais la plupart d'entre elles ont déjà été inventées et implémentées dans les solveurs SAT. Par conséquent, vous pouvez traduire la tâche dans un formulaire compréhensible pour les solveurs SAT et utiliser l'un d'eux.
Qu'est-ce que le solveur SAT et quelles informations attend-il à l'entrée, j'ai considéré dans l'article
«Résoudre le problème de mosaïque à l'aide du solveur SAT en utilisant l'exemple pentamino» . Dans le cas de la génération d'un jeu de mots croisés, une approche légèrement différente est nécessaire pour formuler le problème sous une forme normale conjonctive, que je vais maintenant décrire.
La première chose à faire est de trier tous les mots de la liste en groupes. Chaque groupe contiendra des mots de même longueur. Évidemment, pour chaque mot de la grille de mots croisés, vous pouvez sélectionner un mot du groupe avec la longueur correspondante. Nous associons chaque mot du groupe qui peut être écrit en un seul mot de la grille à une variable booléenne. Cette variable sera vraie si le mot donné du groupe est écrit dans ce mot de la grille et faux sinon.
Établissons maintenant une formule décrivant notre problème, c'est-à-dire que nous imposerons des restrictions sur nos variables. Trouvez toutes les intersections de mots verticalement avec des mots horizontalement. Pour chaque intersection, nous déterminons quelles paires de mots sont combinées entre elles et lesquelles ne le sont pas. Cependant, un problème se pose ici, car le nombre de ces paires peut dépasser un million pour une intersection. Par conséquent, nous utiliserons une approche différente. Nous trions les mots dans le groupe qui correspond au mot horizontalement par lettre, qui se trouve à l'intersection de ces deux mots. Faites de même pour le mot verticalement. Apparemment, les mots correspondants auront la même lettre à l'intersection. Nous introduisons une variable supplémentaire pour chaque lettre qui apparaît dans au moins un mot horizontalement et verticalement. Maintenant, la condition que les deux mots sont combinés l'un avec l'autre est qu'au moins une de ces variables est vraie. Ainsi, pour chaque intersection, une clause sera ajoutée constituée de variables correspondant aux lettres. Vous devez maintenant associer les variables correspondant à une lettre particulière avec les mots contenant cette lettre à la position de l'intersection des mots. Cela se fait par un ensemble de clauses qui garantissent que les deux variables booléennes auront la même valeur. Et enfin, vous devez vous assurer qu'il n'y a pas de mots identiques dans le puzzle de mots croisés. Pour ce faire, pour chaque mot de la base de données, nous ajoutons des clauses du formulaire (pas x_i V pas x_j), où x_i est la variable correspondant à son instance dans un mot de la grille de mots croisés, et x_j est la variable correspondant à son instance dans un autre mot de la grille de mots croisés.
La génération de ce «jeu de mots croisés le plus compliqué» à l'aide de mots russes prend plusieurs minutes sur un Intel 2600K 3,5 GHz avec 16 gigaoctets de mémoire. La création d'un puzzle de mots croisés en utilisant des mots anglais a pris environ vingt minutes.
Après cela, j'ai essayé d'autres puzzles de mots croisés. Par exemple, j'ai réussi à composer un mot croisé de mots anglais et russes sous la forme d'un carré 6 par 6, où tous les mots se croisent.
Ensuite, je donne les mots croisés résultants. Ceux qui le souhaitent peuvent les résoudre.
Option avec des mots russes:1 avion au ralenti horizontal avec un nez bombé
6 Instrument de musique à cordes japonais horizontal
10 Horizontal Dans la mythologie scandinave, un géant issu du chaos prématuré des abysses du monde
14 Exil horizontal du genre
15 minéraux horizontaux
16 Poète tchèque horizontal (20 ch.)
17 Île horizontale dans le golfe de Guinée (Guinée équatoriale)
18 Bouche horizontale, lèvres (obsolètes)
19 ressentiment horizontal, rage
20 Horizontal Un seul parti politique présent
23 Le plus grand fleuve horizontal d'Irlande
24 Vêtements de prêtre horizontaux
25 Rivière horizontale en Angola et au Zaïre, affluent gauche de la rivière Kwango
27 Marque horizontale du bus hongrois
32 Ville et port horizontaux en RPDC
35 Belle-mère ou belle-mère horizontale
37 Solanacées horizontales
38 Horizontal Celui qui s'engage dans le cardage de la laine
41 Nom féminin horizontal (bon grec, gentil)
42 Satellite artificiel canadien horizontal
43 Personnage horizontal de l'opéra de Weber `` Free Shooter ''
44 Ville horizontale en Slovaquie
46 Dépenses horizontales
48 Poissons d'élevage horizontaux de la famille des carpes
50 Horizontal Dans la mythologie japonaise, la divinité de beaucoup d'épis de riz
54 Phosphore cristallin inorganique horizontal
59 Prophète iranien horizontal, fondateur du manichéisme (3 c.)
60 maisons paysannes horizontales dans les îles des Antilles
61 Race de chiens de berger horizontal (semblable à un renard)
62 Horizontal (trans.) Idiot stupide et têtu
63 Ville horizontale dans la région d'Orenbourg sur l'Oural
64 Horizontal Dans la mythologie grecque, un chasseur géant tué par Artemis
65 poète et chanteur chilien horizontal
66 Horizontal Le personnage du théâtre folklorique indien, l'image d'un playman en ruine, un parasite avec un riche mécène
67 Tchétchènes horizontales et terre mère ingouche
1 Surnom vertical de l'un des chefs du soulèvement populaire de 1413 à Paris
2 Sentiment vertical insatisfait
3 Paléontologue allemand vertical (1800-1862)
4 Vertical La conquête des territoires capturés par les Maures par la population indigène de la péninsule ibérique
5 Maître de guitare russe vertical
6 Chef militaire vertical suédois et russe, général, associé de Pierre I (1667-1717)
7 Musicien vertical jouant un instrument de musique
8 Haut-parleur vertical, Eloquent Man
9 Vertical Ridge au Japon, île Honshu
10 Instrument de musique à percussion coréen vertical, tambour octogonal
11 conducteur vertical letton (1917-1967)
12 Cordialité verticale, belette
13 Vertical Dans la mythologie slave, l'esprit, l'incarnation de la mort
21 genre d'animation verticale originaire du Japon
22 Cathode de lampe chauffante à fil vertical
26 Lac vertical dans la région d'Arkhangelsk
28 Rivière verticale en Espagne
29 Vertical Petite forêt d'arbres à feuilles caduques
30 objet rare vertical
31 Windmaster belge vertical, inventeur du saxophone
32 Petit cadre vertical
33 Vertical Black
34 Ancienne mesure verticale du poids pharmaceutique = 62,21 mg
36 Province verticale d'Arabie saoudite
39 Graisse antifriction verticale
40 Décoration sculpturale verticale de chapiteaux, corniches, etc. sous la forme de tiges et de feuilles stylisées d'une telle plante
45 Vertical écrivain russe, poète, dramaturge, scénariste pour les films de A. Sokurov ('' Moloch '', '' Taurus '')
47 Caoutchouc polysulfure vertical, un type de caoutchouc synthétique
49 Pathologiste anglais vertical (prix Nobel 1945)
51 Vertical Dans la mythologie musulmane, un génie au pouvoir spécial
52 Cri vertical d'oie
53 Nom féminin vertical (nom grec de la déesse de la vie paisible; paix)
54 Grand maître d'échecs vertical
55 Groupe vertical formé d'humains, unis par une origine commune
56 Vertical Hybrid en croisant un chameau à une seule bosse (Dromedar) avec un à deux bosses (Bactriane), Nar
57 Valeur mécanique verticale provoquant une accélération
58 Écrivain japonais vertical (1909-1989, `` Notes du prisonnier '', `` Lumières sur le terrain '', `` Bataille sur Leyte '')
Option avec mots anglais:1 Horizontal Un lieu qui attire de nombreux visiteurs
6 Horizontal N'importe lequel d'un certain nombre de poissons de la famille des Carangidae
10 Horizontal Un ensemble de faits à partir desquels des conclusions peuvent être tirées
14 Nintu horizontal)
15 Couverture horizontale du corps d'un animal vivant
16 Horizontal Douleur sourde persistante (généralement modérément intense)
17 Horizontal Une réponse des tissus corporels aux blessures ou à l'irritation
18 Genre de type horizontal des canards d'eau douce Anatidae
19 Horizontal La dynastie qui a gouverné une grande partie de la Mandchourie et du nord-est de la Chine de 947 à 1125
20 Horizontal Composé cristallin blanc utilisé comme analgésique et également comme antipyrétique
23 Horizontal Une ville du centre de la Tanzanie
24 Dieu horizontal de la mort
25 Pâte en forme horizontale et séchée à base de farine et d'eau et parfois d'oeuf
27 Horizontal Membre du peuple Siouan de Virginie et de Caroline du Nord
32 Horizontal Un fort désir agité
35 Prélat sud-africain horizontal et leader de la lutte antiapartheid (né en 1931)
37 Horizontal Document commercial utilisé pour demander à quelqu'un de fournir quelque chose en échange d'un paiement
38 moucherons horizontaux
41 Horizontal Une ancienne ville du nord du Portugal
42 Cabane Eskimo horizontale
43 Mécanisme de rotation horizontale sous la forme d'une roue de rotation montée universellement qui offre une résistance aux virages dans toutes les directions
44 Horizontal La capitale de Bahreïn
46 Horizontal L'acte de donner une teinte claire aux cheveux
48 Genre de type horizontal des Majidae
50 Horizontal N'importe laquelle de plusieurs plantes du genre Camassia
54 grondins volants horizontaux
59 Horizontal La récolte entière peut être récoltée en une seule fois
60 Horizontal Une loi adoptée par le Congrès américain pour empêcher les employés de se blesser ou de contracter des maladies au cours de leur emploi
61 Horizontal Bloc lourd de fer ou d'acier sur lequel les métaux chauds sont façonnés par martelage
62 Homme d'État anglais horizontal qui s'est opposé au divorce d'Henry VIII de Catherine d'Aragon et a été emprisonné et décapité
63 Horizontal Un homme qui courtise une femme
64 Joueur de baseball horizontal des États-Unis
65 Horizontal Un look secret
66 Mouette mince et horizontale à ailes étroites et à queue fourchue
67 Horizontal Connu pour les raisins et les olives et l'huile d'olive
1 Leader révolutionnaire vertical français (né en Suisse) qui a été un leader dans le renversement des Girondins et a été poignardé à mort dans son bain par Charlotte Corday (1743-1793)
2 Herbes verticales annuelles à vivaces de la région méditerranéenne
3 vignes arbustives tropicales tropicales d'Asie du Sud-Est portant des fruits épicés
4 Ani vertical
5 Vertical La première lumière du jour
6 Titre vertical pour l'ancien monarque héréditaire d'Iran
7 Vertical Un photographe qui utilise une caméra vidéo
8 Vertical Une ville du sud de la Turquie sur la rivière Seyhan
9 Vertical Une région aride avec peu ou pas de végétation
10 Peintre espagnol surréaliste vertical (1904-1989)
11 Vertical N'importe lequel de divers composés solubles dans l'eau ayant un goût aigre et capables de tourner au tournesol et de réagir avec une base pour former un sel
12 Vertical Originaire ou habitant de la Thaïlande
13 Vertical (dans le Gnosticisme) un pouvoir divin ou une nature émanant de l'Être Suprême et jouant divers rôles dans le fonctionnement de l'univers
21 Vertical Un volcan actif dans le sud-est de la Colombie dans les Andes
22 Vertical Un lepton de très grande masse
26 Vertical Un membre des Indiens d'Amérique du Sud vivant au Brésil et au Paraguay
28 Vertical Le principal nerf sensoriel du visage et le nerf moteur des muscles de la mastication
29 Vertical Un tourbillon ou un tourbillon miniature résultant du retour d'un courant de fluide sur lui-même
30 Vertical artiste britannique et écrivain de vers absurdes (1812-1888)
31 Biscuit au chocolat vertical fourré de crème blanche
32 Vertical Un missile balistique capable de voyager d'un continent à un autre
33 Vertical Une langue tchadienne tricolore
34 Unité de capacité verticale A utilisée pour mesurer le hareng frais
36 Vertical Large Large hybride juteux entre la mandarine et le pamplemousse ayant une peau ridée et épaisse
39 Tissu tissé uni (souvent glacé) vertical en laine ou en laine et coton utilisé spécialement autrefois pour les doublures, les vêtements et les rideaux
40 Vertical Une unité de poids d'apothicaire égale à 480 grains ou un douzième de livre
45 Vertical Une ville du centre de la Belgique
47 Vertical Un châle long aux couleurs vives
49 Vertical Un livre de l'Ancien Testament décrivant comment Josué a conduit les Israélites à Canaan (la Terre Promise) après la mort de Moïse
51 Vertical Un anti-inflammatoire non stéroïdien (noms commerciaux Advil et Motrin et Nuprin) utilisé pour soulager la douleur de l'arthrite et comme analgésique et antipyrétique
52 Antilope verticale ressemblant à une chèvre de l'Eurasie centrale ayant un nez tronqué comme une trompe
53 Joueur de tennis vertical américain (né en Yougoslavie en 1973)
54 Vertical Une légère humidité
55 plantes succulentes verticales ayant des rosettes de feuilles généralement avec des fibres comme le chanvre et des épis de fleurs voyantes
56 Activité verticale impliquée dans le maintien de quelque chose en bon état de fonctionnement
57 Vertical (sud-africain) un voyage en char à bœufs (en particulier une migration organisée par un groupe de colons)
58 Vertical Un lac de montagne (en particulier un lac formé par des glaciers)
Mots croisés 6 sur 6 en russe:1 pilote d'essai soviétique horizontal, héros de l'Union soviétique, l'un des participants du vol sans escale Moscou - Pôle Nord - Vancouver
2 Oreille horizontale
3 devineuse horizontale
4 Ville horizontale en Italie sur l'île de Sicile
5 Fils texturés bouclés horizontaux obtenus par ondulation dans des chambres chauffées
6 Cinéaste horizontal français, scénariste ('' Bad Blood '', '' Boyfriend Meets Girl '')
7 Pièce verticale en argent du Grand-Duché de Lituanie du XVIe siècle
8 Biochimiste américain vertical, a synthétisé pour la première fois le gène de l'ARNt (prix Nobel 1968)
9 Ville verticale de la Fédération de Russie, Ossétie du Nord, sur le fleuve Ardon, sur la route militaire d'Ossétie
10 Niche verticale horizontale dans le mur de la chambre funéraire, où le défunt a été mis et muré ou suspendu avec un auvent
11 Vertical La cuisse de la carcasse
12 Ville verticale dans le sud-est de la France
Mots croisés 6 sur 6 en anglais:1 Horizontal Membre du peuple indien du nord de la Californie et du sud de l'Oregon
2 Horizontal Membre de l'une des quatre divisions des Grecs préhistoriques
3 Horizontal Peut devenir addictif
4 Dieu grec horizontal de la lumière
5 Petits articles personnels ou vestimentaires ou à coudre horizontaux
6 Arbre en bois de valeur horizontale de Nouvelle-Zélande produisant du bois dur rougeâtre utilisé pour les meubles et les ponts et les quais
7 Vertical Une ligne droite qui coupe une courbe en deux points ou plus
8 Vertical N'importe lequel de plusieurs oiseaux à crête du vieux monde avec un bec mince courbé vers le bas
9 romancier américain vertical noté pour les livres pour enfants (1832-1888)
10 merles bleus nord-américains verticaux
11 Vertical Une personne dont l'occupation consiste à fabriquer et à modifier des vêtements
12 Genre de type vertical des Annonacées
Conclusion
L'utilisation du solveur SAT augmente la complexité des mots croisés qui peuvent être générés. Comme dans l'article précédent, je veux demander au prochain pic incontesté - faire un mot croisé de mots russes ou anglais sous la forme d'un carré 7 par 7. Qui acceptera le défi?