2
$\begingroup$

Context

In the boardgame Azul, your goal is to complete as much as possible of a $5\times5$ board by placing 25 tiles of 5 different colours (5 tiles of each colour) so that no colour appears twice in a row or column. For the normal mode, the tiles must be placed following a predefined pattern, which can be seen here and that I represent with the following matrix $P$, where each letter represents a different colour:

$$P = \begin{bmatrix}a & b & c & d & e\\ e & a & b & c & d\\ d & e & a & b & c \\ c & d & e & a & b \\ b & c & d & e & a\end{bmatrix}$$

The advanced playing mode has no predefined pattern, so you can come up with your own, while respecting the constraint that no colour appears twice in each row or column.

I've realised that I can build valid patterns by permutating the rows and columns of the predefined pattern, as these operation preserve the number of different colours in each row or column. The resulting pattern $P'$ can be represented by $R \times P \times C$, where $R$ and $C$ are two permutation matrices indicating the rows and columns to permutate, respectively. For example:

$$P' = \begin{bmatrix} 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0\end{bmatrix} \times \begin{bmatrix} a & b & c & d & e\\ e & a & b & c & d\\ d & e & a & b & c \\ c & d & e & a & b \\ b & c & d & e & a\end{bmatrix} \times \begin{bmatrix} 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1\end{bmatrix} = \begin{bmatrix} a & c & b & d & e\\ d & a & e & b & c\\ b & d & c & e & a\\ c & e & d & a & b\\ e & b & a & c & d\\\end{bmatrix}$$

Which is a valid pattern.

Since there are $5!$ permutation matrix, I have managed to create $(5!)^2 = 14400$ valid patterns this way, although each pattern appears 5 times, so only 2880 of them are distinct.

Questions

  1. Is there a valid pattern that can't be created by the permutation of rows and columns of $P$? Does the same answer hold true for matrices of higher order?

    For patterns of order 3, I checked and all the valid patterns are permutations of rows and columns of $P$, but brute-forcing this doesn't scale particularly well.

  2. Given $P$ and $P'$, how can I find the permutations matrices $C$ and $R$ that transform $P$ into $P'$?

$\endgroup$
1
  • 2
    $\begingroup$ You might want to read up on Latin squares. $\endgroup$ – Richard Lyons Oct 16 '20 at 16:42
5
$\begingroup$

The answer to Question 1 is yes. What you have described is called a Latin square. Two Latin squares are isotopic if one can be obtained from the other by permuting rows, columns, and permuting the names of the symbols. Note that isotopy is stronger than what you describe since we are allowed to permute the names of the symbols. It is known (see OEIS A040082) that there are exactly two isotopy classes of $5 \times 5$ Latin squares. Thus, every $P'$ which is not in the isotopy class of your $P$ cannot be obtained from $P$ by permuting rows and columns. Of course, this also holds for larger Latin squares, since the number of isotopy classes increases with $n$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.