Aficionado de arte buscando máximo dispersos cuadrado Latino de orden 7

Question

Estoy un arte aficionado trabajando en una pintura que tiene una cuadrícula de $7$ filas y columnas con un rectángulo pintado (esquinas redondeadas) en cada posición de la cuadrícula. Yo quería usar $7$ colores y no tienen un color repetir en cualquier fila o columna. Googleando he encontrado esto se llama un Cuadrado latino. Entonces, para mi sorpresa, me enteré de que hay $16$ millones de orden impar $7$ de los Cuadrados latinos. En lugar de solo uno de los $16$ millones pensé que sería interesante el uso de una de las más únicas versiones que tiene alguna restricción adicional que se le impuso. Entonces me preguntaba si es que existe tal cosa como un máximo dispersos Cuadrado latino? Con esto quiero decir que el promedio de la distancia física entre cada elemento y el otro $6$ elementos de un mismo símbolo es mayor cuando la media de todas las $49$ elementos.

Así que mi pregunta es:

No existe un método para la construcción de un orden de 7 de Cuadrado latino que es el máximo se dispersa en el sentido de que he tratado de describir más arriba?

Answer 1

Este no es un método de construcción, pero la fuerza bruta búsqueda exhaustiva. No matemáticamente elegante, pero eventualmente puede dar un máximo dispersos cuadrado latino.

Wikipedia dice que hay $16942080$ reducción de cuadrados latinos de orden $7$. Sospecho que desea que la primera columna a ser permutados, que multiplica eso por $6! = 720$, con cerca de 12 mil millones de plazas.

Escribí un programa de ordenador para una exhaustiva búsqueda en el espacio de los cuadrados latinos con primera fila fija. (No podría ser más si los errores de redondeo distorsiona los cálculos, yo solo la salida al $\ge$ actual mejor) de los mejores $4$ cada uno con un marcador final de $1199.824938649409432$ correspondiente a la media distancia $4.081$ son:

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

El más próximo, subcampeón había score $1199.476574957478533$.

El cuadrado latino con la menor dispersión (score $1151.661909164740564$, correspondiente a un promedio de distancia $3.917$) fue (dos isomorfo variantes de):

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

El más cercano finalista había score $1152.143695276356539$.

Curiosamente, el uso de un poco diferente de la medición (suma del cuadrado de las distancias), cada uno de los 1 mil millones o así calculado hasta ahora ha score $5488$.

Aquí está el código fuente para el programa de búsqueda:

// 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;
}