Problème algorithmique

Bonsoir,

je sollicite votre aide pour un problème d'algorithmique en langage java. Le projet que je réalise concerne le jeu de scrabble.

Mon plateau de jeu est représenté par un tableau en deux dimensions.

Je demande au joueur s'il veut jouer un jeton, au préalable distribué, en lui demandant les cordonnées où le placer.

Pour vérifier s'il a composé un mot, je vérifie si la ligne ou la colonne concernant la coordonnée rentrée comprend un nouveau mot ou non.

Pour faire ceci, je stocke dans une liste chaînée l'ensemble du dictionnaire et je recherche, dichotomiquement, si les mots sur le plateau sont dans la liste ou non.

Je dois maintenant réaliser une ia et c'est là que je rencontre des problèmes. Elle doit vérifier si il lui est possible de réaliser un mot en fonction de ses lettres.

J'aimerais que vous me donniez des exemples d'algorithmes utilisables avec la conception du jeu que je vous ai faite.

Merci d'avance.

Déjà, oublie la liste chainée, une hashtable sera bien plus efficace et terme de temps de recherche.

Ensuite, il faut tester en intégrant le plateau, car certaines lettres du mot peuvent déjà être posées. C'est même une condition du coup que de réutiliser une lettre déjà posée au moins.

Moi je commencerais comme ça:

pour chaque lettre P déjà posée sur le plateau:
   pour chaque lettre N de la main différente de celles déjà testées pour ce coup:
       pour chaque direction D libre autour de P, parmi (-1,0; 1,0; 0,1; 0,-1):
           former le morceau de mot MM constitué de P et N accolé dans la direction D, plus éventuellement d'autres lettres alignées qui seraient en contact.
           former l'autre morceau de mot perpendiculaire MP qui pourrait avoir été formé dans l'autre sens (si celui-ci fait plus de 1 lettre)
           passer au cas suivant si dans les 2 sens on a formé un mot inexistant (on ne joue que en posant des lettres alignées)
           essayer de placer les autres lettres dans le(s) sens restants et vérifier l'existence des mots ainsi créés (sans oublier les contacts avec d'autres lettres posées).

Et, juste un dernier point : à ce stade, on ne parle pas encore d'IA.

Je te remercie d'avoir répondu, je réfléchirai à tête reposée.

Et, juste un dernier point : à ce stade, on ne parle pas encore d'IA.

C'est effectivement un bien grand mot pour ce que je décris là ^^'

Ah, et puis au passage fait une hashtable pour chaque taille de mots.

Le projet étant à rendre pour dans deux jours je sais pas si j'aurai le temps de changer toute la structure du programme mais même avec celle-là c'est plutôt rapide donc je vais laisser comme ça pour le moment.

En tout cas merci encore.

ça avance bien ?

L'algo que tu m'as décrit est exactement ce que je pensais. Cependant je vois pas comment faire, au niveau code, pour tester tous les sens possibles dans lesquels on peut mettre les lettres sur le plateau.

Ben, faut trouver un algo (comme ici) ou une classe qui te génère toutes les permutations possibles de 6 lettre. Puis regarder somment tu peut mettre ces différents permutations dans des case alignées sur MM ou MP (selon celui que tu teste), d'un coté, de l'autre ou de part et d'autre. Et vérifier l'existence du (ou des) mots ainsi formés dans ton dictionnaire.

L'autre solution est de filtrer ton dictionnaire sur le morceau de mot que tu cherches (MM ou MP) puis sur les lettres que tu as en réserve et celles déjà posées et éventuellement accessibles dans l'axe recherché. C'est peut être plus rapide (à mesurer).

Le forum sur stackoverflow me sera très utile.

Je boucle le sujet maintenant que j'ai assez de données pour chercher quelque chose. Merci pour tout.