176
Recherche de la solution la plus courte pour les puzzles
}
void melange ( int nbCoups ) {
in i t ();
for (int i = O; i < nbCoups ; i++) {
int coupChoisi = 1 + rand ( ) %
coupsPossibles [_vide ] [0] ;
joue ( coupsPossibles [_vide ] [ coupChoisi ]);
}
}
char vide () { return _vide ; }
} ;
Il y a un coup à jouer pour amener la case 2 vers sa position finale, un coup pour la
case 6, 4 coups pour la case 9, etc.
Réponse : h = 1+1+4 + 0 + 3 + 1+0 + 3 + 1+3 + 0 + 1+4 + 4 + 2 + 1=29.
On modifie la classe Position comme suit pour avoir une heuristique admissible :
#define absolue (x) (( X ) >0 ? (X): - ( X ) )
int X [ 1 6] = {O ,
0,
int y [ 1 6] = {O '
2 '
class Position {
char _pos [ 16];
char _vide ;
char _h ;
public :
Position () {
1 '
2, 3 '
0, 1 '
1 '
2, 3 '
0, 1 '
0, 0, 0, 1 '
1 '
2, 2, 2, 3 '
3 '
for (int i = O; i < 15; i++)
_pos [ i ] = 1 + 1 ;
_pos [ 15] = 0;
vide = 15;
h = O;
}
void joue ( int coup) {
2,
2 '
1 '
3 '
3 '
3 } ;
1 '
3 } ;
h = absolue (x [coup] - x [_pos [coup ] - l]) +
absolue (y [coup ] - y [_pos [coup ] - l]);
}
h += absolue (x [_vide ] - x [_pos [coup ]
1]) +
absolue (y [_vide ] - y [_pos [coup ] - 1]);
_pos [_vide ] = _pos [coup ];
_pos [coup] = O;
_vide = coup ;
bool finale () { return h -- O; }