Latin Square Intercalates

The Problem

A Latin Square of order \(n\) is a square filled with the values \(1, \ldots, n\) such that every row and column contains precisely \(1\) copy of \(1, \ldots, n\). An intercalate is a \(2 \times 2\) Latin subsquare. In particular, a subsquare is formed by choosing two rows \(r_1, r_2\) and two columns \(c_1, c_2\) and determining if $$S_{r_1,c_1} = S_{r_2,c_2} \wedge S_{r_2,c_1} = S_{r_1,c_2}$$

Submission Format

Please submit a CSV file that contains \(30 \times 30 = 900\) values from \(1, \ldots, 30\). Each group of \(30\) numbers corresponds to a row of a \(30 \times 30\) square, call it \(S\). \(S\) must correspond to a Latin Square to be scored. The best score is precisely the number of intercalates that exist in \(S\). Your goal is to maximize the number of intercalates in \(S\).

Score Implementation

The following is a Python implementation of the score function to help you get started.

from itertools import combinations
import numpy as np


def is_latin(sqr: np.ndarray, order: int) -> bool:
    need = set(range(1, order + 1))
    # Check the rows.
    for row in sqr:
        if set(row) != need:
            return False

    # Check the columns.
    for col in sqr.T:
        if set(col) != need:
            return False

    # It passed all checks, it is a Latin square.
    return True


def is_intercalate(sqr: np.ndarray, 
                   r1: int, r2: int, c1: int, c2: int) -> bool:
    if sqr[r1, c1] == sqr[r2, c2] and sqr[r2, c1] == sqr[r1, c2]:
        return True
    return False

def score(sqr: list[int]):
    N = 30
    mat = np.reshape(sqr, (N, N))
    # Check to see if we have a valid Latin square.
    if not is_latin(mat, N):
        return None

    nums = list(range(N))
    count = 0
    for r1, r2 in combinations(nums, 2):
        for c1, c2 in combinations(nums, 2):
            if is_intercalate(mat, r1, r2, c1, c2):
                count += 1

    return count