Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Escreva um programa backtracking para determinar o número de quadrados latinos de ordem \(n\). Rode o seu algoritmo para \(n=2,3,4,\) e \(5\).

0 votos
9 visitas
perguntada Set 4 em Programação Computacional por Thiago Trafane (21 pontos)  
editado Set 4 por Thiago Trafane

Ex. 4.13 do Cap. 4 do livro "Combinatorial Algorithms: Generation, Enumeration, and Search" de Donald L. Kreher and Douglas R. Stinson.

Compartilhe

1 Resposta

0 votos
respondida Set 4 por Thiago Trafane (21 pontos)  
editado Set 4 por Thiago Trafane

Um quadrado latino de ordem \(n\) é uma matriz \(n \times n\) preenchida com \(n\) elementos distintos de tal forma que cada elemento aparece no máximo uma única vez em cada linha ou coluna. Um quadrado latino é dito reduzido quando os \(n\) elementos aparecem em sua forma natural na primeira linha e na primeira coluna. Isto é, sendo os elementos o conjunto \(\{1,2,...,n\}\), teremos que em um quadrado latino reduzido os vetores linha da primeira linha e da primeira coluna serão iguais a \( \left[ \begin{array}{cccc} 1 & 2 & ... & n \end{array} \right] \).

O objetivo desse exercício é criar um programa backtracking para determinar o número de quadrados latinos de ordem \(n\). Para isso, eu criei a função latin_square usando o código mostrado abaixo, que demanda a importação do pacote numpy.

# 0) Importando pacotes
import numpy as np

# 1) Definindo a função que identifica os quadrados latinos (n>=2)
def latin_square(n):          

    # 1.1) Construindo matriz quadrado latino reduzido (RLS) e lista de resultados (res)
    RLS = np.empty((n,n))
    RLS[0,:] = range(1,n+1)
    RLS[:,0] = range(1,n+1)        
    res = []

    # 1.2) Função auxiliar com backtracking
    def _latin_square_aux(n,lin,col):

        # Se a matriz RLS estiver toda preenchida, adicione-a aos resultados (res)
        if (lin == n):
            RLS_atual = RLS.copy()
            res.append(RLS_atual)

        # Caso contrário, vamos construí-la
        else:
            for i in range(n):      
                if (i+1 not in RLS[lin,0:col]) and (i+1 not in RLS[0:lin,col]): #Se o elemento não tiver nem na linha e nem na coluna, adicione-o
                    RLS[lin,col] = i+1

                    if col == n-1: #Atualizando linha e coluna caso esteja na última coluna
                        lin_atual = lin+1
                        col_atual = 1
                    else: #Atualizando linha e coluna caso não esteja na última coluna
                        lin_atual = lin
                        col_atual = col+1

                    _latin_square_aux(n,lin_atual,col_atual) #Recursão

    # 1.3) Chamando a função auxiliar e criando o output da função latin_square
    _latin_square_aux(n,1,1)                
    return res

Como se vê, o código que constrói a função é dividido em três partes. Na primeira parte, eu crio a matriz quadrado latino reduzido (RLS) e a lista de resultados (res) que serão preenchidas. Resolvi separar essa parte da parte que usa backtracking (parte 2) para ficar explícito que esses objetos são carregados em todas as recursões. Na segunda parte, eu crio uma função auxiliar com backtracking. Na terceira parte, eu apenas chamo a função auxiliar e defino o output da função principal latin_square como res, que é a lista contendo todos os quadrados latinos reduzidos existentes para a dimensão \(n\) escolhida.

Assim, a parte principal do programa está na função auxiliar definida na parte 2 (função _latin_square_aux). Inicialmente, essa função avalia se a matriz RLS foi toda preenchida. Se for o caso, ele adiciona essa matriz à lista de resultados res. Esse é o trecho que garante o fim da recursão em caso de sucesso do caminho trilhado.

Caso a matriz RLS não esteja totalmente preenchida, ele vai avaliar a inclusão de cada elemento na posição atual (linha = lin e coluna = col). Caso o elemento avaliado não esteja nem na linha nem na coluna atuais, esse elemento é adicionado à posição atual e o programa chama novamente a função auxiliar na próxima posição (coluna seguinte na mesma linha ou, caso estejamos na última coluna, linha seguinte na coluna 1). Se em algum momento uma trilha não for bem sucedida, isto é, não houver um elemento para incluir na posição atual, a recursão para de ser chamada antes da matriz ser totalmente preenchida e, logo, essa trilha é descartada. Portanto, apenas as trilhas bem sucedidas são adicionadas à lista de resultados res.

Com base na função latin_square, podemos gerar os resultados solicitados para \(n=2,3,4,\) e \(5\) usando o programa abaixo, que armazena os resultados no dicionário n_RLS. Como o output da função latin_square é a lista contendo todos os quadrados latinos reduzidos existentes, devo identificar o tamanho dessa lista (função len) para obter o número de quadrados. Vale ressaltar que para o exercício aqui apresentado, eu poderia ter definido o número de quadrados diretamente como o output da função, mas isso limitaria desnecessariamente o potencial da função latin_square ao impossibilitar a identificação dos quadrados latinos reduzidos possíveis.

# 2) Gerando os resultados
if __name__ == '__main__':      

    n_RLS = {} #Dicionário contendo as respostas
    for n in range(2,6):
        n_RLS[n] = len(latin_square(n))

Os resultados apontam para 1, 1, 4 e 56 quadrados latinos reduzidos para \(n\) igual a 2, 3, 4 e 5, respectivamente.

...