184
Bases de patterns
10.7 Corrigés des exercices
10.7.1 Le Ta quin
La taille de la base de patterns engendrée est de 167 = 228 = 268435456, soit 256
Mo.
On peut diminuer la taille à 19�1 mais l ' indice d' une position est alors plus difficile
à calculer. On peut toutefois précalculer les indices de début pour chaque position de la
première pièce.
Pour coder les positions et initialiser la base on écrit les fonctions suivantes :
const int Taille = 268435457;
const int Size = 16;
int Pieces = 7;
int casePiece [ Size ];
unsigned char distance [Taille ];
unsigned long long code () {
unsigned long long h = 0;
}
for (int i = 1; i < Pieces + l; i++) {
h = h << 4;
h I= casePiece [ i];
}
return h;
void in i t ( ) {
}
for (int i = O; i < Taille ; i++)
distance [ i] = 255; Il distance inconnue
for (int i = O; i < Pieces ; i++)
casePiece [ i + 1] = i;
distance [code ()] = O;
Pour engendrer toutes les configurations possibles et les tester on écrit :
int contenuCase [ Size ];
unsigned char distanceCourante = O;
bool testeConfiguration () {
bool trouve = false ;
if (distance [code ()] != 255)
return false ;