import itertools
import numpy as np
from time import time

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

def validite_verticale(grille, taille, contraintes, num_ligne):
    for num_colonne in range(taille):
        colonne = extraire_colonne(grille, num_colonne, num_ligne+1)
        if not validite_colonne_regle(colonne):
            return False
        if not validite_colonne_contrainte_nord(colonne, contraintes[1][num_colonne]):
            return False
    return True

def validite_colonne_regle(colonne):
    return len(set(colonne)) == len(colonne)

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_colonnes_finale(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:
        validite_contraintes = validite_ligne(ligne, contraintes_decalees, indice)
        if not validite_contraintes:
            return False
        indice += 1
    return True

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_colonne_contrainte_nord(colonne, contrainte_haut):
    if not (contrainte_haut is None):
        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_haut:
            return False
    return True

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 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 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 calcTempsFonction(f):
      t1 = time()
      f()
      t2 = time()
      return t2 - t1