cours_8.md

title: "Backtracking et piles"
date: "2021-11-17"
patat:
  eval:
    tai:
      command: fish
      fragment: false
      replace: true
    ccc:
      command: fish
      fragment: false
      replace: true
  images:
    backend: auto
PPCM(36, 90):
36  < 90  // 36  + 36
72  < 90  // 72  + 36
108 > 90  // 90  + 90
108 < 180 // 108 + 36
144 < 180 // 144 + 36
180 = 180 // The End!
// on cherche i*m == j*m (i,j aussi petits que possibles)
int ppcm(int m, int n) {
    int mult_m = m, mult_n = n;
    while (mult_m != mult_n) {
        if (mult_m > mult_n) {
            mult_n += n;
        } else {
            mult_m += m;
        }
    }
    return mult_m;
}


bool board[n][n];
// 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);
// Calcule le nombre de solutions au problème des <n> reines
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
// Placer une reine et mettre à jour
placer_devant(board, ligne, colonne)
    // board est occupé à ligne/colonne
        // toutes les cases des colonnes
        //    suivantes sont mises à jour
// 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;
            }
        }
    }
}
// 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 prises_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;
        }
    }
}
#define MAX_CAPACITY 500
typedef struct _stack {
    int data[MAX_CAPACITY]; // les données
    int top;                // indice du sommet
} stack;
void stack_init(stack *s) {
    s->top = -1;
}
bool stack_is_empty(stack s) {
    return s.top == -1;
}
void stack_push(stack *s, int val) {
    s->top += 1;
    s->data[s->top] = val;
}
int stack_pop(stack *s) {
    s->top -= 1;
    return s->data[s->top+1];
}
int stack_peek(stack *s) {
    return s->data[s->top];
}