|
|
EXAMPLE
|
For n = 5,they are 2 main classes of Latin squares. One of them has representative M = [[1,2,3,4,5],[2,4,1,5,3],[3,5,4,2,1],[4,1,5,3,2],[5,3,2,1,4]], and it has 3 transversals; {M(1,1), M(5,2), M(3,3), M(2,4), M(4,5)}, {M(2,1), M(5,2), M(4,3), M(1,4), M(3,5)}, and {M(4,1), M(5,2), M(2,3), M(3,4), M(1,5)}. The other main class representative [[1,2,3,4,5],[2,3,4,5,1],[3,4,5,1,2],[4,5,1,2,3],[5,1,2,3,4]] has 15 transversals. Therefore, the minimum number of transversals in order 5 Latin squares is 3, i.e., a(5) = 3.
|
|
|
PROG
|
(MATLAB)
%This extracts entries from each column. For an example, if
%A=[1 2 3 4; 5 6 7 8; 9 10 11 12; 13 14 15 16], and if list = (2, 1, 4),
%this code extracts the second element in the first column, the first
%element in the second column, and the fourth element in the third column.
function [output] = extract(matrix, list)
for i=1:length(list)
output(i) = matrix(list(i), i);
end
end
%Searches matrix to find transversal and outputs the transversal.
function [output] = findtransversal(matrix)
n=length(matrix);
for i=1:n
partialtransversal(i, 1)=i;
end
for i=2:n
newpartialtransversal=[];
for j=1:length(partialtransversal)
for k=1:n
if (~ismember(k, partialtransversal(j, :)))&(~ismember(matrix(k, i), extract(matrix, partialtransversal(j, :))))
newpartialtransversal=[newpartialtransversal; [partialtransversal(j, :), k]];
end
end
end
partialtransversal=newpartialtransversal;
end
output=partialtransversal;
end
%Takes input of n^2 numbers with no spaces between them and converts it
%into an n by n matrix.
function [A] = tomatrix(input)
n=sqrt(floor(log10(input))+2);
for i=1:n^2
temp(i)=mod(floor(input/(10^(i-1))), 10);
end
for i=1:n
for j=1:n
A(i, j)=temp(n^2+1-(n*(i-1)+j));
end
end
A=A+ones(n);
end
|
