Je reprends un vieux chantier qui me fait fort déguster:
 
L'utilisateur définit les dims d'une matrice (genre 12×8) et l'appli génère une grille de mots croisés en optimisant l'emplacement des "cases noires" pour qu'il y en ait, évidemment, le moins possible.
 
L'appli utilise évidemment un/des dico(s) de mots, et l'utilisateur peut fixer qq contraintes, remplir a priori une partie de la grille, etc.
 
Ca fait des lustres que je réfléchis sur ce type d'algo, et tout ce que j'ai trouvé me semble trop bourrin. Une implémentation rudimentaire en C++ à base de "pile de bi-vecteurs chaînés" (!), ça faisait frime et ça marchait vaguement, mais IRREALISTE (encore plusieurs heures pour une 9×9...)
 
Un algorithme linéaire (ligne à ligne simple) est naturellement inconcevable vu la nature exponentielle du process.
 
 
Mais je pense qu'il existe des stratégies de génération beaucoup plus efficaces. Je pars du principe que l'être humain réussit à fabriquer de telles grilles en un temps ...humain.
 
Certains d'entre vous ont-ils déjà planché sur un pb analogue ou désassemblé du code de logiciels existants? Merci d'avance.

fort intéressant... mais je peux pas t'aider
 
drapal tout de même

T'as quoi comme contraintes? un nombre de mots sur la grille?
 
Moi ce que je ferais c 1) générer la liste des mots que je veux mettres sur la grille 2) les placer dessus, sans chercher à optimiser 3) une fois cette prmière grille générée tanter d'optimiser la grille avec un algo de type recuit simulé ou autre
 
Ca peut être une première approche, c pa sûr que ça donne qqc  

Regarde dans des bouquins d'IA.
En fait, ça peut presque s'apparenter à du A* dans le sens où tu cherche "un plus court chemin".
 
Mais fait quelques recherches car par exemple, le problème du taquin (les jeux de puzzle ou on a une matrice n x n avec un vide et où on fait coulisser les pièces) se resoud très bien.... jusqu'en 4 x 4. Après c'est même pas la peine de lancer ton thread...

<<T'as quoi comme contraintes? un nombre de mots sur la grille?>>
J'comprends pas. La contrainte C'EST la grille! Faut que les mots horizontaux et verticaux se croisent correctement et qu'ils appartiennent au(x) dictionnaire(s) fourni(s).
 
<<Moi ce que je ferais c 1) générer la liste des mots que je veux mettres sur la grille...>>
La liste des mots que tu PEUX mettre, c'est le dico! Dans cette affaire, je suppose le(s) dico(s) fixés et fournis à l'avance (ressources de l'appli). Ils ne sont pas générés à la volée. Le pb c'est vraiment l'algo compte tenu de ça.
 
Pour préciser: je dispose déjà de dictionnaires (un pour chaque taille de mot: 2 lettres, 3 lettres, etc.) structurés en arbres.

<<Regarde dans des bouquins d'IA. En fait, ça peut presque s'apparenter à du A* dans le sens où tu cherche "un plus court chemin".>>
 
Je suis une brêle totale en IA, mais l'idée me plaît bien. A* c'est quoi? Tu peux me donner un peu + de billard?
Merci d'avance.

Plutôt que A* tu devrai regarder du côté des problèmes d'odonancement (enfin surtout les algo pour les résoudres )

 
tout à fait. Sinon, y'a un langage qui est tout à fait adapter pour résoudre ce genre de pb : PROLOG. C'est pas évident à comprendre comment ça marche, faut trouver la modélisation de ton pb, mais après, c'est lui qui fait tout ...

Je vais essayer d'être + précis car j'ai l'impression qu'on parle de plusieurs choses en même temps.
 
Le pb fondamental de cet algorithme, c'est de trouver une "combinaison" de mots qui remplit la grille, sachant que plus on avance vers le but (la fin de la grille), plus il est probable d'"échouer".
 
En fait, l'algo passe le + clair de son temps à échouer. Jusqu'à présent, j'ai toujours raisonné "lettre par lettre". Prenons une matrice arrivée à un certain stade, par exemple si c'est une 5×5:
 
 AMOU-
 LIV--
 OT?--
 R----
 S----
 
L'algo va essayer de remplir la case ?
 
NB. Chaque fois qu'une lettre est testée et affichée, ça veut dire qu'il existe au moins un mot HORIZ et un mot VERT prolongeant cette lettre
 
?=A peut marcher. On fait l'hyporthèse. On continue. A un moment ou un autre, l'algo échoue: dans la case active il n'y a pas d'intersection HORIZ×VERT ou, du moins, toutes les lettres intersection ont été testées et il faut "remonter".
 
Voilà tout le problème: remonter où? lors d'un échec, quelle hypothèse parente remettre en cause? D'une façon générale, selon quelle stratégie progresser dans la grille?
 
J'espère avoir été à peu près intelligible. Mon pb est strictement algorithmique.

C'est marrant que tu parles de Prolog, Rufo, parce que c'est en effet (il y a très très longtemps!) dans ce langage que j'ai fait la première implémentation du bidule.
 
Mais, comme tu le dis, le Prolog n'est bon que sur une stratégie déjà correctement modélisée!! Et là, tu verrais quoi comme prédicats pour gérer cette foutue grille?

C'est typiquement un problème d'ordonancement ton truc (enfin c comme ça que je l'aborderai moi): tu veux placer des mots sur un espace 2D. Tu devrai rechercher des algo dans cete voie.

 
l'algo de découpe de planches le bois dans un panneau d'une certaine taille (2D bien sûr) et il faut minimiser la superficie les chutes; ça pourrait pas coller comme modélisation???

 
je verrais rien du tout comme modélisation pour Prolog car j'ai juré de ne plus jamais en faire : j'ai trop souffert avec ce langage à mon école d'Ingé

En fait on veut placer des LETTRES dans un espace 2D, ou plus exactement des INSTANCES de lettres (puisées dans l'alphabet). Mais les mots à "ordonnancer" ne sont pas réellement connus a priori... Enfin, certes, ils sont puisés dans des ensembles finis (les dicos), mais j'ai du mal à concevoir le truc comme si j'avais "a priori" N mots et qu'il s'agissait de les ranger...

 
Ben si, le truc t'as un esemble de mots: ton dico, et tu dosi arriver à en caser le plus possible sur la grille en minimisant les espaces vides et en respectants certaiens contraintes sur le placements des mots. Mais bon c qu'une approche, on doit pouvoir voir le PB auttrement.  

Merci LetoII pour tes idées. Je crois que tu te concentres sur la deuxième partie du pb, qui est d'optimiser le remplissage de la grille, càd de choisir l'emplacement idéal des cases noires pour en avoir le moins possible. Je dirais que c'est la dimension la + "intelligente" du process, mais paradoxalement elle est secondaire!
 
Prenons l'exemple d'une grille 7×7
 
En fait, l'algo va peut-être réussir à la remplir entièrement sans case noire! C'est-à-dire qu'il va trouver 7 mots HORIZ et 7 mots VERT qui se croisent parfaitement. Et la question est moins de savoir comment il a optimisé leur placement dans la grille que de savoir COMMENT IL A FAIT POUR LES SELECTIONNER dans un ensemble de 50000 éléments ou plus (les mots de 7 lettres).

 
Je peux te proposer une autre modélisation : celle du sac-à-dos (knap-sac). D'un côté, tu as un ensemble d'objets avec un poid pour chaque objet. De l'autre, un sac à dos qui peut contenir un poid max. Tu veux savoir quels sont les objets que tu dois prendre pour remplir au mieux ton sac-à-dos... Si t'arrive à faire coller tes contraintes pour ta génération de grille avec celle du sac à dos, ton pb est résolu

Interessant comme problème.
J'étudie le truc et je poste plus tard si j'ai une idée interessante ...

J'ai peur que vous ne pigiez pas le pb sous-jacent... L'allégorie du sac à dos est aux antipodes de la génération de grille!

 
Non je crois pas, je pense plutôt que c toi qui est trop proche de ton pb  

 
arrête moi si je me trompe :
ta contrainte : la taille 2D de ta grille
ton pb : trouver le maximum de mots qui vont pouvoir remplir ta grille avec le minimum de cases noires.
 
Toi, t'es parti pour remplir ta grille lettre par lettre pourvu que les lettres fassent au final des mots qui existent dans ton dico.
 
bon en y réfléchissant, je pense pas que le sac à dos puisse d'aider, c'est un pb à 1D et ton pb est 2D, donc la modélisation de la découpe de planches daans un panneau est mieux...
 
Tu sais, des fois, pour modéliser un pb, faut "tordre" un peu les données pour les faires coller à celles d'un pb déjà connu.

D'accord avec vos remarques. Je suis peut-être trop "focalisé" et la modélisation "découpe de planches" pourrait être pertinente, qui sait.
 
N'empêche que la structure implicite est plus de l'ordre de l'arborescence (ou du réseau) que du plan euclidien 2D. Je m'explique: dans la grille, chaque lettre a en quelque sorte le statut d'un ANCETRE vis-à-vis de la partie de la grille qui dépend d'elle:
 
Dans mon exemple:
 
A M O U -
L I V - -
O T - - -
R - - - -
S - - - -
 
le V situé en (3,2) a une incidence DIRECTE sur les cases (4,2) et (3,3) en ce sens qu'il détermine les mots possibles de la forme LIV-- et OV---, mais les cases (4,2) et (3,3), une fois remplies (testées), vont à leur tour influencer toute une descendance de possibilités. Chacune de ces possibilités reste INDIRECTEMENT dépendante du V situé en (3,2). C'est pour ça que je le vois comme un noeud dans une arborescence.
 
Reste que "voir" la grille comme une arborescence de cases n'est pas forcément l'option la plus efficace...

 
ben avec ta arborescence, ton pb est exponentiel. Avec ma modélisation de découpe de planches, le pb est polynomial (je crois pas dire de bêtises).

 
Je crois bien que tu dis une bêtise. Ce genre de problèmes ne sont pas polynomiaux.

 
Disons que le sac à dos ne convient pas.
 
Il s'agit d'un problème dit "du sac à dos" avec contraintes (qui sont les superpositions de lettres).

 
ah? il me semblait pourtant que c'était polynomial... Mais si c'est pas le cas, autant pour moi...

moi je procéderai comme cela:
 
1/ Random d'un mot qui rentre dans ta grille,
2/ tu le places aléatoirement,
3/si je ne me trompe pas - là je suis pas sur - 2 mots verticaux ne peuvent pas partir de lettres voisines du mot d'origine, à moins - cas qui doit être exceptionnel - que les 2 mots mis cote a cote forme tous des mots.
Dans ce cas, tu prends une position aléatoire par ex 2 lettres sur un mot horizontal de 7 lettres, et tu colles des mots verticaux aléatoirement en 2ème, 5ème et 7ème position qui sont susceptibles de rentrer dans ta grille.
4/ensuite il faut reprendre la condition précedente (espacement d'une ligne) afin de tester si des mots horizontaux peuvent, 2 lignes par 2 lignes, rentrer à partir des lettres précédemment implantées. Si ca marche pas, il faudra revenir en arrière et changer 1 ou plusieurs mots verticaux.  
5/Si ca marche, continuer le "tissage" de cette toile de mots, à partir des précédents.
 
A chaque fois, il faudra faire une séléction des mots qui collent potentiellement et faire un random pour le choix,
si le choix s'avère non exploitable,il faudra retourner dans ce tableau déjà généré.
 
Je sais pas si j ai été très clair mais je ferai comme ca...
 
prolog peut marcher mais bon courage pour t'en sortir avec ce truc là.
 
 

 
ben si, justement, c'est possible; aussi bien verticalement, que horizontalement. La meilleure grille serait finalement une grille sans case noire (mais là accroche toi Jeannot pour trouver les mots qui permettent de générer une telle grille, et en +, faudra pas qu'elle soit trop grande).

 
oui tu as raison...
je pense tout de même qu'on peut partir de cette méthode, même non optimisée mais qui serait cohérente, et l'améliorer par la suite.

En plus je pense que tu as mal pensé la "dimension" du problème.
 
Le caractère dimensionnant, à mon avis n'est pas la taille de la matrice mais le nombre de case noires. En effet passer sur un 10x10 de 4 à 3 noires représente par exemple un plus gros gap que de passer de 10x10 4 noires à 9x9 4 noires

Où à la limite une grandeur K=Nombre de noires / Nombre total de cases. (plus malin)

En général, au-delà des 7×7 (qui se batissent souvent à 0% de noires!), les concepteurs de grilles tolèrent jusqu'à 10% de noires.
 
Ainsi, il est sans doute préférable de raisonner par seuil. L'algo doit considérer qu'il échoue s'il utilise + de x% de noires, et il a toute latitude d'en utiliser moins!

 
C'est exactement le contraire qu'il faudrait réussir! Une grille de mot croisés réussie est "dense", tous les mots doivent se nourrir mutuellement. Là tu raisonnes sur un autre problème qui est plus "scrabble".
 
C'est pour ça que le contrat de base, ça devrait être "0 cases noires" (l'algo TEND à faire ça), mais comme combinatoirement c'est impossible au-delà de 7×7 il va commencer à se donner du mou.
 
Quand l'algo POSE une noire en (x,y), il va tolérer un reset de mot HORIZ en (x+1,y) et un reset de mot VERT en (x, y+1). "reset" au sens où le mot n'est plus empêtré dans les contraintes ascendantes. Par exemple, si * représente une case noire dans le début de grille suivante:
 
B I N A I R E
O R * - - - -
- - - - - - -
- - - - - - -
- - - - - - -
 
le mot-horiz situé "après" la case noire a rompu son lien de descendance vis-à-vis de OR. Donc, la lettre qui démarre en (4,2) n'a plus qu'un ascendant vertical (A). Je résume, la lettre en (4,2) doit satisfaire à la fois:
 
HORIZ: n'importe quelle lettre commençant un mot de 4 lettres (autrement dit, on a tout l'alphabet de ce côté!)
 
VERT: n'importe quelle 2e lettre d'un mot de 5 lettres commençant par A
 
Sans la case noire, la contrainte HORIZ serait beaucoup plus réduite et le croisement des deux contraintes commencerait à devenir acrobatique...
 
Cet exemple incarne bien la difficulté de cet algo.

Pour ceux que ça intéresse, y a des sources assez éducatives sur:
http://www.gtoal.com/athome/scrabble/crosswords.html
 
Le sous-rep "cross/" est le + intéressant. Une implémentation à base de DAWG (Directed Acyclic Word Graph)...
 
NB: le serveur est un poil poussif

sinon, peut-être qu'un algo génétique pourrait marcher : les mots horizontaux (et verticaux) sont les gènes et plus un gène a de cases noires, et plus il est mauvais. Un individu est une grille avec qq mots déjà dedans.
 
En gros, tu génère une population de départ : un certains nb de grilles avec le plus de mots possibles dedans (pourquoi pas des mots qui font la longueur de la largeur de ta grille) disposés une ligne sur 2 (ou une colonne sur 2, afin que tu aies des individus "horizontaux" et des individus "verticaux" ). Ensuite, tu recherches le gène le plus mauvais de chaque individu t tu essaye de l'améliorer en trouvant un mot qui arriverait à améliorer le gène. Tu me suis?

Putain ça va overloin ton idée!
 
Sais pas si c'est faizuble, mais c'est plaisant à imaginer.

Le defaut de l'algo genetique c'est que sont temps d'execution n'est pas defini. Comme là il a l'air de rechercher les performances, il doit y avoir plus efficace que ça. Ceci dit, je trouve toujours très intéressant de s'essayer à ce genre d'implémentation ; certainement ma formation de biologiste qui ressort...

 
je veux pas dire, mais bien souvent, la durée d'exécution d'un algo n'est pas bornée, surtout quand il s'agit d'une heuristique (à moins que tu implémentes une fonction qui arrête l'algo après un certain temps et balance la dernière solution trouvée)...

Oui ce que je voulais dire c'est que l'algo genetique est en moyenne toujours lent, alors que pour ce probleme, il doit exister des algo assez rapides ne faisant pas appel au hasard.
 
EDIT : je me rends compte de mon erreur : il FAUT faire appel au hasard ; il serait inacceptable que le programme sorte toujours la même grille pour une dimension donnée.

 
Oui et non. Vu l'explosion combinatoire, une stratégie exhaustive (i.e "force brute" ) n'est pas réaliste. Pour simplifier, ne considère qu'une minuscule grille 7×7 que l'algo devrait remplir sans case noire: il doit donc trouver un certain arrangement "gagnant" de 14 mots (7 horiz + 7 vertic) puisés dans un ensemble de 50.000 mots env. (les mots de 7 lettres, c'est un ordre de grandeur).
Je résume: le loto c'est 7 boules sur 49, là c'est 14 mots sur 50.000, et ordonnés en plus! Je vous dispense d'une estimation...
 
Moralité: la difficulté de cet algo n'est pas de trouver comment cracher très vite toutes les possibilités (c'est pas jouable), mais d'arriver à optimiser des stratégies d'accélération dans la recherche, éliminer rapidement des voies de garage, etc., c'est ce que fait le concepteur humain de grilles!
 
Alors, le hasard, ouais, c'est une manière comme une autre d'élaguer les branches, mais je ne pense pas que le hasard soit une stratégie optimale. La stratégie c'est de l'injecter au bon moment si besoin.
 
NB. - En fait, la grille admet en entrée un paramétrage tel que l'utilisateur remplit, par exemple, la première ligne et la première colonne de la matrice. L'algo doit alors finir le boulot. Avec ce type de contrainte initiale, tu n'auras jamais deux fois la même grille si tu la "charges" différemment, y compris si l'algorithme est déterministe.