Les meilleurs développeurs jeux vidéos freelances sont sur Codeur.com

Résolution du Taquin

 Fermé·Moins de 500 €·1 offre·728 vues·2 interactions


Le but est de résoudre le jeu du taquin en utilisant les différentes structures type : piles, files tables de Hash.

Dans le jeu du taquin nous avons 9 cases disposées dans une matrice 3x3 ayant des valeurs uniques entre 0 et 8, comme par exemple l’état initial suivant :
5 4 0
6 1 8
7 3 2
Les règles du jeu sont simples ; seul le « 0 » peut bouger à gauche, à droite, en bas et en haut. Cependant, dans l’exemple ci-dessus, le « 0 » ne peut bouger qu’en bas ou à gauche. Le jeu est gagné lorsqu’on arrive à l’état final suivant :
1 2 3
4 5 6
7 8 0
L’idée de base pour résoudre le problème est d’engendrer à chaque étape tous les successeurs possibles et de les insérer dans une file d’attente. La stratégie est la suivante :Générer le premier élément de la file ;

Faire
1. Si premier élément de la file = état final  gagné (sortir de la boucle) ;
2. Déterminer les successeurs de l’élément en tête de la file qui n’ont jamais été insérés dans la file (utiliser une table de Hash pour savoir si un élément a déjà été visité) ;
3. Insérer les successeurs dans la file ;
4. Extraire de la file l’élément qui a généré les successeurs et l’insérer dans la table de Hash ; On utilisera une table de Hash pour déterminer si un état donné a déjà été inséré dans la file.
Au début, la table est vide ; puis peu à peu elle se remplira. A la fin du jeu il faudra donner le nombre d’états visités (= nombre d’éléments dans la table de Hash) et le nombre de mouvements pour arriver à la solution, c’est-à-dire la succession des mouvements du « 0 ». Il faudra afficher toutes les matrices qui vont de l’état initial à l’état final indiquant le mouvement du « 0 ».
Jusqu’ici l’algorithme de résolution a été décrit par rapport à une file d’attente ; il faudra aussi le concevoir et l’exécuter par rapport à une structure de pile. Tout simplement, on remplacera la file par la pile dans l’algorithme décrit ci-dessus.

Budget indicatif : Moins de 500 €

Publication : 02 juin 2021 à 11h41

Profils recherchés : Développeur de jeux vidéo freelance

Le profil du client est reservé aux prestataires abonnés

Créer un compte

1 freelance a répondu à ce projet

1 proposition de devis en moins de 2h

Publier un projet similaire

Chaque jour, des centaines de clients utilisent Codeur.com pour trouver un prestataire. Créez votre compte dès maintenant, remplissez votre profil et trouvez de nouveaux clients.

Trouver des nouveaux clients

Votre navigateur Web n’est plus à jour. Il ne permet pas d’afficher correctement le site Codeur.com.
Nous vous invitons à mettre à jour votre navigateur ou à utiliser un autre navigateur plus récent.