I wanted to point out that there seems to be biases even in the set it does generate (regardless if that is all that is possible).
I know this is not a proof (and therefore not an answer), but I think it might help someone else who is going to attack the problem. I ran a simulation in python for $n = 4$. Results represent the set of permutations of size $n$ that constitute the latin square and the number of times they turned up out of 100000. There are 24 which makes sense once you mod out relabelling from the 576 latin squares ($24 = 576 / 4!$)

```
frozenset([(1, 3, 0, 2), (0, 2, 1, 3), (3, 0, 2, 1), (2, 1, 3, 0)]) 5021
frozenset([(2, 3, 1, 0), (0, 1, 3, 2), (1, 0, 2, 3), (3, 2, 0, 1)]) 1817
frozenset([(0, 3, 1, 2), (1, 2, 0, 3), (3, 0, 2, 1), (2, 1, 3, 0)]) 1748
frozenset([(0, 1, 3, 2), (3, 2, 1, 0), (2, 3, 0, 1), (1, 0, 2, 3)]) 4938
frozenset([(3, 0, 1, 2), (0, 3, 2, 1), (1, 2, 0, 3), (2, 1, 3, 0)]) 5069
frozenset([(3, 1, 2, 0), (2, 3, 0, 1), (0, 2, 1, 3), (1, 0, 3, 2)]) 4958
frozenset([(3, 0, 1, 2), (1, 2, 3, 0), (2, 3, 0, 1), (0, 1, 2, 3)]) 4903
frozenset([(3, 0, 1, 2), (2, 1, 0, 3), (0, 3, 2, 1), (1, 2, 3, 0)]) 1835
frozenset([(0, 1, 3, 2), (1, 2, 0, 3), (3, 0, 2, 1), (2, 3, 1, 0)]) 4941
frozenset([(1, 3, 0, 2), (2, 0, 3, 1), (3, 1, 2, 0), (0, 2, 1, 3)]) 1795
frozenset([(1, 3, 0, 2), (2, 0, 1, 3), (3, 1, 2, 0), (0, 2, 3, 1)]) 4962
frozenset([(3, 1, 0, 2), (2, 0, 3, 1), (1, 3, 2, 0), (0, 2, 1, 3)]) 4974
frozenset([(1, 3, 2, 0), (3, 1, 0, 2), (2, 0, 1, 3), (0, 2, 3, 1)]) 1759
frozenset([(1, 0, 3, 2), (2, 3, 1, 0), (3, 2, 0, 1), (0, 1, 2, 3)]) 4958
frozenset([(1, 0, 3, 2), (2, 3, 0, 1), (3, 2, 1, 0), (0, 1, 2, 3)]) 1817
frozenset([(1, 2, 3, 0), (0, 3, 1, 2), (2, 1, 0, 3), (3, 0, 2, 1)]) 4826
frozenset([(3, 1, 2, 0), (2, 0, 3, 1), (0, 3, 1, 2), (1, 2, 0, 3)]) 4980
frozenset([(1, 3, 0, 2), (2, 0, 3, 1), (3, 2, 1, 0), (0, 1, 2, 3)]) 4933
frozenset([(1, 3, 2, 0), (0, 1, 3, 2), (2, 0, 1, 3), (3, 2, 0, 1)]) 4995
frozenset([(3, 0, 1, 2), (2, 1, 0, 3), (1, 3, 2, 0), (0, 2, 3, 1)]) 4857
frozenset([(2, 1, 3, 0), (0, 3, 1, 2), (1, 0, 2, 3), (3, 2, 0, 1)]) 4941
frozenset([(1, 2, 3, 0), (3, 1, 0, 2), (2, 0, 1, 3), (0, 3, 2, 1)]) 4958
frozenset([(3, 2, 1, 0), (2, 1, 0, 3), (1, 0, 3, 2), (0, 3, 2, 1)]) 4936
frozenset([(3, 1, 0, 2), (2, 3, 1, 0), (1, 0, 2, 3), (0, 2, 3, 1)]) 5079
```

In particular these don't do as well:

```
frozenset([(2, 3, 1, 0), (0, 1, 3, 2), (1, 0, 2, 3), (3, 2, 0, 1)]) 1817
frozenset([(0, 3, 1, 2), (1, 2, 0, 3), (3, 0, 2, 1), (2, 1, 3, 0)]) 1748
frozenset([(3, 0, 1, 2), (2, 1, 0, 3), (0, 3, 2, 1), (1, 2, 3, 0)]) 1835
frozenset([(1, 3, 0, 2), (2, 0, 3, 1), (3, 1, 2, 0), (0, 2, 1, 3)]) 1795
frozenset([(1, 3, 2, 0), (3, 1, 0, 2), (2, 0, 1, 3), (0, 2, 3, 1)]) 1759
frozenset([(1, 0, 3, 2), (2, 3, 0, 1), (3, 2, 1, 0), (0, 1, 2, 3)]) 1817
```

I am curious why they are different. Here is the code that produced it

```
from random import random, shuffle
from itertools import permutations
N = 4
DEBUG = False
def score(matrix):
'''Used to score a permutation in a current matrix'''
def helper(perm):
s = 0
for i in range(N):
s = s + matrix[i][perm[i]]
return s
return helper
def compatible(partial_lat_sq, perm):
'''You don't want a perm which interferes with existing perms'''
for perm2 in partial_lat_sq:
for i in range(N):
if perm[i] == perm2[i]:
return False
return True
result = {}
# here is the experiment
for experiment_number in xrange(100000):
lat_sq = []
s_n = list(tuple(p) for p in permutations(range(N)))
matrix = [[random() for c in range(N)] for r in range(N)]
while len(lat_sq) < N:
shuffle(s_n)
s_n = sorted(s_n, key=score(matrix), reverse=True) # perms sorted by matrix, big first
for perm in s_n
if compatible(lat_sq, perm):
lat_sq.append(perm)
for i in range(N):
matrix[i][perm[i]] = 0
if DEBUG:
print 'Lat Sq.', lat_sq
print 'Matrix', matrix
break
lat_sq = frozenset(lat_sq)
result[lat_sq] = 1 + result.get(lat_sq, 0)
for k, v in sorted(result.items()):
print k, v
```