IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Mots croisés


Sujet :

Algorithmes et structures de données

  1. #1
    Futur Membre du Club
    Profil pro
    Inscrit en
    Novembre 2010
    Messages
    10
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Novembre 2010
    Messages : 10
    Points : 9
    Points
    9
    Par défaut Mots croisés
    Bonjour, j'ai un travail à faire et jviens pas demander des codes, mais plutôt une idée d'algorithme parce que ça fait 20h que je bloque dessus (alors qu'il est supposé prendre 10h ) du coup j'aurais besoin d'aide de personnes plus intelligentes.

    En fait je dois générer une grille de mot croisé 10x10 chaque mot complet sont suivi d'une case noir, ça c'est pas si compliqué parce qu'il y a beaucoup d'exemple sur internet, mais le truc compliqué c'est que j'ai une contrainte qui fait que chaque rangée et colonne doivent contenir un ou deux mots. Et ça sa complique toute la chose, parce que tous les algorithmes sur le web ne tient pas compte de cette contrainte.

    J'ai aussi pensé à quelque chose : on ajoute colonne par colonne des mots. Du coup à 2 colonnes par exemple, chaque rangée sera composés de 2 lettres et là on vérifie si les 2 lettres de chaque rangée sont le debut d'un mot (nous avons accès à une liste de mot qu'on doit mettre dans le crossboard) si c'est le cas pour chaque rangée, on place le prochain mot dans la colonne sinon on l'enlève et on remplace le mot jusqu'à que ça marche pour toute les rangées ou on décale le mot verticalement. Le problème avec cette methode c'est que ça demande trop de mot qui se coincide horizontalement et verticalement et d'autres problèmes un peu plus compliqué à expliquer.

    Du coup, je ne sais plus trop, si quelqu'un aurait une idée

    merci d'avance.

  2. #2
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    Décembre 2013
    Messages
    4 038
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : Décembre 2013
    Messages : 4 038
    Points : 9 347
    Points
    9 347
    Par défaut
    Tu dis que tu as un algorithme pour construire des grilles sans la dernière contrainte 'max 2 mots par ligne et par colonne'.
    Pour moi, la solution 'de base', c'est d'utiliser cet algorithme, puis rejeter les grilles qui ne respectent pas cette contrainte spécifique. C'est juste un post-traitement à faire, c'est donc très simple à implémenter. Le problème, c'est que sur des grilles relativement grandes, tu vas rejeter une grande proportion de grilles, et donc, ton algorithme risque d'être lent.

    La solution plus avancée, c'est de reprendre l'algorithme existant, et de supprimer telle ou telle grille alors même qu'elle n'est pas finie, dès qu'elle ne vérifie pas les contraintes spécifiques.
    Mais dans ce cas, il faut bien comprendre l'algorithme que tu utilises pour générer des grilles standard.
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  3. #3
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut
    Citation Envoyé par eric141 Voir le message
    le truc compliqué c'est que j'ai une contrainte qui fait que chaque rangée et colonne doivent contenir un ou deux mots. Et ça sa complique toute la chose, parce que tous les algorithmes sur le web ne tient pas compte de cette contrainte.
    Cette contrainte limite simplement la liste des mots pour compléter une ligne/colonne.

    Si tu as placé sur une ligne un mot de longueur 5 + 1 case noire, alors tu dois absolument compléter la ligne par un mot de longueur 3 + 1 case noire pour avoir un total de 10 cases = la longueur totale d'une ligne.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  4. #4
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    Décembre 2013
    Messages
    4 038
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : Décembre 2013
    Messages : 4 038
    Points : 9 347
    Points
    9 347
    Par défaut
    Citation Envoyé par pseudocode Voir le message
    Cette contrainte limite simplement la liste des mots pour compléter une ligne/colonne.

    Si tu as placé sur une ligne un mot de longueur 5 + 1 case noire, alors tu dois absolument compléter la ligne par un mot de longueur 3 + 1 case noire pour avoir un total de 10 cases = la longueur totale d'une ligne.
    Pas sûr.
    Si sur une ligne, on a par exemple : mot#a##mot (les caractères # symbolisent les cases noires), d'après ce que je lis, la contrainte est respectée.
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  5. #5
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut
    Citation Envoyé par tbc92 Voir le message
    Pas sûr.
    Si sur une ligne, on a par exemple : mot#a##mot (les caractères # symbolisent les cases noires), d'après ce que je lis, la contrainte est respectée.
    Effectivement, ca dépend de l'interprétation "chaque mot complet est suivi d'une case noir".

    Dans tous les cas, ca reste une contrainte sur la taille du mot servant à compléter la ligne/colonne.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

Discussions similaires

  1. [Free Pascal] Jeu de mots croisés
    Par Alcatîz dans le forum Codes sources à télécharger
    Réponses: 4
    Dernier message: 22/02/2015, 23h00
  2. Génération de mots croisés
    Par esired dans le forum Algorithmes et structures de données
    Réponses: 4
    Dernier message: 24/05/2013, 00h57
  3. mots croisés en C
    Par moncif44 dans le forum C
    Réponses: 1
    Dernier message: 30/04/2011, 12h07
  4. Mots croisés, mots fléchés ou sudokus
    Par rambc dans le forum jQuery
    Réponses: 9
    Dernier message: 22/04/2011, 00h16
  5. [JavaScript] [SRC] Aide aux mots-croisés
    Par Bisûnûrs dans le forum Contribuez
    Réponses: 14
    Dernier message: 22/12/2006, 05h39

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo