Art hobbyist seeking maximally dispersed Latin Square of order 7

Question

I'm an art hobbyist working on a painting that has a grid of $7$ rows and columns with a painted rectangle (rounded corners) at each grid position. I wanted to use $7$ colours and not have a colour repeat in any row or column. Googling I found this is called a Latin Square. Then to my surprise I learnt that there are $16$ million odd order $7$ Latin Squares. Rather than just pick one of those $16$ million I thought it would be interesting to use one of the more unique versions that has some additional constraint imposed on it. Then I wondered whether there is such a thing as a maximally dispersed Latin Square? By this I mean that the average physical distance between each element and the other $6$ elements of the same symbol is greatest when averaged over all $49$ elements.

So my question is:

Does a method exist for construction an order 7 Latin Square that is maximally dispersed in the sense I've tried to describe above?

Answer 1

This is not a method of construction, but a brute force exhaustive search. Not mathematically elegant, but may eventually give you a maximally dispersed Latin square.

Wikipedia says there are $16942080$ reduced Latin squares of order $7$. I suspect you want the first column to be permuted, which multiplies that by $6! = 720$, giving around 12 billion squares.

I wrote a computer program to exhaustively search the space of Latin squares with first row fixed. (There could possibly be more if rounding errors distorted the calculations, I only output when $\ge$ current best) the best $4$ each with a final score of $1199.824938649409432$ corresponding to average distance $4.081$ are:

A B C D E F G
D E F G A B C
F G A B C D E
B C D E F G A
E F G A B C D
G A B C D E F
C D E F G A B

A B C D E F G
D E F G C A B
G C A B F D E
B F D E A G C
E A G C D B F
C D B F G E A
F G E A B C D

A B C D E F G
E F G A B C D
C D E F G A B
G A B C D E F
D E F G A B C
B C D E F G A
F G A B C D E

A B C D E F G
F G E A B C D
C D B F G E A
E A G C D B F
B F D E A G C
G C A B F D E
D E F G C A B

The next nearest runner-up had score $1199.476574957478533$.

The Latin square with the least dispersion (score $1151.661909164740564$, corresponding to average distance $3.917$) was (two isomorphic variants of):

A B C D E F G
B C A E F G D
C A E B G D F
F E B G D A C
E D G F B C A
D G F A C B E
G F D C A E B

The nearest runner up had score $1152.143695276356539$.

Interestingly, using a slightly different measurement (summing squared distances), every single one of the 1 billion or so calculated so far has score $5488$.

Here is the source code for the search program:

// gcc -std=c99 -Wall -Wextra -pedantic -O3 -march=native -o latin7 latin7.c -lm

#include <math.h>
#include <stdio.h>

#define O 7

static char square[O][O];
static long long total = 0;
static double best = 0;

static inline double evaluate()
{
  double metric = 0;
  for (int i = 0; i < O; ++i)
    for (int j = 0; j < O; ++j)
    {
      char symbol = square[i][j];
      for (int p = 0; p < O; ++p)
        for (int q = 0; q < O; ++q)
          if (square[p][q] == symbol)
          {
            int x = i - p;
            int y = j - q;
            metric += sqrt(x * x + y * y);
          }
    }
  return metric;
}

static inline int prune(int i, int j)
{
  char symbol = square[i][j];
  for (int q = 0; q < j; ++q)
    if (symbol == square[i][q])
      return 1;
  for (int p = 0; p < i; ++p)
    if (symbol == square[p][j])
      return 1;
  return 0;
}

static inline void output(void)
{
  total++;
  if ((total & 0xFFFF) == 0)
    fprintf(stderr, "\r        %lld      ", total);
  double metric = evaluate();
  if (metric < best) return;
  best = metric;
  printf("%.18e", metric);
  for (int p = 0; p < O; ++p)
  {
    printf("\t");
    for (int q = 0; q < O; ++q)
      printf("%c", square[p][q]);
  }
  printf("\n");
}

static void generate(int i, int j)
{
  if (j == O)
  {
    i += 1;
    j = 0;
  }
  if (i == O)
  {
    output();
    return;
  }
  if (i == 0)
  {
    square[i][j] = 'A' + j;
    generate(i, j + 1);
  } 
  else
  {
    for (int k = 0; k < O; ++k)
    {
      square[i][j] = 'A' + k;
      if (prune(i, j))
        continue;
      generate(i, j + 1);
    }
  }
}

int main()
{
  generate(0, 0);
  return 0;
}