Completing partial Latin squares with prescribed diagonals. (Q1428555)

A partial transversal of a partial Latin square of order \(n\) is a set of filled cells, at most one in each row and each column, such that no two of the cells contain the same symbol. A partial transversal with \(n\) cells is called a transversal. \textit{B. Alspach} and \textit{K. Heinrich} [Australas. J. Comb. 2, 39--55 (1990; Zbl 0757.05037)] posed the following question: Does there exist an integer \(N(k)\) such that if \(k\) transversals of a partial Latin square of order \(n \geq N(k)\) are prescribed, the square can always be completed? Here the author studies certain aspects of this question. In particular he asks: Does there exist an odd integer \(C(k)\) such that if \(k\) cyclically generated diagonals \(l_{i+t,j+t} = l_{ij}+t\) of a partial Latin square of odd order \(n \geq C(k)\) are prescribed, the square can always be cyclically completed? In this paper the author shows that \(C(k) \geq 3k-1\) and that \(N(k) \geq 4k-1\). The author conjectures that the bound for \(C(k)\) is sharp, and provides strong evidence for this claim by some computer constructions. By using hill climbing, he shows that every partial Latin square \(L\) of order \(n\) with \(k\) cyclically generated diagonals is cyclically completable for all \(k\) in the range \(2 \leq k \leq 7\) if \(n\) is odd and \(3k-1 \leq n \leq 21\). Furthermore, he shows that \(L\) is (noncyclically) completable for \(k=2,3\) or \(4\) and arbitrary \(n\) with \(4k-1 \leq n \leq 21\). He concludes with the question: Is it possible to prove that every partial Latin square of order \(n\) with \(k\) cyclically generated diagonals can be completed if \(n \geq 4k-1\)?