Principes fondamentaux du backtracking

Les algorithmes de backtracking représentent une technique clé en programmation C, notamment pour les défis algorithmiques. Leur essence repose sur une exploration systématique : progresser pas à pas dans un espace de solutions, revenir en arrière dès qu'une impasse est détectée, et explorer d'autres branches jusqu'à l'obtention d'un résultat ou l'épuisement des possibilités. Cette méthode est particulièrement efficace pour les problèmes de recherche exhaustive tels que la génération de permutations, de combinaisons, ou la résolution de labyrinthes.

Pour illustrer, imaginez un chercheur dans une bibliothèque tentant de retrouver un ouvrage perdu. Il inspecte les rayonnages un par un ; si un rayon ne contient pas le livre, il revient à l'entrée de la section pour essayer le rayon suivant. Ce processus se poursuit jusqu'à la découverte du livre ou l'exploration complète de la bibliothèque. En C, cette logique est généralement mise en œuvre via la récursion, structurée en trois étapes incontournables :

1. Établir un état : marquer les éléments déjà utilisés ou les positions visitées pour éviter les répétitions.
2. Exploration récursive : approfondir la recherche en se basant sur l'état courant, jusqu'à une condition d'arrêt (solution trouvée ou fin de la branche).
3. Restauration : annuler les modifications d'état pour permettre l'exploration d'alternatives à partir d'un point précédent.

L'avantage majeur du backtracking réside dans son mécanisme de retour, qui réduit les recherches inutiles par rapport à une force brute pure. D'un point de vue structurel, la pile d'appels récursifs gère implicitement les états, bien que des implémentations itératives utilisant une pile explicite soient possibles. Pour des raisons de clarté et de rapidité d'implémentation, la récursion est privilégiée dans les contextes compétitifs.

Implémentation C générique

Voici un modèle adaptable, utilisant des variables globaels pour simplifier le code. La fonction recherche incarne le cœur de l'algorithme.

#include <stdio.h>
#include <string.h>

#define TAILLE_MAX 10

int sequence[TAILLE_MAX];   // Stocke la solution en cours de construction
int marque[TAILLE_MAX];     // Indique si un élément a été utilisé
int dimension;              // Taille du problème

void recherche(int etape) {
    // Condition d'arrêt : solution complète
    if (etape == dimension) {
        for (int i = 0; i < dimension; i++) {
            printf("%d ", sequence[i]);
        }
        printf("\n");
        return;
    }

    // Tentative pour chaque élément non utilisé
    for (int candidat = 0; candidat < dimension; candidat++) {
        if (!marque[candidat]) {
            marque[candidat] = 1;           // Marquer l'élément
            sequence[etape] = candidat;     // Ajouter à la solution
            recherche(etape + 1);           // Exploration récursive
            marque[candidat] = 0;           // Restauration
        }
    }
}

int main() {
    dimension = 3;
    memset(marque, 0, sizeof(marque));
    recherche(0);
    return 0;
}

Ce modèle est modulable : les variables globales peuvent être passées en paramètres pour éviter les effets de bord, et des conditions de coupure supplémentaires peuvent être intégrées pour optimiser la performance.

Application aux problèmes classiques

Permutations

Pour générer toutes les permutations d'un ensemble de n éléments distincts, on adapte le modèle ci-dessus en itérant sur les éléments de 1 à n. Le code suivant en offre une implémentation alternative avec des noms de variables et une structure légèrement modifiée.

#include <stdio.h>
#include <string.h>

#define LIMITE 10

int arrangement[LIMITE];
int disponible[LIMITE];
int taille_donnee;

void generer_permutations(int position) {
    if (position == taille_donnee) {
        for (int i = 0; i < taille_donnee; i++) {
            printf("%d", arrangement[i]);
            if (i < taille_donnee - 1) printf(" ");
        }
        printf("\n");
        return;
    }

    for (int valeur = 1; valeur <= taille_donnee; valeur++) {
        if (disponible[valeur]) {
            disponible[valeur] = 0;
            arrangement[position] = valeur;
            generer_permutations(position + 1);
            disponible[valeur] = 1;
        }
    }
}

int main() {
    scanf("%d", &taille_donnee);
    memset(disponible, 1, sizeof(disponible)); // Initialisation inverse
    generer_permutations(0);
    return 0;
}

Ici, le tableau disponible est initialisé à 1 (libre), et mis à 0 lors de l'utilisation, avec restauration après l'appel récursif.

Combinaisons

Les combinaisons requièrent un ordre croissant pour éviter les doublons. On introduit un paramètre depart pour contrôler le point de démarrage de l'itération.

#include <stdio.h>
#include <string.h>

#define MAX_COMBINAISON 20

int selection[MAX_COMBINAISON];
int utilise[MAX_COMBINAISON];
int n_total, k_taille;

void explorer_combinaisons(int profondeur, int debut) {
    if (profondeur == k_taille) {
        for (int i = 0; i < k_taille; i++) {
            printf("%d", selection[i]);
            if (i < k_taille - 1) printf(" ");
        }
        printf("\n");
        return;
    }

    for (int elem = debut; elem <= n_total; elem++) {
        if (!utilise[elem]) {
            utilise[elem] = 1;
            selection[profondeur] = elem;
            explorer_combinaisons(profondeur + 1, elem + 1); // Prochain élément supérieur
            utilise[elem] = 0;
        }
    }
}

int main() {
    scanf("%d %d", &n_total, &k_taille);
    memset(utilise, 0, sizeof(utilise));
    explorer_combinaisons(0, 1);
    return 0;
}

Le paramètre debut assure que chaque choix suivant est supérieur au précédent, garantissant des combinaisons uniques.

Sous-ensembles

Pour lister tous les sous-ensembles, la sortie se fait à chaque nœud de l'arbre récursif, et non seulement aux feuilles.

#include <stdio.h>
#include <string.h>

#define MAX_ENSEMBLE 20

int ensemble[MAX_ENSEMBLE];
int marqueur[MAX_ENSEMBLE];
int taille_globale;
int longueur_actuelle = 0;

void enumerer_sous_ensembles(int commencement) {
    // Afficher le sous-ensemble courant (y compris l'ensemble vide)
    for (int i = 0; i < longueur_actuelle; i++) {
        printf("%d", ensemble[i]);
        if (i < longueur_actuelle - 1) printf(" ");
    }
    printf("\n");

    for (int j = commencement; j <= taille_globale; j++) {
        if (!marqueur[j]) {
            marqueur[j] = 1;
            ensemble[longueur_actuelle++] = j;
            enumerer_sous_ensembles(j + 1);
            longueur_actuelle--; // Restauration de la longueur
            marqueur[j] = 0;
        }
    }
}

int main() {
    scanf("%d", &taille_globale);
    memset(marqueur, 0, sizeof(marqueur));
    enumerer_sous_ensembles(1);
    return 0;
}

Cette approche capture tous les sous-ensembles, y compris l'ensemble vide, en maintenant une longueur dynamique.

Problèmes de labyrinthe

Pour trouver des chemins dans une grille, on combine la vérification des limites, le marquage des cases visitées, et l'exploration directionnelle. Le code suivant utilise des vecteurs de déplacement pour simplifier la logique.

#include <stdio.h>
#include <string.h>

#define LIGNES_MAX 10
#define COLONNES_MAX 10

int grille[LIGNES_MAX][COLONNES_MAX];
int visite[LIGNES_MAX][COLONNES_MAX];
int chemin[LIGNES_MAX + COLONNES_MAX][2];
int nb_lignes, nb_colonnes;
int longueur_chemin = 0;

// Déplacements : droite et bas
int deplacements[2][2] = {{0, 1}, {1, 0}};

void chercher_chemins(int x, int y) {
    if (x == nb_lignes - 1 && y == nb_colonnes - 1) {
        // Enregistrer et afficher le chemin
        chemin[longueur_chemin][0] = x;
        chemin[longueur_chemin][1] = y;
        longueur_chemin++;
        for (int i = 0; i < longueur_chemin; i++) {
            printf("(%d,%d)", chemin[i][0], chemin[i][1]);
            if (i < longueur_chemin - 1) printf(" - ");
        }
        printf("\n");
        longueur_chemin--; // Restauration avant sortie
        return;
    }

    visite[x][y] = 1;
    chemin[longueur_chemin][0] = x;
    chemin[longueur_chemin][1] = y;
    longueur_chemin++;

    for (int d = 0; d < 2; d++) {
        int nx = x + deplacements[d][0];
        int ny = y + deplacements[d][1];
        if (nx >= 0 && nx < nb_lignes && ny >= 0 && ny < nb_colonnes && grille[nx][ny] == 0 && !visite[nx][ny]) {
            chercher_chemins(nx, ny);
        }
    }

    longueur_chemin--;
    visite[x][y] = 0; // Restauration
}

int main() {
    scanf("%d %d", &nb_lignes, &nb_colonnes);
    for (int i = 0; i < nb_lignes; i++) {
        for (int j = 0; j < nb_colonnes; j++) {
            scanf("%d", &grille[i][j]);
        }
    }
    memset(visite, 0, sizeof(visite));
    chercher_chemins(0, 0);
    return 0;
}

Les directions sont encapsulées dans un tableau, et la vérification des conditions (limites, accessibilité, non-visite) assure une exploration efficace.

Erreurs fréquentes et solutions

• Oubli de la restauration : Si les marqueurs (tableaux marque ou visite) ne sont pas réinitialisés après l'appel récursif, cela conduit à des résultats incomplets ou des boucles infinies. Tojuours placer la restauration immédiatement après l'appel récursif.
• Condition d'arrêt mal définie : Pour les permutations, l'arrêt doit survenir lorsque la séquence atteint la taille complète ; pour les combinaisons, lorsque la profondeur atteint k. Une condition incorrecte peut empêcher la génération des solutions.
• Manque d'élagage : Des coupures supplémentaires (comme le paramètre depart pour les combinaisons) réduisent les branches inutiles. Les ignorer augmente le temps d'exécution, surtout pour de grandes instances.
• Dépassement de tableau : Les tableaux doivent être dimensionnés en fonction des limites maximales du problème (par exemple, TAILLE_MAX 10 pour des n≤10). Toute vérification de coordonnées doit inclure les bornes.