// Exo de demonstration du backtracking
// Problème : afficher toutes les codes (ou arrangements) possibles de N chiffres.
//            On veut 0 < N <= 20 et les chiffres seront restreints a {0,1,2}


// on inclus stdlib pour faire des allocations dynamiques
#include <stdio.h>
#include <stdlib.h>

// déclarations préliminaires des fonctions auxilliaires
void allouer(int **tab, int N);
void generer_code(int *tab, int N);
void afficher_code(int *tab, int N);


int main() {
  int N;
  int *tab=0; // pointeur sur le tableau contenant le code (nul au départ)
  
  // saisir la taille du code
  do {
    printf("Saisir la taille du code (entre 1 et 20): ");
    scanf("%d",&N);
  } while (N < 0 && N > 20);

  // allouer
  allouer(&tab, N); // tab va changer => passage par adresse
  
  // generer les codes
  generer_code(tab, N);

  return 0;
} // main


// allouer le tableau de code
void allouer(int **ptab, int N) {
  *ptab = (int*) malloc(N * sizeof(int));
  if (!*ptab) { // *ptab == 0 => allocation impossible
    printf("Problème d'allocation !\n");
    exit(1);
  }
} // allouer


// generer les codes avec backtracking
void generer_code(int *tab, int N) {
  // initialiser le tableau
  int i;
  for (i=0; i < N; i++)
    tab[i]=0;
  
  // parcourir les codes
  int pos; // position dans le code du chiffre a modifier
  do {
    // sortir le code courant
    afficher_code(tab, N);
    // passer au suivant
    pos=N-1; // position du dernier chiffre
    tab[pos] += 1; // on incremente le chiffre
    // backtracking :
    //   y a t-il bouclage de 2 vers 0 ?
    //   si oui bouger le chiffre precedent
    //   
    while (pos >= 0 && tab[pos] == 3) {
      tab[pos] = 0; // boucler le chiffre sur 0 
      pos -= 1; // passer à la position precedente
      tab[pos] += 1; // on incremente le chiffre precedent
    }
    // si pos < 0 alors plus de backtrack possible, on termine
  } while (pos >= 0);

} // generer_code


// afficher le code a l'ecran
void afficher_code(int *tab, int N) {
  int i;
  for (i=0; i< N; i++)
    printf("%d", tab[i]);
  printf("\n");
} // afficher_code