Um quadrado latino de ordem \(n\) é uma matriz quadrada \(n\times n\) tal que cada coluna e cada linha contém exatamente uma vez cada algarismo \(k=1,...,n\).
Um exemplo clássico de quadrado latino utiliza as cartas de um baralho.
Tomando quatro cartas de cada naipe (Paus, Ouros, Copas e Espadas) e arranjando-as em uma matriz \(4\times4\) de modo que cada naipe aparece exatamente uma vez em cada linha e uma vez em cada coluna, obtemos:
Podemos construir outro quadrado latino tomando quatro cartas de cada valor: Ás, Rei, Dama e Valete. Uma possibilidade é:
Dois quadrados latinos de ordem \(n\) são chamados de ortogonais se a sobreposição dos dois quadrados resulta em uma matriz de ordem \(n\) cujas entradas são os pares ordenados formados pelas entradas de cada quadrado e tal que cada par ordenado aparece exatamente uma vez na matriz.
No exemplo das cartas, é possível dispor as 16 cartas em uma matriz \(4\times4\) de modo que cada linha e cada coluna contém todos os quatro valores e todos os quatro naipes:
Os naipes e valores no exemplo anterior podem ser substituídos por quaisquer valores, simbolos ou letras. O termo "quadrado latino" foi inspirado no trabalho de Leonhard Euler, que usou caracteres latinos em seus estudos sobre o tema. Dois quadrados latinos ortogonais recebem o nome de quadrado "greco-latino" devido ao uso dos caracteres do alfabeto latino em um dos quadrados e do alfabeto grego no outro.
O exercício proposto no livro parte de um quadrado greco-latino formado pelos quadrados
Este quadrado greco-latino deve ser estendido de modo a incorporar um terceiro quadrado latino formado com caracteres do alfabeto hebraico. Este terceiro quadrado deve ser mutuamente ortogonal a ambos os quadrados já definidos. Isto significa que nenhum par de caracteres (latino, grego), (latino, hebraico) ou (grego-hebraico) aparece mais de uma vez quando os quadrados são sobrepostos dois a dois.
Já foi provado que no caso de quadrados \(4\times4\) existem apenas 3 quadrados que atendem à condição de ortogonalidade mútua. Logo, existe apenas uma possível disposição dos caracteres hebraicos em uma matriz que satisfaz à condição.
O código abaixo constrói quadrados latinos mutuamente ortogonais (Mutually Orthogonal Latin Squares - MOLS) de números, mas estes números podem ser posteriormente substituídos pelos caracteres gregos, latinos e hebraicos.
O primeiro passo para encontrar os MOLS é encontrar o primeiro quadrado latino. A função que gera este quadrado (latin_sq) começa com uma matriz \(4\times4\) de zeros. A ideia é pegar cada algarismo k=1,2,3,4 e testar cada posição da matriz que satisfaça às duas condições: não repetir o número na linha nem na coluna. Estas condições são testadas pelas funções "linhaOK" e "colunaOK", reunidas na função "position _ check" que verifica se ambas são satisfeitas (não basta apenas uma condição ser satisfeita). Se a posição é legal, ou seja, se satisfaz às condições e se a posição está disponível (se o valor que está na posição é zero), então podemos colocar o algarismo nesta posição. Caso contrário, testamos a próxima posição. O loop termina quando cada algarismo aparece exatamente uma vez em cada linha e cada coluna. Formamos assim o QUADRADO1.
O segundo passo é construir um segundo quadrado latino ortogonal ao QUADRADO 1. Para isso, precisamos verificar uma terceira condição: as coordenadas formadas pela sobreposição dos quadrados não podem se repetir. A função "coordinate_check" verifica se uma coordenada já aparece em uma lista de coordenadas que será construída à medida que as posições do segundo quadrado forem preenchidas. A função "ortogonal" gera uma matriz ortogonal a outra matriz que deve ser dada como argumento (no caso o argumento será o QUADRADO 1). Da mesma forma que na construção do primeiro quadrado latino, começamos com uma matriz \(4\times4\) de zeros. Iniciamos também com uma lista vazia de coordenadas que já existem na matriz de coordenadas. Pegamos cada algarismo e testamos cada posição primeiro para a condição de não repetição na linha e na coluna e depois para a condição de não repetição da coordenada. Se a posição é legal e está disponível, colocamos o algarismo nesta posição. Verificamos então se a coordenada formada nesta posição já existe em algum lugar da matriz de coordenadas. Se não existe, a condição é satisfeita e adicionamos esta coordenada à lista de coordenadas que já foram formadas. Se a coordenada já existe, retiramos o algarismo colocado na posição e testamos a próxima posição. Este algoritmo forma o QUADRADO2.
O terceiro passo é construir uma terceira matriz (QUADRADO3) que seja ao mesmo tempo ortogonal ao QUADRADO 1 e ao QUADRADO 2. Isto é feito com a função "MOLS_generator". O processo é semelhante: primeiro testamos se a posição satisfaz às duas restrições de não repetição em linhas e colunas, colocando o algarismo na posição se a condição é satisfeita. Desta vez, contudo, testamos duas vezes a coordenada formada. Primeiro testamos se a coordenada se repete na matriz formada pela sobreposição dos quadrados 1 e 3 e depois testamos se a coordenada formada se repete quando se sobrepõem os quadrados 2 e 3. Somente se a coordenada não se repete em ambos os casos podemos manter o algarismo nesta posição. Caso contrário retiramos e testamos a próxima posição.
A função "print_orthogonal_matrix" revela os quadrados latinos mutuamente ortogonais, assim como a matriz que sobrepõe os três quadrados.
import numpy as np
class MOLS:
@staticmethod
def linhaOK(matriz, linha, algarismo):
'''
Verifica se o algarismo já aparece na linha da matriz. Se não aparece: ok
'''
for l in range(4):
if matriz[linha][l]==algarismo:
return False
return True
@staticmethod
def colunaOK(matriz, coluna, algarismo):
'''
Verifica se o algarismo já aparece na coluna da matriz. Se não aparece: ok
'''
for c in range(4):
if matriz[c][coluna]==algarismo:
return False
return True
def position_check(self, matriz, linha, coluna, algarismo):
'''
Verifica ambas as condições (linha e coluna)
'''
if self.linhaOK(matriz, linha, algarismo)==True:
if self.colunaOK(matriz, coluna, algarismo)==True:
return True
return False
return False
def latin_sq(self):
'''
Gera um quadrado latino de ordem 4
'''
matriz=np.array([[0,0,0,0], [0,0,0,0], [0,0,0,0], [0,0,0,0]])
for e in range(1,5): #cada algarismo de 1 a 4
for lin in range(0,4): #para cada linha da matriz
for col in range(0,4): #para cada coluna da matriz
if self.position_check(matriz, lin, col, e) == True: #se a posição é "legal"
if matriz[lin][col]==0: # e se a posição está disponível
matriz[lin][col]=e #coloca o algarismo nesta posição
return matriz
@staticmethod
def coordinate_check(conj_coord, coordinate):
'''
Verifica se a coordenada já existe
conj_coord é uma lista de coordenadas que já estão na matriz de coordenadas
'''
if (coordinate in conj_coord):
return False
return True
def ortogonal(self, matrix):
'''
Constroi a matriz ortogonal a uma matriz dada
'''
matrix1=matrix #a matriz em relação à qual será construída a matriz ortogonal
matrix2=np.array([[0,0,0,0], [0,0,0,0], [0,0,0,0], [0,0,0,0]]) #inicializa a matriz ortogonal - vazia
conj_coordinates=[] #lista de coordenadas que já existem. Começa vazia.
for f in range (1,5): #para cada algarismo de 1 a 4
for linha in range (0,4): #para cada linha
for coluna in range(0,4): #para cada coluna
if self.position_check(matrix2, linha, coluna, f) == True: #se a posição é "legal"
if matrix2[linha][coluna]==0: # e se a posição está disponível
matrix2[linha][coluna]=f # coloca o algarismo nesta posição
if self.coordinate_check(conj_coordinates, [matrix1[linha][coluna],matrix2[linha][coluna]]) == True:
# se a coordenada formada é "legal"
conj_coordinates.append([matrix1[linha][coluna],matrix2[linha][coluna]])
#adiciona à lista de coordenadas que já existem
else:
matrix2[linha][coluna]=0 #se a coordenada é "ilegal", retira o algarismo colocado
return matrix2
def MOLS_generator(self, matrix1, matrix2):
'''
Gera quadrados latinos mutuamente ortogonais (Mutually Orthogonal Latin Squares)
'''
matrix1=self.latin_sq() #gera o primeiro quadrado latino
matrix2=self.ortogonal(matrix1) #gera o segundo quadrado latino, ortogonal ao primeiro
matrix3=np.array([[0,0,0,0], [0,0,0,0], [0,0,0,0], [0,0,0,0]]) #inicializa o terceiro quadrado latino - vazio
conj_coordinates1=[] #lista de coordenadas que já existem quadrados 1 e 3
conj_coordinates2=[] #lista de coordenadas que já existem quadrados 2 e 3
for f in range (1,5): #para cada algarismo de 1 a 4
for linha in range (0,4): #para cada linha
for coluna in range(0,4): #para cada coluna
if self.position_check(matrix3, linha, coluna, f) == True: #se a posição é "legal"
if matrix3[linha][coluna]==0: # e se a posição está disponível
matrix3[linha][coluna]=f # coloca o algarismo nesta posição
if (self.coordinate_check(conj_coordinates1, [matrix1[linha][coluna],matrix3[linha][coluna]]) == True) and ((self.coordinate_check(conj_coordinates2, [matrix2[linha][coluna],matrix3[linha][coluna]]) == True)):
# se a coordenada formada é "legal"
conj_coordinates1.append([matrix1[linha][coluna],matrix3[linha][coluna]])
conj_coordinates2.append([matrix2[linha][coluna],matrix3[linha][coluna]])
#adiciona à lista de coordenadas que já existem
else:
matrix3[linha][coluna]=0 #se a coordenada é "ilegal", retira o algarismo colocado
return matrix3
def print_orthogonal_matrix(self):
'''
Gera a matriz ortogonal
'''
quadrado=np.array([[0,0,0,0], [0,0,0,0], [0,0,0,0], [0,0,0,0]])
matrix1=self.latin_sq()
print("Quadrado Latino #1:")
print(matrix1)
matrix2=self.ortogonal(matrix1)
print("Quadrado Latino #2: ")
print(matrix2)
matrix3=self.MOLS_generator(matrix1, matrix2)
print("Quadrado Latino #3: ")
print(matrix3)
orthogonal_matrix=[[[0,0,0],[0,0,0],[0,0,0],[0,0,0]], #inicia com uma matriz de zeros.
[[0,0,0],[0,0,0],[0,0,0],[0,0,0]], #cada entrada da matriz é uma lista com 3 valores
[[0,0,0],[0,0,0],[0,0,0],[0,0,0]],
[[0,0,0],[0,0,0],[0,0,0],[0,0,0]]]
for i in range(0,4):
for j in range(0,4):
orthogonal_matrix[i][j][0] = matrix1[i][j] # o primeiro valor vem da primeira matriz
orthogonal_matrix[i][j][5] = matrix2[i][j] # o segundo valor vem da segunda matriz
orthogonal_matrix[i][j][6] = matrix3[i][j] # o terceiro valor vem da terceira matriz
print("Matriz de MOLS")
print(orthogonal_matrix)
Usando esta classe:
if __name__ == '__main__':
LatinSquares=MOLS()
LatinSquares.print_orthogonal_matrix()
obtemos:
Quadrado Latino #1:
[[1 2 3 4]
[2 1 4 3]
[3 4 1 2]
[4 3 2 1]]
Quadrado Latino #2:
[[1 2 3 4]
[3 4 1 2]
[4 3 2 1]
[2 1 4 3]]
Quadrado Latino #3:
[[1 2 3 4]
[4 3 2 1]
[2 1 4 3]
[3 4 1 2]]
Matriz de MOLS
[[[1, 1, 1], [2, 2, 2], [3, 3, 3], [4, 4, 4]],
[[2, 3, 4], [1, 4, 3], [4, 1, 2], [3, 2, 1]],
[[3, 4, 2], [4, 3, 1], [1, 2, 4], [2, 1, 3]],
[[4, 2, 3], [3, 1, 4], [2, 4, 1], [1, 3, 2]]]
É possível notar que o Quadrado Latino #2 representa o quadrado com as letras gregas da questão, fazendo \(\gamma=1, \delta=2, \beta=3, \alpha=4\). O Quadrado Latino #3 é aquele com as letras latinas, fazendo \(d=1, a=2, b=3, c=4\). O Quadrado Latino 1, então, deve ser aquele que possui os caracteres hebraicos. Fazendo as devidas substituições, o resultado é o quadrado greco-latino-hebraico da figura abaixo.
