'''
   Dizemos que uma matriz inteira a com n linhas e n colunas e' um
   quadrado latino de ordem n se em cada linha e em cada coluna 
   aparecem todos os inteiros 1, 2, 3, ..., n; ou seja, cada linha 
   e cada coluna e' uma permutacao dos inteiros 1, 2, 3, ..., n.

   - Escreva uma funcao que recebe uma lista com n inteiros e 
     retorna True, se nessa lista ocorrem todos os inteiros de 1 a n;
     e retorna False, em caso contrario.
   - Escreva um programa que, dada uma matriz inteira a com n linhas e
     n colunas, verifica se a matriz a e' um quadrado latino de ordem n.
'''

def main():
    # ler e criar a matriz
    a_mat = leCriaMatriz()
    
    print()
    imprime_matriz(a_mat)
   
    print()
    if quadrado_latino(a_mat):
        print("A matriz eh um quadrado latino.")
    else:
        print("A matriz nao eh um quadrado latino.")
        
#-------------------------------------------------------------------------

def leCriaMatriz():
    ''' ( ) -> matriz 

    Le do teclado o numero nlin de linhas, o numero ncol de colunas,
    e os elementos (inteiros) de uma matriz de dimensao (nlin x ncol).
    A funcao cria e retorna a matriz lida.
    '''
    
    nlin = int(input("Digite o numero de linhas: "))
    ncol = int(input("Digite o numero de colunas: "))

    # ler e criar a lista matriz (nlin x ncol)
    matriz = []
    for i in range(nlin):
        #  ler e criar uma lista para a linha i
        linha = [] 
        for j in range(ncol):
            num = int(input("Digite um inteiro para a posição [%d][%d]: "
                                                                %(i, j)))
            linha.append(num)

        # inserir a lista linha no final da lista matriz        
        matriz.append(linha)       

    return matriz

#-----------------------------------------------------------------

def imprime_matriz(matriz):
    ''' (matriz) -> NoneType

    Recebe e imprime uma matriz de inteiros.
    '''
    
    nlin = len(matriz)
    ncol = len(matriz[0])

    print("Matriz com %d linhas e %d colunas" %(nlin, ncol))
    print()
    
    for i in range(nlin):
        # imprimir os elementos da linha i
        for j in range(ncol): 
            print("%6d" %(matriz[i][j]), end='')  ### veja como fazer para nao mudar de linha
        print()   #### importante para mudar de linha <===========
    
#---------------------------------------------------------------

def permutacao(lista):
    ''' (list) -> bool
    
    Recebe uma lista de inteiros. Seja n o seu número de elementos da lista
    Retorna True se na lista ocorrem todos os inteiros de 1 a n.
    Em caso contrário, retorna False.
    '''

    n = len(lista)
    
    ocorre = cria_lista(n+1, False)  # note que foi criada uma lista com comprimento n+1,
                                     # seus indices variam de 0 a n (fica mais conveniente
                                     # para a ideia a seguir)
    # A lista ocorre eh criada e inicializada com False.
    # Para cada i, 1<=i<=n, ocorre[i] sera' True ou False, dependendo,
    # respectivamente, se i ja' ocorreu ou nao ocorreu na lista.
        
    # Vamos supor inicialmente que lista satisfaz a propriedade.
    satisfaz = True
    
    i = 0
    while i < n and satisfaz:
        if 1 <= lista[i] <= n:
            if ocorre[lista[i]] == False:  # poderia escrever  if not ocorre[lista[i]]:
                                        
                ocorre[lista[i]] = True   
                i += 1
            else:
                satisfaz = False  # lista[i] ocorre mais de uma vez 
        else:
            satisfaz = False  # lista contem elementos fora do intervalo 1, ...,n 
        
    return satisfaz

#-----------------------------------------------------------------------------

def quadrado_latino(matriz):
    ''' (matriz) -> bool

    Recebe uma matriz e retorna True se a matriz é um quadrado latino;
    em caso contrario, retorna False.
    Obs. A funcao supoe que a matriz eh quadrada.
    '''

    n = len(matriz)

    # Supomos inicialmente que a matriz eh um quadrado latino
    latino = True

    # verificar se cada linha eh uma permutacao dos inteiros de 1 a n        
    i = 0
    while i < n and latino:
        # matriz[i] eh uma lista com os elementos da linha i da matriz
        if permutacao(matriz[i]):
            i += 1
        else:
            latino = False

    # verificar se cada coluna eh uma permutacao dos inteiros de 1 a n
    # criar uma lista para armazenar os elementos de cada coluna da matriz
     
    j = 0
    while j < n and latino:
        # constrói lista_coluna com os elementos da coluna j 
        lista_coluna = []
        for i in range(n):
            lista_coluna.append(matriz[i][j])       
            
        if permutacao(lista_coluna):
            j += 1 # atualiza j para testar nova coluna 
        else:
            latino = False

    return latino

#-------------------------------------------------------------------------------

def cria_lista(n, valor):
    ''' (int, valor) -> list

    Cria uma lista com n elementos, todos iguais a valor.
    Retorna a lista criada.
    '''
    
    lista = []
    for i in range(n):
        lista.append(valor)

    return lista

#-----------------------------------------------------------------------    

main()