Premier algorithme

7.1 Problème

Nous avons défini les structures Piece et Puzzle, nous savons les créer à partir de paramètres, nous savons trouver le nombre de pièces bien placées dans un Puzzle défini et nous pouvons créer un fichier solution. Cependant, nous ne savons toujours pas donner la solution d’un Puzzle à partir des pièces données dans n’importe quel ordre. Il faut pour cela utiliser un algorithme de
résolution afin de résoudre ce type de problèmes.

7.2 Résolution

7.2.1 Idée générale

Nous allons démarrer en tentent de résoudre de façon simple le puzzle. Le premier algorithme consiste à construire le puzzle ligne par ligne, en commençant par la pièce en haut à gauche du puzzle. On pourra placer une pièce ou une de ses rotations seulement si elle respecte les contraintes de couleurs. Si aucune pièce n’est plaçable, alors l’algorithme prendra fin.

7.2.2 Heuristique1

/* Interface heuristique1
– type : Puzzle -> Puzzle
– arg : puz un puzzle
– pre : aucune
– post : si aucun problème ne se pose, renvoie le puzzle reformé selon les règles de l’heuristique
– raises : en cas de placement de pièce impossible -> exit()
*/

Ce premier algorithme est assez difficile à mettre en place. En effet, on place des pièces les unes après les autres, lignes par lignes, en commençant par la première. Cependant, lorsqu’on place une pièce, il faut qu’elle soit source de comparaison pour la mise en place d’une prochaine pièce à côté d’elle. De plus, il ne faut pas qu’une pièce soit réutilisée. Autant de conditions qui doivent être remplies nous entraîne à utiliser quelques astuces.

7.2.3 L’initialisation

Il y a beaucoup de paramètres à prendre en compte. Voici comment nous allons procéder :
– La pièce tout en haut à gauche du Puzzle sera p[1], cette pièce sera notre point de départ.
– Pour installer la seconde pièce, il faudra qu’elle respecte les conditions de couleur avec
p[1], puis la troisième pièce avec celle nouvellement placée... etc. Nous devons donc garder une pièce en mémoire pour qu’elle soit réutilisée en tant que comparaison. De plus, quand on placera une pièce au milieu du puzzle, il faudra comparer avec la pièce juste à gauche, et la pièce juste au-dessus, soit deux pièces à garder en mémoire et à faire "glisser" le long de la ligne.
– Enfin, il ne faut pas réutiliser une pièce déjà placée. Pour cela j’ai instauré un système simple. Il suffit d’initialiser toutes les lignes des pièces à 0. Si une pièce est utilisée, alors la ligne où elle est placée devient différente de 0. Quand on veut placer une pièce, il suffit juste de vérifier si sa ligne est bien égale à 0, sinon c’est qu’elle a déjà été placée. Voici donc l’initialisation de notre fonction, en supposant qu’on a défini un certain nombre de pièces avant :

for (i=1;i<=l*L;i++) // initialisation des lignes et colonnes
{
p[i].ligne = 0;
p[i].colonne = 0;
p[i].rotation = 0;
16
}
// La pièce en haut à gauche est la pièce p[1]
p[1].colonne = 1;
p[1].ligne = 1;
struct Piece q = p[1];
// q gardera en mémoire la pièce qu’on place, pour pouvoir comparer avec la
suivante à placer

7.2.4 La première ligne

Tout d’abord, nous allons nous occuper de la première ligne, qui ne nécessite pas le même traitement que les autres. En effet, lorsqu’on place une pièce sur la première ligne, il faut juste qu’une de ses couleurs correspondent à la couleur de droite de la pièce d’avant.
Voici une version simple de la boucle sur les colonnes pour la première ligne :

for (col=2;col<=L;col++)
{
for (i=2;i<=L*l;i++) // boucle sur les pieces p[i]
{
if (p[i].gauche == q.droite && p[i].ligne == 0)
// p[i].ligne == 0 assure que la pièce n’a pas été utilisée
{
p[i].ligne = 1;
p[i].colonne = col;
q = p[i]; // on place p[i] et on la garde en mémoire pour la
prochaine itération
break; // sort de la boucle pour entamer une nouvelle colonne
}
}

Il ne faut pas oublier que lorsqu’on place une pièce, on peut la placer après avoir effectué plusieurs rotations. Ainsi, il faudra rajouter les mêmes éléments, mais en utilisant la fonction rotationPiece. Ainsi on rajoutera les lignes :

else if (rotationPiece(p[i]).gauche == q.droite && p[i].ligne == 0)
// rotation de 90°
{ ...
}
else if (rotationPiece(rotationPiece(p[i])).gauche == q.droite
&& p[i].ligne == 0)
// rotation de 180°
{ ...
}
else if (rotationPiece(rotationPiece(rotationPiece(p[i]))).gauche == q.droite
&& p[i].ligne == 0)
// rotation de 270°
{ ...
}

Sans oublier de modifier la valeur de p.rotation.
Enfin, si aucune pièce n’a respecté les conditions de couleur, c’est-à-dire si i=l*L (vu qu’il
n’y a pas eu de break avant), alors on exit de la fonction.

if (i == l*L)
// si toutes les pièces n’ont pas respecté les conditions de placement, on exit
{
exit (5);
}

7.2.5 Le reste du puzzle

Maintenant, pour le reste du puzzle, le principe est le meme, à ceci près que l’on rajoute une boucle pour se déplacer sur les lignes du puzzle (de 2 à l) et qu’il faudra garder 3 pièces en mémoire.
– q gardera en mémoire la première pièce d’une ligne, afin de pouvoir placer celle en dessous
sur la première colonne.
– s aura le meme effet que le q de la première partie, c’est-à-dire sauvegarder la pièce que
l’on place.
– r gardera en mémoire la pièce placée une case à droite et une case en haut de s, et se
déplacera de la meme façon que s
Le but de cette manoeuvre est de pouvoir placer une pièce p en la comparant à s (à sa gauche)
et à r (au dessus) et de pouvoir faire "glisser" r et s le long de la ligne.
Voici le principe en image :

Pour commencer, on initialise q à p[1], s à p[L+1], et pour r, il suffira, à chaque changement de ligne, de choisir la pièce qui est à la ligne lig-1 et colonne 2, comme ceci :

q = p[1];
struct Piece s;
struct Piece r;
s = p[L+1];
for (lig=2;lig<=l;lig++) // lignes 2 à l
{
for (i=2;i<=l*L;i++)
// initialisation de r à chaque fois qu’une nouvelle ligne débute
{
if (p[i].ligne == lig-1 && p[i].colonne == 2)
{
r = p[i];
break;
18
}
}
...

Nous devons donc faire une boucle for pour se déplacer de lignes en lignes et une boucle for imbriquée pour se déplacer d’une colonne à l’autre sur chaque ligne. Ensuite, tout dépend du numéro de la colonne :
– si c’est la colonne 1, alors il suffit de comparer avec la pièce au-dessus, qui n’est autre que q. On place la pièce et cette pièce nouvellement placée deviendra q, pour la ligne d’après, toujours en colonne 1.
– si c’est une autre colonne, alors il faut comparer avec s à gauche, et r à droite. Une fois que l’on place une pièce, elle devient s, et il faut déplacer r de manière à ce que ses coordonnées soient : ligne lig-1 et colonne col+1.

Si on est sur la colonne 1 :

if (col == 1) // si on est sur la première colonne, il suffit de comparer
avec q qui est au dessus
{
for (i=2;i<=l*L;i++)
{
if (p[i].haut == q.bas && p[i].ligne == 0)
// on vérifiera toujours que p[i].ligne = 0
{
p[i].ligne = lig;
p[i].colonne = col;
q = p[i];
s = p[i];
break;
}
... Tous les cas de rotations
if (i == l*L) // si on ne trouve pas de pièce plaçable, on exit
{
exit(6);
}
}
...

Si on est sur une autre colonne :

else if (col <= L && col > 1) // pour les autres colonnes, on compare avec
s à gauche, et r en haut
{
for (i=2;i<=l*L;i++)
{
if (p[i].gauche == s.droite && p[i].haut == r.bas && p[i].ligne == 0)
{
p[i].ligne = lig;
p[i].colonne = col;
s = p[i]; // s devient la nouvelle pièce
for (j=2;j<=l*L;j++) // on déplace r selon les coordonnées
{
if (p[j].ligne == lig-1 && p[j].colonne == col+1)
{
r = p[j];
}
}
break;
}
... // Tous les cas de rotations
if (i == l*L) // si aucune pièce plaçable, exit
{
exit(7);
}

Ainsi, on a traité tous les cas pour chaque pièce lignes par lignes. En cas de problème, on sort de l’algorithme. Si aucun obstacle ne se pose, on obtient le Puzzle reconstruit par cet algorithme.