mathr / blog / #

A Latin square of order \(n\) is a matrix of \(n^2\) values each in the range \(\{1, 2, ,\ldots, n\}\), such that each value occurs exactly once in each row and each column. The number of Latin squares goes up very quickly with \(n\): see A002860 in the Online Encyclopedia of Integer Sequences. A subset is that of reduced Latin squares, where the first row and the first column are the sequence \((1 2 \ldots n)\) (counted by A000315). And a third group is Latin squares with the first row fixed as \((1 2 \ldots n)\) and no condition on the first column: A000479.

While answering a question on math.SE, I noticed the OEIS has very few terms of another sequence related to Latin squares, namely the number of classes of "structurally equivalent" Latin squares, where equivalence is over rotations, reflections, and permuting the symbols. The computer programs I wrote to search for the answers to the question finished in a long but manageable amount of time, so I wrote a program to search for the next term of A264603:

// gcc -std=c99 -Wall -Wextra -pedantic -O3 -march=native A264603.c
// ./a.out order

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// order
static int O = 0;

// generated square
static char *square = 0;

// buffer for normalization of symmetrical squares
static char *squares = 0;

// counter for progress
static long long total = 0;

// counter for uniques
static long long unique = 0;

// make first row be ABC... in-place
static inline void relabel(char *s)
{
  char label[O];
  for (int i = 0; i < O; ++i)
    label[s[i] - 'A'] = 'A' + i;
  for (int i = 0; i < O; ++i)
    for (int j = 0; j < O; ++j)
      s[O*i+j] = label[s[O*i+j] - 'A'];
}

// wrap strcmp with comparator type
static int compare(const void *a, const void *b)
{
  return strcmp(a, b);
}

// find lexicographically least of all relabeled symmetries
// this acts as the canonical representative for the structure class
static inline void normalize()
{
  // regular
  int k = 0;
  for (int i = 0; i < O; ++i)
    for (int j = 0; j < O; ++j)
      squares[k+O*i+j] = square[O*i+j];
  relabel(&squares[k]);
  // rotated 90
  k += O * O + 1;
  for (int i = 0; i < O; ++i)
    for (int j = 0; j < O; ++j)
      squares[k+O*(O-j-1)+i] = square[O*i+j];
  relabel(&squares[k]);
  // rotated 180
  k += O * O + 1;
  for (int i = 0; i < O; ++i)
    for (int j = 0; j < O; ++j)
      squares[k+O*(O-i-1)+(O-j-1)] = square[O*i+j];
  relabel(&squares[k]);
  // rotated 270
  k += O * O + 1;
  for (int i = 0; i < O; ++i)
    for (int j = 0; j < O; ++j)
      squares[k+O*j+(O-i-1)] = square[O*i+j];
  relabel(&squares[k]);
  // reflect I
  k += O * O + 1;
  for (int i = 0; i < O; ++i)
    for (int j = 0; j < O; ++j)
      squares[k+O*(O-i-1)+j] = square[O*i+j];
  relabel(&squares[k]);
  // reflect J
  k += O * O + 1;
  for (int i = 0; i < O; ++i)
    for (int j = 0; j < O; ++j)
      squares[k+O*i+(O-j-1)] = square[O*i+j];
  relabel(&squares[k]);
  // reflect IJ
  k += O * O + 1;
  for (int i = 0; i < O; ++i)
    for (int j = 0; j < O; ++j)
      squares[k+O*j+i] = square[O*i+j];
  relabel(&squares[k]);
  // reflect JI
  k += O * O + 1;
  for (int i = 0; i < O; ++i)
    for (int j = 0; j < O; ++j)
      squares[k+O*(O-1-j)+(O-1-i)] = square[O*i+j];
  relabel(&squares[k]);
  // normalize
  qsort(squares, 8, O * O + 1, compare);
}

// return 1 if square is not Latin at index i,j
static inline int prune(int i, int j)
{
  char symbol = square[O*i+j];
  for (int q = 0; q < j; ++q)
    if (symbol == square[O*i+q])
      return 1;
  for (int p = 0; p < i; ++p)
    if (symbol == square[O*p+j])
      return 1;
  return 0;
}

static inline void output(void)
{
  // output normalized representation
  normalize();
  if (! compare(square, squares))
    unique++;
  // report progress
  total++;
  if ((total & 0xFFFF) == 0)
    fprintf(stderr, "\r%lld %lld ", total, unique);
}

// depth first search across space of Latin squares with pruning
static void generate(int i, int j)
{
  if (j == O)
  {
    i += 1;
    j = 0;
  }
  if (i == O)
  {
    output();
    return;
  }
  if (i == 0)
  {
    // first row is ABC... wlog
    square[O*i+j] = 'A' + j;
    generate(i, j + 1);
  }
  else
  {
    // try each possibility for next cell
    for (int k = 0; k < O; ++k)
    {
      square[O*i+j] = 'A' + k;
      if (prune(i, j))
        continue;
      generate(i, j + 1);
    }
  }
}

// entry point
int main(int argc, char **argv)
{
  if (argc > 1)
    O = atoi(argv[1]);
  if (! (0 < O))
  {
    fprintf(stderr, "usage: %s order\n", argv[0]);
    return 1;
  }
  square = calloc(1, O * O + 1);
  squares = calloc(1, 8 * (O * O + 1));
  generate(0, 0);
  printf("\norder: %d\ntotal: %lld\nunique: %lld\n", O, total, unique);
  return 0;
}

For order 1 through 6 it matches up with the OEIS page, and for order 7 the output after around 16 hours of computation is:

\[1524901344\]

You can download the C source code: A264603.c