Discussion :

[claire_cartier]

Bonjour,
Je suis debutante en C et je dois realiser un puzzle en utilisant un tableau 3*3.
Pour cele l'algorithme est le suivant:
Un puzzle 3x3 se présente comme suit:

abc
def
gh

Une case est toujours vide afin de pouvoir y déplacer, au choix, l'une des
cases adjacentes dont elle prend la place. Ainsi, les deux opérations
réalisables sur l'exemple ci-dessus sont:

abc
de
ghf

abc
def
g h

L'objectif de la résolution du puzzle est de passer d'un état initial connu à
un état final choisi.

abc ? abc
def ---> d e
gh fgh

Pour ce faire, on évalue à chaque étape "l'erreur" vis-à-vis de l'état final en
sommant, sur chaque case, la distance par rapport à sa position dans l'état
final. La distance entre deux cases se calcule en additionnant le nombre de
colonnes et de lignes qui les séparent. Dans l'exemple ci-dessus, on a :

erreur(e) = 1
erreur(f) = 3
erreur(g) = 1
erreur(h) = 1
-------------
erreur 6

Donc, pour résoudre le puzzle, il suffit de choisir, à chaque étape, le
déplacement parmi les 2, 3 ou 4 possibles (selon la position de la case vide)
qui minimise cette erreur. Bien sûr, lorsque l'erreur est nulle, la solution
est atteinte.

La solution n'est pas toujours trouvable par cette méthode (c'est le cas de
l'exemple ci-dessus). Pour éviter une boucle infinie, il faut fixer un nombre
maximum d'itérations de l'algorithme.

Interface:

Le programme doit pouvoir s'appeller en ligne de commande, avec comme arguments
le puzzle de départ et le puzzle d'arrivée, mis sous forme d'une chaîne de 9
caractères entre guillemets (en concaténant les lignes de la matrice).

Le programme affiche les déplacements réalisés sous la forme d'une suite de
symboles représentant le parcours de la case vide. Par exemple "hbgd" pour
"haut-bas-gauche-droite", ou encore "^v<>".

Exemple:
$ MC []MON_PROGRAMME.EXE " 23185746" "1238 4765"

Solution: v>v>^<
Le truc c'est que je ne comprends pas vrt comment on calcule l'erreur et par ou commencer...Pourriez vous m'aider svp en ces temps difficiles d'examens..?
Merci d'avance!

[ToTo13]

Bonjour,

pour ce qui est de l'erreur, il faut bien lire l'énoncé, c'est expliqué dedans :
- Pour une pièce P du puzzle, elle génère une erreur E qui se calcule comme suit expliqué dans l'énoncé.
- On additionne le nombre de ligne et de colonnes entre la position actuelle de la pièce P et sa position juste (celle dans la solution du puzzle).

[claire_cartier]

ok j'ai compris comment n calcule cette erreur.. Mais une fois que j'ai calcule cette errueur, comment je fais pour resoudre ce puzzle? Comment choisir l'ordre des pieces que je dois bouger et faut iln que je prenne un matrice supplementaire temporaire ou je stockerai au fur t a mesure mon puzzle que je modifie a chaque calcule d'erreur?

[ToTo13]

Bonjour,

la encore, il suffit de lire l'énoncé, la solution est dedans :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
Donc, pour résoudre le puzzle, il suffit de choisir, à chaque étape, le
déplacement parmi les 2, 3 ou 4 possibles (selon la position de la case vide)
qui minimise cette erreur. Bien sûr, lorsque l'erreur est nulle, la solution
est atteinte.

Donc à chaque itération, tu peux calculer l'erreur de chaque pièce et tu déplaces celle qui se trouve contre la case vide et qui possède la plus petite erreur.