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 + 1; i++) { h = h << 4; h |= casePiece [i]; } return h; } void init () { for (int i = 0; i < Taille; i++) distance [i] = 255; // distance inconnue for (int i = 0; i < Pieces; i++) casePiece [i + 1] = i; distance [code ()] = 0; } int contenuCase [Size]; unsigned char distanceCourante = 0; bool testeConfiguration () { bool trouve = false; if (distance [code ()] != 255) return false; for (int i = 0; i < Size; i++) if (contenuCase [i] != 0) { if ((i > 3) && (contenuCase [i - 4] == 0)) { casePiece [contenuCase [i]] = i - 4; if (distance [code ()] == distanceCourante) trouve = true; casePiece [contenuCase [i]] = i; } if ((i < 12) && (contenuCase [i + 4] == 0)) { casePiece [contenuCase [i]] = i + 4; if (distance [code ()] == distanceCourante) trouve = true; casePiece [contenuCase [i]] = i; } if ((i % 4 != 0) && (contenuCase [i - 1] == 0)) { casePiece [contenuCase [i]] = i - 1; if (distance [code ()] == distanceCourante) trouve = true; casePiece [contenuCase [i]] = i; } if (((i + 1) % 4 != 0) && (contenuCase [i + 1] == 0)) { casePiece [contenuCase [i]] = i + 1; if (distance [code ()] == distanceCourante) trouve = true; casePiece [contenuCase [i]] = i; } } if (trouve) distance [code ()] = distanceCourante + 1; return trouve; } bool engendre (int piece) { bool trouve = false; if (piece == Pieces) for (int i = 0; i < Size; i++) contenuCase [i] = 0; if (piece == 0) return testeConfiguration (); for (int i = 0; i < Size; i++) if (contenuCase [i] == 0) { contenuCase [i] = piece; casePiece [piece] = i; if (engendre (piece - 1)) trouve = true; contenuCase [i] = 0; } return trouve; } void analyseRetrograde () { init (); distanceCourante = 0; while (engendre (Pieces)) distanceCourante++; } int main () { analyseRetrograde (); }