ROUGE = 1
BLEU = 2
VERT = 3
JAUNE = 4
OEUFS = [ROUGE, BLEU, VERT, JAUNE,\
         ROUGE, BLEU, VERT, JAUNE,\
         ROUGE, BLEU, VERT, JAUNE,\
         ROUGE, BLEU, VERT, JAUNE]

NB_OEUFS = 16

#une contrainte est représentée par un couple (couleur, nombre)
DEFI_15 = [(ROUGE, 2), (BLEU, 3), (ROUGE, 2),\
           (JAUNE, 3), (BLEU, 3), (JAUNE, 4),\
           (BLEU, 1), (JAUNE, 1), (JAUNE, 1),\
           (JAUNE, 2), (ROUGE, 4), (BLEU, 3)]
DEFI_19 = [(ROUGE, 2), (VERT, 2), (JAUNE, 3),\
           (BLEU, 2), (VERT, 3), (BLEU, 2),\
           (BLEU, 3), (JAUNE, 2), (JAUNE, 1),\
           (JAUNE, 1), (BLEU, 4), (ROUGE, 4)]
INDICE_CONTRAINTE_L1 = 0
INDICE_CONTRAINTE_L2 = 1
INDICE_CONTRAINTE_L3 = 2
INDICE_CONTRAINTE_L4 = 3
INDICE_CONTRAINTE_L12 = 4
INDICE_CONTRAINTE_L34 = 5
INDICE_CONTRAINTE_C1 = 6
INDICE_CONTRAINTE_C2 = 7
INDICE_CONTRAINTE_C3 = 8
INDICE_CONTRAINTE_C4 = 9
INDICE_CONTRAINTE_C12 = 10
INDICE_CONTRAINTE_C34 = 11

def resoudre(contraintes, grille, oeufs_disponibles):
    if len(oeufs_disponibles) == 0:
        print("TROUVE !")
        afficher(grille)
        return True
    for indices_oeufs in generateur_ligne(oeufs_disponibles):
        oeufs_restant = prelever_oeufs(oeufs_disponibles, indices_oeufs)
        nouvelle_grille = creer_nouvelle_grille(grille, oeufs_disponibles, indices_oeufs)
        
        if not nouvelle_ligne_correcte(nouvelle_grille, contraintes):
            continue
        if not verifier_verticalement(nouvelle_grille, contraintes):
            continue
        if resoudre(contraintes, nouvelle_grille, oeufs_restant):
            return True
    return False

def creer_nouvelle_grille(grille, oeufs_disponibles, indices):
    nouvelle_ligne = list(map(lambda x: oeufs_disponibles[x], indices))
    nouvelle_grille = grille[:]
    nouvelle_grille.append(nouvelle_ligne)
    return nouvelle_grille
    
def prelever_oeufs(oeufs_disponibles, indices_prelevement):
    indices_tries = sorted(indices_prelevement)
    oeufs_restant = oeufs_disponibles[:indices_tries[0]] +\
        oeufs_disponibles[indices_tries[0]+1:indices_tries[1]] +\
        oeufs_disponibles[indices_tries[1]+1:indices_tries[2]] +\
        oeufs_disponibles[indices_tries[2]+1:indices_tries[3]] +\
        oeufs_disponibles[indices_tries[3]+1:]
    return oeufs_restant
    
def afficher(grille):
    for ligne in grille:
        for case in ligne:
            print(car(case),end='')
        print()

def car(nombre):
    conversion = [" ", "R", "B", "V", "J"]
    return conversion[nombre]

def nouvelle_ligne_correcte(grille, contraintes):
    indice_ligne = len(grille) - 1
    correction = verifier_ligne(grille[indice_ligne], contraintes[indice_ligne])
    if not correction:
        return False
    if indice_ligne % 2 == 1:
        contrainte_bloc = contraintes[4 + indice_ligne //2]
        correction2 = verifier_bloc_horizontal(grille[indice_ligne-1:indice_ligne+1], contrainte_bloc)
        if not correction2:
            return False
    return True

def verifier_ligne(ligne, contrainte):
    resultat = ligne.count(contrainte[0]) == contrainte[1]
    return resultat

def verifier_bloc_horizontal(bloc, contrainte):
    fusion = bloc[0] + bloc[1]
    resultat = fusion.count(contrainte[0]) == contrainte[1]
    return resultat

def essayer15():
    resoudre(DEFI_15, [], OEUFS)

def essayer19():
    resoudre(DEFI_19, [], OEUFS)

def verifier_colonnes(grille, contraintes):
    derniere_ligne = len(grille) == 4
    correct = True
    for num_colonne in range(4):
        colonne = extraire_colonne(grille, num_colonne)
        contrainte_colonne = contraintes[num_colonne + 6]
        if derniere_ligne:
            correct = correct and colonne.count(contrainte_colonne[0]) == contrainte_colonne[1]
        else:
            correct = correct and colonne.count(contrainte_colonne[0]) <= contrainte_colonne[1]
        if not correct:
            return False
    return True

def verifier_bloc_vertical(grille, contraintes, num_bloc):
    derniere_ligne = len(grille) == 4
    fusion = extraire_colonne(grille, num_bloc * 2) +\
        extraire_colonne(grille, num_bloc * 2 + 1)
    contrainte_bloc = contraintes[10 + num_bloc]
    if derniere_ligne:
        correct = fusion.count(contrainte_bloc[0]) == contrainte_bloc[1]
    else:
        correct = fusion.count(contrainte_bloc[0]) <= contrainte_bloc[1]
    if not correct:
        return False
    return True
    
def verifier_blocs_verticaux(grille, contraintes):
    for num_bloc in range(2):
        if not verifier_bloc_vertical(grille, contraintes, num_bloc):
            return False
    return True

def verifier_verticalement(grille, contraintes):
    if not verifier_colonnes(grille, contraintes):
        return False
    return verifier_blocs_verticaux(grille, contraintes)

def extraire_colonne(grille, num_colonne):
    retour = [0] * len(grille)
    for indice in range(len(retour)):
        retour[indice] = grille[indice][num_colonne]
    return retour

def generateur_ligne(oeufs_disponibles):
    configurations_essayees = set()
    for oeuf1 in range(len(oeufs_disponibles)):
        for oeuf2 in range(len(oeufs_disponibles)):
            if oeuf2 == oeuf1:
                continue
            for oeuf3 in range(len(oeufs_disponibles)):
                if oeuf3 == oeuf2 or oeuf3 == oeuf1:
                    continue
                for oeuf4 in range(len(oeufs_disponibles)):
                    if oeuf4 == oeuf3 or oeuf4 == oeuf2 or oeuf4 == oeuf1:
                        continue
                    representation = oeufs_disponibles[oeuf1] +\
                        oeufs_disponibles[oeuf2] * 4 +\
                        oeufs_disponibles[oeuf3] * 16 +\
                        oeufs_disponibles[oeuf4] * 64
                    if representation in configurations_essayees:
                        continue
                    configurations_essayees.add(representation)
                    yield [oeuf1, oeuf2, oeuf3, oeuf4]