#include <stdio.h>

//Suponha que já conhecemos uma solucao de tamanho 4, obtido pela heuristica por exemplo
int melhor = 4;

void bnb(int posicaoAT, int * vet) {

  for(int cont = 0; cont < posicaoAT; cont++) {
    //verificar se a solucao eh valida. Aqui só estamos imprimindo
    printf("%d ",vet[cont]);
  }
  printf("\n");

  //Suponha que encontramos uma solucao nesse caso a (1,2) e ela tem tamanho 2
  if(posicaoAT == 2 && vet[0] == 1 && vet[1] == 2){
    //é uma solucao de tamanho 2	
    //atualiza o meu limitante superior
    melhor = 2;
    return;
  }
  
  //Devo tentar solucoes mais longas?
  //Se nao fizer sentido tentar solucoes mais longas
  //faca uma poda por limitante	
  if(posicaoAT >= melhor - 1) {
    return;
  }

  //Nao tendo mais podas, temos que testar todas as opcoes
  //poderiamos usar um criterio melhor, mas vamos tentar as
  //cores nas ordem mesmo 0, 1, 2, 3, 4, 5
  for(int cont = 0; cont < 6; cont++) {
    //Naum preciso gerar a mesma cor.
    if(posicaoAT > 0 && vet[posicaoAT - 1] == cont) continue;
    vet[posicaoAT] = cont;
    bnb(posicaoAT+1, vet);
  }
  return;
}

int main(void) {
  int vet[3];

  bnb(0, vet);
  return 0;
}