Maîtrisez l'Algorithme de Warnsdorff pour le Problème du Cavalier aux Échecs

Vous cherchez à résoudre le problème du parcours du cavalier aux échecs ? L'algorithme de Warnsdorff est une solution élégante et efficace. Découvrez comment il fonctionne et comment il peut vous aider.

Cet article vous guide à travers les étapes clés, avec des exemples concrets et des explications claires, pour que vous puissiez l'appliquer facilement. Ne vous laissez plus déconcerter par ce défi algorithmique !

Qu'est-ce que l'Algorithme de Warnsdorff ?

L'algorithme de Warnsdorff est une heuristique utilisée pour résoudre le problème du parcours du cavalier. Le but est de faire parcourir à un cavalier toutes les cases d'un échiquier une seule fois.

Contrairement à une approche par force brute, Warnsdorff utilise une règle simple pour guider le cavalier :

• Privilégier les cases adjacentes non visitées avec le moins de mouvements possibles restants.

En clair, le cavalier choisit toujours la case la plus "difficile" à atteindre plus tard.

Les Avantages de l'Algorithme de Warnsdorff

Pourquoi utiliser Warnsdorff plutôt qu'une autre méthode ? Voici quelques avantages :

• Simplicité : Facile à comprendre et à implémenter.
• Efficacité : Trouve une solution rapidement dans la plupart des cas.
• Pas de backtracking excessif : Réduit considérablement le besoin de revenir en arrière dans la recherche.
• Adaptabilité : Peut être utilisé sur des grilles de différentes tailles, pas seulement un échiquier standard 8x8.

Comment Fonctionne l'Algorithme de Warnsdorff ?

Voici les étapes clés de l'algorithme :

1. Point de Départ : Choisissez une case de départ aléatoire sur l'échiquier.
2. Accessibilité : Calculez l'accessibilité de chaque case adjacente non visitée (nombre de cases non visitées accessibles depuis cette case).
3. Choix du Mouvement : Déplacez le cavalier vers la case adjacente non visitée avec la plus faible accessibilité.
4. Marquer la Visite : Marquez la case actuelle comme visitée.
5. Répéter : Répétez les étapes 2 à 4 jusqu'à ce que toutes les cases aient été visitées, ou qu'aucun mouvement valide ne soit possible.

Illustration avec un Exemple Simplifié

Imaginez un mini-échiquier 3x3. Partons de la case centrale.

Le cavalier peut se déplacer vers les coins. L'algorithme choisirait un coin (car chaque coin a le même nombre de mouvements disponibles), et continuerait jusqu'à avoir parcouru toutes les cases.

Code en C++ pour l'Algorithme de Warnsdorff

Le code suivant donne une implémentation en C++ de l'algorithme de Warnsdorff.

// C++ program to for Knight's tour problem using
// Warnsdorff's algorithm
#include <iostream>
#define N 8

// Move pattern on basis of the change of
// x coordinates and y coordinates respectively
static int cx[N] = {1,1,2,2,-1,-1,-2,-2};
static int cy[N] = {2,-2,1,-1,2,-2,1,-1};

// function restricts the knight to remain within
// the 8x8 chessboard
bool limits(int x, int y) {
    return ((x >= 0 && y >= 0) && (x < N && y < N));
}

/* Checks whether a square is valid and empty or not */
bool isempty(int a[], int x, int y) {
    return (limits(x, y)) && (a[y*N+x] < 0);
}

/* Returns the number of empty squares adjacent
   to (x, y) */
int getDegree(int a[], int x, int y) {
    int count = 0;
    for (int i = 0; i < N; ++i)
        if (isempty(a, (x + cx[i]), (y + cy[i])))
            count++;
    return count;
}

// Picks next point using Warnsdorff's heuristic.
// Returns false if it is not possible to pick
// next point.
bool nextMove(int a[], int *x, int *y) {
    int min_deg_idx = -1, c, min_deg = (N+1), nx, ny;

    // Try all N adjacent of (*x, *y) starting
    // from a random adjacent. Find the adjacent
    // with minimum degree.
    int start = rand()%N;
    for (int count = 0; count < N; ++count) {
        int i = (start + count)%N;
        nx = *x + cx[i];
        ny = *y + cy[i];
        if ((isempty(a, nx, ny)) &&
            (c = getDegree(a, nx, ny)) < min_deg) {
            min_deg_idx = i;
            min_deg = c;
        }
    }

    // IF we could not find a next cell
    if (min_deg_idx == -1)
        return false;

    // Store coordinates of next point
    nx = *x + cx[min_deg_idx];
    ny = *y + cy[min_deg_idx];

    // Mark next move
    a[ny*N + nx] = a[(*y)*N + (*x)]+1;

    // Update next point
    *x = nx;
    *y = ny;

    return true;
}

/* displays the chessboard with all the
   legal knight's moves */
void print(int a[]) {
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j)
            printf("%d\t",a[j*N+i]);
        printf("\n");
    }
}

/* checks its neighbouring squares */
/* If the knight ends on a square that is one
   knight's move from the beginning square,
   then tour is closed */
bool neighbour(int x, int y, int xx, int yy) {
    for (int i = 0; i < N; ++i)
        if (((x+cx[i]) == xx)&&((y + cy[i]) == yy))
            return true;
    return false;
}

/* Generates the legal moves using warnsdorff's
   heuristics. Returns false if not possible */
bool findClosedTour() {
    // Filling up the chessboard matrix with -1's
    int a[N*N];
    for (int i = 0; i< N*N; ++i)
        a[i] = -1;

    // Random initial position
    int sx = rand()%N;
    int sy = rand()%N;

    // Current points are same as initial points
    int x = sx, y = sy;
    a[y*N+x] = 1; // Mark first move.

    // Keep picking next points using
    // Warnsdorff's heuristic
    for (int i = 0; i < N*N-1; ++i)
        if (nextMove(a, &x, &y) == 0)
            return false;

    // Check if tour is closed (Can end
    // at starting point)
    if (!neighbour(x, y, sx, sy))
        return false;

    print(a);
    return true;
}

// Driver code
int main() {
    // To make sure that different random
    // initial positions are picked.
    srand(time(NULL));

    // While we don't get a solution
    while (!findClosedTour()) {
        ;
    }

    return 0;
}

Défis et Limitations de Warnsdorff

Bien que performant, l'algorithme de Warnsdorff n'est pas parfait :

• Pas toujours de solution : Il ne garantit pas de trouver une solution pour tous les points de départ. Il peut se retrouver bloqué.
• Complexité temporelle : Dans le pire des cas, sa complexité peut être élevée.

Conclusion: Warnsdorff, un outil puissant pour le Cavalier

L'algorithme de Warnsdorff offre une approche élégante et relativement simple pour résoudre le problème du parcours du cavalier. Sa facilité d'implémentation et son efficacité en font un outil précieux pour explorer ce défi classique de l'algorithmique. N'hésitez pas à l'expérimenter et à l'adapter pour vos propres explorations !