import itertools
from time import time

def generer(contraintes, taille, liste, grille, ligne):
    marge = "  " * ligne
    for permutation in itertools.permutations(liste):
        grille[ligne] = list(permutation)
        if ligne == taille-1:
            resultat = tester_validite_generale(contraintes, taille, grille)
            if resultat:
                afficher(grille)
                return
        else:
            generer(contraintes, taille, liste, grille, ligne+1)

def transposer(taille, grille):
    resultat = []
    for colonne in range(taille):
        nouvelle_ligne = []
        for ligne in range(taille):
            nouvelle_ligne.append(grille[ligne][colonne])
        resultat.append(nouvelle_ligne)
    return resultat

def tester_validite_verticale(contraintes, taille, grille):
    # on vérifier que les colonnes sont bien des permutations de [1.. n]
    transposee = transposer(taille, grille)
    indice = 0
    contraintes_decalees = contraintes[:]
    contraintes_decalees.pop(0)
    for ligne in transposee:
        ens = set(ligne)
        if len(ens) < taille:
            return False
        validite_contraintes = validite_ligne(ligne, contraintes_decalees, indice)
        if not validite_contraintes:
            return False
        indice += 1
    return True

def tester_contraintes_lignes(contraintes, taille, grille):
    for num_ligne in range(taille):
        ligne = grille[num_ligne]
        if not validite_ligne(ligne, contraintes, num_ligne):
            return False
    return True

def tester_contraintes_colonnes(contraintes, taille, grille):
    for num_colonne in range(taille):
        colonne = extraire_colonne(grille, num_colonne)
        if not validite_colonne(colonne, contraintes, num_colonne):
            return False
    return True

def tester_validite_generale(contraintes, taille, grille):
    if not tester_validite_verticale(contraintes, taille, grille):
        return False
    if not tester_contraintes_lignes(contraintes, taille, grille):
        return False
    return tester_contraintes_colonnes(contraintes, taille, grille)

def extraire_colonne(grille, num_colonne, nb_elements = None):
    if nb_elements is None:
        nb_elements = len(grille)
    retour = [0] * nb_elements
    for ligne in range(0, nb_elements):
        retour[ligne] = grille[ligne][num_colonne]
    return retour

def afficher(grille):
    print("-" * (2 * len(grille)))
    for ligne in grille:
        for case in ligne:
            print(case, end=' ')
        print()
        
def validite_gauche(ligne, contrainte):
    visu_gauche = 1
    maxi = ligne[0]
    for i in range(1,len(ligne)):
        if ligne[i] > maxi:
            visu_gauche += 1
            maxi = ligne[i]
    if visu_gauche != contrainte:
        return False
    return True

def validite_droite(ligne, contrainte):
    visu_droite = 1
    maxi = ligne[-1]
    for i in range(-2,-len(ligne)-1, -1):
        if ligne[i] > maxi:
            visu_droite += 1
            maxi = ligne[i]
    if visu_droite != contrainte:
        return False
    return True

def validite_ligne(ligne, contraintes, num_ligne):
    contrainte_gauche = contraintes[0][num_ligne]
    contrainte_droite = contraintes[2][num_ligne]
    if not contrainte_gauche is None and not validite_gauche(ligne, contrainte_gauche):
        return False
    if not contrainte_droite is None:
        return validite_droite(ligne, contrainte_droite)
    return True

def validite_haute_potentielle(contrainte, colonne):
    visu_haut = 1
    maxi = colonne[0]
    for i in range(1,len(colonne)):
        if colonne[i] > maxi:
            visu_haut += 1
            maxi = colonne[i]
    if visu_haut > contrainte:
        return False
    return True

def validite_haute_finale(contrainte, colonne):
    visu_haut = 1
    maxi = colonne[0]
    for i in range(1,len(colonne)):
        if colonne[i] > maxi:
            visu_haut += 1
            maxi = colonne[i]
    if visu_haut != contrainte:
        return False
    return True

def validite_basse_finale(contrainte, colonne):
    visu_bas = 1
    maxi = colonne[-1]
    for i in range(-2, -len(colonne)-1, -1):
        if colonne[i] > maxi:
            visu_bas += 1
            maxi = colonne[i]
        if visu_bas != contrainte:
            return False
    return True

def validite_colonne(colonne, contraintes, num_colonne):
    contrainte_haut = contraintes[1][num_colonne]
    contrainte_bas = contraintes[3][num_colonne]
    if num_colonne < len(colonne) - 1:
        if not contrainte_haut is None:
            return validite_haute_potentielle(contrainte_haut, colonne)
        else:
            return True
    else:
        if not contrainte_haut is None and not validite_haute_finale(contrainte_haut, colonne):
            return False
        if not contrainte_bas is None:
            return validite_basse_finale(contrainte_bas, colonne)
        return True
    
######################################################
#             Quelques cas de test
######################################################
def creer3():
    taille = 3
    grille = []
    for i in range(taille):
        grille.append([0] * taille)
    liste = [i for i in range(1, taille+1)]
    generer([[None, None, None],\
             [1, None, None],\
             [2, 1, None],\
             [None, None, None]\
    ], taille, liste, grille, 0)

def creer4():
    taille = 4
    grille = []
    for i in range(taille):
        grille.append([0] * taille)
    liste = [i for i in range(1, taille+1)]
    generer([[None, 2, 3, None],\
             [3, None, 2, None],\
             [None, 1, None, 3],\
             [None, 3, None, None]\
    ], taille, liste, grille, 0)

def creer5():
    taille = 5
    grille = []
    for i in range(taille):
        grille.append([0] * taille)
    liste = [i for i in range(1, taille+1)]
    generer([[3, None, 2, None, 4],\
             [2, None, 1, 2, None],\
             [None, 3, 1, 3, None],\
             [None, None, None, None, None]\
    ], taille, liste, grille, 0)
    

def calcTempsFonction(f):
      t1 = time()
      f()
      t2 = time()
      return t2 - t1