---
title: "Backtracking et piles"
date: "2023-11-28"
---


# Problème des 8-reines

* Placer 8 reines sur un échiquier de $8 \times 8$.
* Sans que les reines ne puissent se menacer mutuellement (92 solutions). 

## Conséquence

* Deux reines ne partagent pas la même rangée, colonne, ou diagonale.
* Donc chaque solution a **une** reine **par colonne** ou **ligne**.

## Généralisation

* Placer $N$ reines sur un échiquier de $N \times
  N$. 
- Exemple de **backtracking** (retour en arrière) $\Rightarrow$ récursivité.

![Problème des 8-reines. Source:
[wikipedia](https://fr.wikipedia.org/wiki/Problème_des_huit_dames)](./figs/fig_recursivite_8_reines.png){width=35%}

# Problème des 2-reines

![Le problème des 2 reines n'a pas de solution.](figs/2reines.svg){width=50%}

# Comment trouver les solutions?

* On pose la première reine sur la première case disponible.
* On rend inaccessibles toutes les cases menacées.
* On pose la reine suivante sur la prochaine case non-menacée.
* Jusqu'à ce qu'on puisse plus poser de reine.
* On revient alors en arrière jusqu'au dernier coup où il y avait plus qu'une
  possibilité de poser une reine.
* On recommence depuis là.

. . .

* Le jeu prend fin quand on a énuméré *toutes* les possibilités de poser les
  reines.

# Problème des 3-reines

![Le problème des 3 reines n'a pas de solution non plus.](figs/3reines.svg)

# Problème des 4-reines

![Le problème des 4 reines a une solution.](figs/4reines.svg)

# Problème des 4-reines, symétrie

![Le problème des 4 reines a une autre solution (symétrie
horizontale).](figs/4reines_sym.svg)

# Problème des 5 reines

## Exercice: Trouver une solution au problème des 5 reines

* Faire une capture d'écran / une photo de votre solution et la poster sur
  matrix.

```C













```

# Quelques observations sur le problème

* Une reine par colonne au plus.
* On place les reines sur des colonnes successives.
* On a pas besoin de "regarder en arrière" (on place "devant" uniquement).
* Trois étapes:
    * On place une reine dans une case libre.
    * On met à jour le tableau.
    * Quand on a plus de cases libres on "revient dans le temps" ou c'est qu'on
      a réussi.

# Le code du problème des 8 reines (1/5)

## Quelle structure de données?

. . .

Une matrice de booléens fera l'affaire:

```C
bool board[n][n];
```

## Quelles fonctionnalités?

. . .

```C
// Pour chaque ligne placer la reine sur toutes les colonnes
//    et compter les solutions
void nbr_solutions(board, column, counter);
// Copier un tableau dans un autre
void copy(board_in, board_out);
// Placer la reine à li, co et rendre inaccessible devant
void placer_devant(board, li, co);
```

# Le code du problème des 8 reines (2/5)

## Le calcul du nombre de solutions

```C
// Calcule le nombre de solutions au problème des <n> reines
rien nbr_solutions(board, column, count)
    pour chaque ligne 
        si la case libre
            si column < n - 1
                copier board dans un "new" board, 
                    y poser une reine
                    et mettre à jour ce "new" board
                nbr_solutions(new_board, column+1, count)
            sinon
                on a posé la n-ème et on a gagné
                count += 1
```

# Le code du problème des 8 reines (3/5)

## Le calcul du nombre de solutions

```C
// Placer une reine et mettre à jour
rien placer_devant(board, ligne, colonne)
    board est occupé à ligne/colonne
        toutes les cases des colonnes
           suivantes sont mises à jour
```

# Le code du problème des 8 reines (4/5)

## Compris? Alors écrivez le code et postez le!

. . .

## Le nombre de solutions

\footnotesize

```C
// Calcule le nombre de solutions au problème des <n> reines
void nb_sol(int n, bool board[n][n], int co, int *ptr_cpt) {
    for (int li = 0; li < n; li++) {
        if (board[li][co]) {
            if (co < n-1) {
                bool new_board[n][n]; // alloué à chaque nouvelle tentative
                copy(n, board, new_board);         
                prises_devant(n, new_board, li, co);
                nb_sol(n, new_board, co+1, ptr_cpt);
            } else {
                *ptr_cpt = (*ptr_cpt)+1;
            }
        }
    }
}
```


# Le code du problème des 8 reines (5/5)

\footnotesize

## Placer devant

```C
// Retourne une copie du tableau <board> complété avec les positions
// prises sur la droite droite par une reine placée en <board(li,co)>
void placer_devant(int n, bool board[n][n], int li, int co) {
    board[li][co] = false; // position de la reine
    for (int j = 1; j < n-co; j++) {
        // horizontale et diagonales à droite de la reine
        if (j <= li) {
            board[li-j][co+j] = false;
        }
        board[li][co+j] = false;
        if (li+j < n) {
            board[li+j][co+j] = false;
        }
    }
}
```

# Les piles (1/5)

## Qu'est-ce donc?

* Structure de données abstraite...

. . .

* de type `LIFO` (*Last in first out*).

![Une pile où on ajoute A, puis B avant de les retirer. Source:
[Wikipedia](https://upload.wikimedia.org/wikipedia/commons/e/e1/Stack_(data_structure)_LIFO.svg)](figs/Stack.svg){width=70%}

## Des exemples de la vraie vie

. . .

* Pile d'assiettes, de livres, ...
* Adresses visitées par un navigateur web.
* Les calculatrices du passé (en polonaise inverse).
* Les boutons *undo* de vos éditeurs de texte (aka *u* dans vim).

# Les piles (2/5)

## Fonctionnalités

. . .

1. Empiler (push): ajouter un élément sur la pile.
2. Dépiler (pop): retirer l'élément du sommet de la pile et le retourner.
3. Liste vide? (is_empty?).

. . .

4. Jeter un œil (peek): retourner l'élément du sommet de la pile (sans le dépiler).
5. Nombre d'éléments (length).

## Comment faire les 4, 5 à partir de 1 à 3?

. . .

4. Dépiler l'élément, le copier, puis l'empiler à nouveau.
5. Dépiler jusqu'à ce que la pile soit vide, puis empiler à nouveau.

. . .

## Existe en deux goûts

* Pile avec ou sans limite de capacité (à concurrence de la taille de la
mémoire).

# Les piles (3/5)

## Implémentation

* Jusqu'ici on n'a pas du tout parlé d'implémentation (d'où le nom de structure
  abstraite).
* Pas de choix unique d'implémentation.

## Quelle structure de données allons nous utiliser?

. . .

Et oui vous avez deviné: un tableau!

## La structure: de quoi avons-nous besoin (pile de taille fixe)?

. . .

```C
#define MAX_CAPACITY 500
typedef struct _stack {
    int data[MAX_CAPACITY]; // les données
    int top;                // indice du sommet
} stack;
```

# Les piles (4/5)

## Initialisation

. . .

```C
void stack_init(stack *s) {
    s->top = -1;
}
```

## Est vide?

. . .

```C
bool stack_is_empty(stack s) {
    return s.top == -1;
} 
```

## Empiler (ajouter un élément au sommet)

. . .

```C
void stack_push(stack *s, int val) {
    s->top += 1;
    s->data[s->top] = val;
}
```

# Les piles (5/5)

## Dépiler (enlever l'élément du sommet)

. . .

```C
int stack_pop(stack *s) {
    s->top -= 1;
    return s->data[s->top+1];
}
```

## Jeter un oeil (regarder le sommet)

. . .

```C
int stack_peek(stack s) {
    return s.data[s.top];
}
```

## Quelle est la complexité de ces opérations?

. . .

## Voyez-vous des problèmes potentiels avec cette implémentation?

. . .

* Empiler avec une pile pleine.
* Dépiler avec une pile vide.
* Jeter un oeil au sommet d'une pile vide.

# Gestion d'erreur, level 0

* Il y a plusieurs façon de traiter les erreur:
    * Ne rien faire (laisser la responsabilité à l'utilisateur).
    * Faire paniquer le programme (il plante plus ou moins violemment).
    * Utiliser des codes d'erreurs.

## La panique

* En C, on a les `assert()` pour faire paniquer un programme.


# Assertions (1/3)

```C
#include <assert.h>
void assert(int expression);
```

## Qu'est-ce donc?

- Macro permettant de tester une condition lors de l'exécution d'un programme:
  - Si `expression == 0`{.C} (condition fausse), `assert()`{.C} affiche un message d'erreur sur `stderr`{.C} et termine l'exécution du programme.
  - Sinon l'exécution se poursuit normalement.
  - Peuvent être désactivés à la compilation avec `-DNDEBUG` (équivalent à `#define NDEBUG`)

## À quoi ça sert?

- Permet de réaliser des tests unitaires.
- Permet de tester des conditions catastrophiques d'un programme.
- **Ne permet pas** de gérer les erreurs.

# Assertions (2/3)

<!-- \footnotesize -->

## Exemple

```C
#include <assert.h>
void stack_push(stack *s, int val) {
    assert(s->top < MAX_CAPACITY-1);
    s->top += 1;
    s->data[s->top] = val;
}
int stack_pop(stack *s) {
    assert(s->top >= 0);
    s->top -= 1;
    return s->data[s->top+1];
}
int stack_peek(stack *s) {
    assert(s->top >= 0);
    return s->data[s->top];
}
```

# Assertions (3/3)

## Cas typiques d'utilisation

- Vérification de la validité des pointeurs (typiquement `!= NULL`{.C}).
- Vérification du domaine des indices (dépassement de tableau).

## Bug vs. erreur de *runtime*

- Les assertions sont là pour détecter les bugs (erreurs d'implémentation).
- Les assertions ne sont pas là pour gérer les problèmes externes au programme (allocation mémoire qui échoue, mauvais paramètre d'entrée passé par l'utilisateur, ...).

. . .

- Mais peuvent être pratiques quand même pour ça...
- Typiquement désactivées dans le code de production.
