Cycles in $5×5$ Latin squares (solution found)

151 Views Asked by At

One of my favorite puzzle formats is KenKen, in which you are to find an $n×n$ Latin square to be filled with whole numbers from 1 to $n$, given sums, differences, products or quotients of various groups of entries. The puzzles come in various sizes, including $5×5$.

When I solve a $5×5$ puzzle I always seem to find at the end that at least two rows are cyclic permutations of each other. Is this always true in $5×5$ Latin squares, or is there some weird coincidence going on?

Turns out I found the solution. Over 90% of 5×5 Latin squares actually have at least one pair of cyclically permuted rows. So, a 5×5 KenKen without such a cyclic permutations turns out to be relatively rare!

1

There are 1 best solutions below

3
On BEST ANSWER

A counter example where none of the rows are a cyclic permutation of another:

$$\begin{bmatrix} 1&2&3&4&5\\ 2&3&5&1&4\\ 3&5&4&2&1\\ 4&1&2&5&3\\ 5&4&1&3&2 \end{bmatrix}$$

But, it turns out that there are only $5$ reduced Latin squares out of $56$ total for $5×5$ squares. So, less than 10% of all $5×5$ solutions should be expected to lack such a cyclic row permutation. Hence such solutions are hard to find.

Here are the other four reduced squares with no cyclic row permutations:

$$\begin{bmatrix} 1&2&3&4&5\\ 2&5&1&3&4\\ 3&1&4&5&2\\ 4&3&5&2&1\\ 5&4&2&1&3 \end{bmatrix}$$

$$\begin{bmatrix} 1&2&3&4&5\\ 2&5&4&1&3\\ 3&4&2&5&1\\ 4&1&5&3&2\\ 5&3&1&2&4 \end{bmatrix}$$

$$\begin{bmatrix} 1&2&3&4&5\\ 2&4&5&3&1\\ 3&5&2&1&4\\ 4&3&1&5&2\\ 5&1&4&2&3 \end{bmatrix}$$

$$\begin{bmatrix} 1&2&3&4&5\\ 2&4&1&5&3\\ 3&1&5&2&4\\ 4&5&2&3&1\\ 5&3&4&1&2 \end{bmatrix}$$