générateur de mots croisés

tibo · 06-01-2011 20:34:53

Yop,

Voyant que chaque jour, nos journaux quotidiens nous fournissent des mots croisés, sans compter la multitude de magazine de jeux et mots croisés, j'ai pensé que des humains, meme en grand nombre et tres intelligents, ne pouvaient en créer autant. Il doit surement il y avoir des machines pour les aider.
Je me suis donc lancé dans la programation d'un générateur de mots croisés.

Mais mon niveau de programation est assez faible et je voudrais optimiser un peu mon programe.

J'ai une grille vide,
et de tres longues listes contenant presque tout les mots de langue francaise, triées par nombre de lettres.

En fait mon algorithme consiste à tester tout les mots possibles (horizontale par exemple) et de vérifier si ça fait des mots vertical.
Comme vous pouvez l'immaginer, c'est trèèèèèès loooooong.
Pour les grilles de taille <5 ça reste raisonnable, mais bon j'aimerais faire des grilles un peu plus grandes.

Je programe en Python, mais ce qui m'interesse c'est l'algorithme meme en pseudo-language
J'ai pensé à une procédure qui s'appelle elle meme, mais rien de tres concluant

des idées?

yoshi · 06-01-2011 20:46:48

Re,

Riche idée...

En fait mon algorithme consiste à tester tout les mots possibles (horizontale par exemple) et de vérifier si ça fait des mots vertical.

Avec ou sans les cases noires ?
Peut-être devrais-tu te limiter au départ à 500 mots maxi, et penser et à enrichir la base, quand ça tournera ?

J'ai pensé à une procédure qui s'appelle elle meme, mais rien de tres concluant.

C'est de la récursivité...
Le prog est plus court en principe mais il me semble bien avoir lu quelque part que, dans pas mal de cas, c'était plus lent à cause des "appels intensifs à la Pile".
Barbichu t'en dirait sûrement plus...

Je vais essayer de trouver du temps pour ton truc.
Mais il me semble qu'on code d'abord et qu'on optimise après, cela dit un programme est lent s'il gigote dans tous les sens et fait des tas de tests inutiles...

@+

freddy · 06-01-2011 21:11:41

Salut Tibo,

j'ai connu plusieurs cruciverbistes, ceux qui fabriquent des mots croisés.

Toute la subtilité de l'exercice n'est pas tant de remplir une grille, mais de donner des définitions très, très subtiles de mots plus ou moins connus.

La touche finale est de trouver le sens de mot à deux ou trois lettres qui comblent les trous (il y a une contrainte sur le nombre de cases noires) en évitant les répétitions (pew ost, erg, reg, ...)

Sinon, je pense que tu t'attelles à un boulot de ... comment dire, ... ah oui, du nom d'une planète de notre système solaire !

J'y pense : t'es tu attaqué à un programme de création de grille de sudoku ?

tibo · 06-01-2011 22:28:44

Re,

Yoshi, j'ai un programme qui tourne très bien, pour les petites grilles.
J'ai plusieurs grille de taille 2x2, 3x3, 3x4, 4x4
je dois avoir quelques grilles 5x5, mais en laissant tourner toute la nuit.
J'ai pas essayé au dessus.

mes grilles ont des cases noires.

Quant à trouver des définitions, je connais une littéraires très vicieuses qui s'en fera une joie, mais encore faut-il que je lui donne des grilles.

Je réfléchirai au sudoku, ça peut etre interessant
meme si je n'ai aucune idée de comment m'y prendre.
La difficulté étant que la grille soit unique.

Dernière modification par tibo (06-01-2011 22:29:09)

Fred · 06-01-2011 22:40:46

tibo a écrit :

je connais une littéraires très vicieuses

Ouh la, il prend une drole de tournure notre forum!!!!

Pour revenir à ton problème, je crois me souvenir d'avoir lu qqch sur des algorithmes produisant des algos de sudoku dans une revue du style Tangente ou Quadrature. A vérifier....
Si tu trouves des infos sur ton problème, tiens nous au courant (j'aime bien l'algorithmique...).

F.

yoshi · 06-01-2011 23:07:39

Re,

@tibo : Eh bien, publie ton truc, et on regardera s'il y a optimisation possible...
Sûrement : je l'ai déjà écrit, sur mon vieux Amstrad CPC 6128 avec 128 ko de RAM, cadencé à 4,77 Hz (processeur Z80), j'avais réussi à écrire un programme de conjugaison incollable :
- Sans liste de verbes,
- Pouvant conjuguer à tous, tous les modes, à la voix active, la forme pronominale et à la voix passive,
- Pouvant corriger ta conjugaison avec 20 messages d'erreur différents, les règles de conjugaison,
- Qui réclamait le verbe, l'auxiliaire à utiliser (avec aide sur dq), le choix des temps,
- Qui déterminait de lui-même le groupe du verbe et notamment pour les verbes en ir (4 mois de recherches pour l'astuce et 6 lignes de code)...
Moyennant quoi, écrit en Basic Amstrad, le prog occupait autour de 40 ko en mémoire et les délais d'attente étaient inférieurs à la demi-seconde.
Mon programme était de plein de nombres...

@Fred. Oui, qui l'eut cru ? Les algos de sudoku pullulent sur la Toile, certains tous faits, d'autres expliquant les méandres à programmer. Une grille de mots croisés, ça m'a l'air moins évident...

@+

Barbichu · 07-01-2011 01:37:43

Salut,

yoshi a écrit :

tibo a écrit :
J'ai pensé à une procédure qui s'appelle elle meme, mais rien de tres concluant.
C'est de la récursivité...
Le prog est plus court en principe mais il me semble bien avoir lu quelque part que, dans pas mal de cas, c'était plus lent à cause des "appels intensifs à la Pile".
Barbichu t'en dirait sûrement plus...

Je me sens presque invoqué quand tu parles comme ça ...
Les programmes récursifs ne sont pas toujours les plus courts, tout dépend de la nature du problème étudié et de la structure des objets utilisés. Quant à la pile, la programmation récursive l'utilise en effet intensivement, ce qui a pour effet d'augmenter la complexité mémoire de l'algo (qui sur une machine physique se traduit par des ralentissement lorsque la mémoire vient à manquer, puis un crash du petit nom de "stack overflow"). Il est cependant possible, avec un compilateur un tout petit peu élaboré et un style de programmation convenable (http://fr.wikipedia.org/wiki/R%C3%A9cursion_terminale) de contrôler l'occupation de la mémoire.

Quant au cas particulier du programme que tu veux écrire, tu auras sûrement compris qu'essayer tous les mots possible n'est pas raisonnable. Moi je tirerais un premier mot au hasard, en le plaçant horizontalement, puis je compléterais en tirant des complétions verticales possibles, puis horizontales, ... etc ... en mettant des cases noire là où l'on ne trouve rien de bien. En gros, tu lui fais jouer au Scrabble (R), mais avec toutes les lettres qu'il veut ! Après ce n'est que mon intuition.

a+

Dernière modification par Barbichu (07-01-2011 01:38:01)

Barbichu · 07-01-2011 01:44:40

Re,

yoshi a écrit :

Mais il me semble qu'on code d'abord et qu'on optimise après, cela dit un programme est lent s'il gigote dans tous les sens et fait des tas de tests inutiles...

En fait, d'abord on trouve un algo de complexité raisonnable. Ensuite on le code, et s'il marche en pratique sur des exemples de la taille voulue en un temps que l'on trouve raisonnable, on peut commencer à chercher des optim'.
Si le programme qu'on a codé ne termine pas, inutile de l'optimiser en général : soit on a fait une erreur, soit on n'a pas pris un bon algo ... soit il n'en existe pas de "bon" ;). Dans ce dernier cas, il faut trouver d'autres approches (à des problèmes simplifiés ou de manière probabiliste) ou utiliser un très gros calculateur ... ou bien les deux.

a+

tibo · 07-01-2011 23:32:01

Yop,

Comme demandé, voila mon code
ne faite pas attention aux commentaires que j'ai mis, quand je code, je pars en trance et je délire complètement.
Je l'ai un peu modifié en rajoutant un part d'aléatoire.

(j'aime pas trop montrer mes codes, j'ai l'impression qu'on va pouvoir analyser mon caractère bordélique, et en plus je sais que je code trop à l'arache n'importe comment)

# -*- coding: cp1252 -*-

from Tkinter import *

######################################

##### configuration de la grille #####

######################################

######################################

# l'utilisateur rentre la taille de la grille

nbligne=input("nombre de lignes : ")

nbcolonne=input("nombre de colonnes : ")

# et le nombre de tentative de grille

nbtest=input("nombre de tentative : ")

# liste des cases ligne par ligne

caseligne=[]

for i in range(nbligne):

    caseligne.append([])

    for j in range(nbcolonne):

        caseligne[i].append(1)

# liste des cases colonne par colonne

casecolonne=[]

for i in range(nbcolonne):

    casecolonne.append([])

    for j in range(nbligne):

        casecolonne[i].append(1)

######################################

# l'utilisateur va rentrer les cases noires

fen=Tk()    # pour cela on va utiliser Tkinter comme interface

case=[]

for i in range(nbligne):

    case.append([])

    for j in range(nbcolonne):

        case[i].append(Frame(fen, bg="white", width=10, height=10))

        # fonction remplir la case ligne i colonne j

        def action (envent, li=i, co=j):

            case[li][co].configure(bg="black")

            caseligne[li][co]=0            # 0 dans les listes pour indiquer

            casecolonne[co][li]=0          # que l'on ne peut pas écrire dedans

        case[i][j].grid(row=i, column=j, padx=2, pady=2)

        case[i][j].bind('<Button-1>', action)

# quand c'est fini on détruit la fenetre

Button(fen,text="OK", command=fen.destroy).grid(row=nbligne, column=1,columnspan=nbcolonne)

fen.mainloop()

#####################################################

##### nombre de lettres des mots dans la grille #####

#####################################################

#####################################################

# créons maintenant de nouvelles listes où l'on entrera le nombre de lettre de chaque mot

nblettreligne=[]

for i in caseligne:

    nblettreligne.append(i)

nblettrecolonne=[]

for i in casecolonne:

    nblettrecolonne.append(i)

#####################################################

# entrons le nombre de lettre

for i in range(nbligne):            # pour chaque ligne

    j=0                             # partons de la première case

    while j<len(nblettreligne[i]):  # tant que j n'est pas la derniere case de la ligne

        if nblettreligne[i][j]!=0:   # si on peut ecrire dedans

            if j!=len(nblettreligne[i])-1:      # et si on est pas la derniere case de la ligne (ya repetition la non? osef ça marche c le principal)

                if nblettreligne[i][j+1]!=0:    # si l'on peut écrire dans la case suivante (et oui c pour ça qu'il ne fallait pas etre à la derniere case)

                    nblettreligne[i][j]=nblettreligne[i][j]+nblettreligne[i][j+1]  # on ajoute à la case ou l'on est le nombre de lettre de la case suivante (hum pas tres clair tout ça, mais comme dit plus haut osef ça marche)

                    del(nblettreligne[i][j+1])  # et on supprime la case suivant (enfin on la supprime pas mais on en a tirer les info qu'on voulait donc on en a plus besoin donc on la jarte CQFD)

                    j=j-1           # case precédente

        j=j+1                       # case suivante

# meme chose pour chaque colonne

for i in range(nbcolonne):

    j=0

    while j<len(nblettrecolonne[i]):

        if nblettrecolonne[i][j]!=0:

            if j!=len(nblettrecolonne[i])-1:

                if nblettrecolonne[i][j+1]!=0:

                    nblettrecolonne[i][j]=nblettrecolonne[i][j]+nblettrecolonne[i][j+1]

                    del(nblettrecolonne[i][j+1])

                    j=j-1

        j=j+1

#####################################################

# on est à présent en possession de:

# nbligne         -> le nombre de ligne de la grille (jure j'aurais jamais cru)

# nbcolonne       -> le nombre de colonne de la grille (étonnant ça aussi)

# caseligne       -> chaque case ligne par ligne

# casecolonne     -> chaque case colonne par colonne

#      -> 1 = on peut écrire dedans

#      -> 0 = case noire , on ne peut pas écrire dedans

# nblettrelibne   -> chaque mot est remplacé par son nombre de lettre, classé par ligne

# nblettrecolonne -> chaque mot est remplacé par son nombre de lettre, classé par colonne

#################################

##### génération de grilles #####

#################################

# c bien beau tout ce qu'on a fait mais il va bien faloir commencer à les créer ces grilles

#################################

import mot_tri      # on importe tous les mots sous forme de liste

                    # dans mot_tri, il y a une liste s'appelant mot

                    # cette liste contient des listes tel que:

                    # mot[i] est une liste contenant des mots de i littres

from random import randrange

grillebien=[]

for i in range(nbtest):

    grille=[]

    for j in range(nbligne):

        grille.append([])

        for k in nblettreligne[j]:

            if k==0:

                grille[j].append(0)

            else:

                mot=mot_tri.mot[k][randrange(1,len(mot_tri.mot[k]))]

                for l in range(len(mot)):

                    grille[j].append(mot[l])

    grille2=[]

    for j in range(nbcolonne):

        grille2.append([])

        for k in range(nbligne):

            grille2[j].append(grille[k][j])

    ##### vérification de l'existance des mots #####

    mot=[]

    for j in grille2:

        m=""

        for k in j:

            if k==0:

                mot.append(m)

                m=""

            else:

                m=m+k

        mot.append(m)

    t=1

    for j in mot:

        if j in mot_tri.mot[len(j)]:

            1

        else:

            t=0

    if t==1:

        grillebien.append(grille2)

        print grille2

        print ""

print "fin"

.

Barbichu, j'aime bien ton idée de lui faire jouer un scrable, comme ça ya moins à s'embeter à vérifier si les mots existent (un peu quand meme), mais j'ai peur que ça soit un peu claircemé, enfin avec beaucoup de cases noires

PS: désolé Fred, je ne te la présenterai pas, c'est ma fiancée

Dernière modification par tibo (07-01-2011 23:38:38)

Fred · 07-01-2011 23:40:56

tibo a écrit :

PS: désolé Fred, je ne te la présenterai pas, c'est ma fiancée

Ah, c'est donc pour cela que tu connais ses moeurs!
Je suis ravi que tu me considères comme un concurrent!

Fred.

tibo · 08-01-2011 00:15:17

Par contre j'ai le regret de te dire ce n'est pas en faisant des math que tu la charmeras, elle en a horreur.(Comment ça tient entre nous? heu...)

Dernière modification par tibo (08-01-2011 12:22:03)

tibo · 10-01-2011 22:17:40

Yop,

J'ai réfléchi à l'idée du scrable.
Pour moi qui ne suis qu'un amateur, ça s'avère beaucoup plus compliqué...

Forum de mathématiques - Bibm@th.net

#1 06-01-2011 20:34:53

générateur de mots croisés

#2 06-01-2011 20:46:48

Re : générateur de mots croisés

#3 06-01-2011 21:11:41

Re : générateur de mots croisés

#4 06-01-2011 22:28:44

Re : générateur de mots croisés

#5 06-01-2011 22:40:46

Re : générateur de mots croisés

#6 06-01-2011 23:07:39

Re : générateur de mots croisés

#7 07-01-2011 01:37:43

Re : générateur de mots croisés

#8 07-01-2011 01:44:40

Re : générateur de mots croisés

#9 07-01-2011 23:32:01

Re : générateur de mots croisés

#10 07-01-2011 23:40:56

Re : générateur de mots croisés

#11 08-01-2011 00:15:17

Re : générateur de mots croisés

#12 10-01-2011 22:17:40

Re : générateur de mots croisés

Réponse rapide

Pied de page des forums