#include <stdio.h> #include <stdlib.h> int coupsPossibles [16] [5] = {{2, 1, 4, 0, 0}, {3, 0, 5, 2, 0}, {3, 1, 6, 3, 0}, {2, 2, 7, 0, 0}, {3, 0, 5, 8, 0}, {4, 1, 4, 6, 9}, {4, 2, 5, 7, 10}, {3, 3, 6, 11, 0}, {3, 4, 9, 12, 0}, {4, 5, 8, 10, 13}, {4, 6, 9, 11, 14}, {3, 7, 10, 15, 0}, {2, 8, 13, 0, 0}, {3, 9, 12, 14, 0}, {3, 10, 13, 15, 0}, {2, 11, 14, 0, 0}}; #define absolue(x) ((x)>0?(x):-(x)) int x [16] = {0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3}; int y [16] = {0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3}; class Position { char _pos [16]; char _vide; char _h; public : Position () { for (int i = 0; i < 15; i++) _pos [i] = i + 1; _pos [15] = 0; _vide = 15; _h = 0; } void joue (int coup) { _h -= absolue (x [coup] - x [_pos [coup] - 1]) + absolue (y [coup] - y [_pos [coup] - 1]); _h += absolue (x [_vide] - x [_pos [coup] - 1]) + absolue (y [_vide] - y [_pos [coup] - 1]); _pos [_vide] = _pos [coup]; _pos [coup] = 0; _vide = coup; } bool finale () { return _h == 0; } int h () { return _h; } void melange (int nbCoups) { for (int i = 0; i < nbCoups; i++) { int coupChoisi = 1 + rand () % coupsPossibles [_vide] [0]; joue (coupsPossibles [_vide] [coupChoisi]); } } char vide () { return _vide; } }; class Noeud { Position _p; int _g, _h; public : Noeud *parent, *suivant; Noeud () { suivant = NULL; } void init (Position & p, int g) { _p = p; _g = g; _h = p.h (); } int f () { return _g + _h; } bool final () { return _p.finale (); } int vide () { return _p.vide (); } void joue (int coup) { _p.joue (coup); _g++; _h = _p.h (); } }; // valeur maximum de f const int MaxLength = 1000; // une pile d'ouverts par f possible Noeud ouverts [MaxLength + 1]; void insere (Noeud * noeud) { Noeud * tmp = & ouverts [noeud->f ()]; noeud->suivant = tmp->suivant; tmp->suivant = noeud; } int fcourant = 0; Noeud fermes; Noeud * meilleur () { while (ouverts [fcourant].suivant == NULL && fcourant < MaxLength) fcourant++; return ouverts [fcourant].suivant; } bool developpe (Noeud * noeud) { // On ote le noeud développé de l'ensemble des Ouverts ouverts [noeud->f ()].suivant = noeud->suivant; // on insere les fils dans les ouverts for (int i = 1; i <= coupsPossibles [noeud->vide ()] [0]; i++) { Noeud * tmp = new Noeud (); *tmp = *noeud; if (tmp == NULL) { fprintf (stderr, "Abandon, mémoire saturée\n"); return false; } tmp->parent = noeud; tmp->joue (coupsPossibles [noeud->vide ()] [i]); insere (tmp); } // On l'ajoute à l'ensemble des fermes noeud->suivant = fermes.suivant; fermes.suivant = noeud; return true; } int AEtoile (Position & p) { Noeud * racine = new Noeud; racine->init (p, 0); insere (racine); Noeud * noeud = meilleur (); while (true) { if (!developpe (noeud)) return -1; noeud = meilleur (); if (noeud == NULL) return -1; if (noeud->final ()) break; } return noeud->f (); } Position pos; int seuil; bool IDAEtoileRecursif (int g); int IDAEtoile () { bool trouve = false; for (seuil = pos.h (); seuil < MaxLength && !trouve; seuil++) { fprintf (stderr, "%d,", seuil); trouve = IDAEtoileRecursif (0); } return seuil - 1; } bool IDAEtoileRecursif (int g) { if (g + pos.h () > seuil) return false; if (pos.finale ()) return true; char vide = pos.vide (); for (int i = 1; i <= coupsPossibles [vide] [0]; i++) { pos.joue (coupsPossibles [vide] [i]); if (IDAEtoileRecursif (g + 1)) return true; pos.joue (vide); } return false; } int main () { Position p; p.melange (100); pos = p; fprintf (stdout, "IDAEtoile : %d\n", IDAEtoile ()); fprintf (stdout, "AEtoile : %d\n", AEtoile (p)); }