Generate a Graeco-Latin square
05AB1E, 26 23 22 bytes
-3 bytes thanks to Emigna
-1 byte thanks to Kevin Cruijssen
Lãœ.ΔIôDζ«D€í«ε€нÙgQ}P
Try it online!
R, 164 148 bytes
-many bytes thanks to Giuseppe.
n=scan()
`!`=function(x)sd(colSums(2^x))
m=function()matrix(sample(n,n^2,1),n)
while(T)T=!(l=m())|!(g=m())|!t(l)|!t(g)|1-all(1:n^2%in%(n*l+g-n))
l
g
Try it online!
Dramatically inefficient - I think it's even worse than other brute force approaches. Even for n=3
, it will probably time out on TIO. Here is an alternate version (155 bytes) which works for n=3
in about 1 second.
Works by rejection. The function m
draws a random matrix of integers between \$1\$ and \$n\$ (without forcing each integer to appear exactly \$n\$ times, or in different columns - this explains the slowness of the code, and is the only thing changed in the faster version). Call this function twice, to get the "latin" and "greek" squares l
and g
. Then we check:
all(1:n^2%in%(n*l+g-n))
: are there \$n^2\$ different pairs of values inl
\$\times\$g
?- are
l
andg
latin squares?
To check that a matrix is a latin square, use the function !
. Since point 1. above has been validated, we know that each integer appears \$n\$ times in each of l
and g
. Compute the column-wise sums of 2^l
: these sums are all equal if and only if each integer appears once in each column (and the value of the sum is then \$2^{n+1}-2\$). If this is true for both l
and its transpose t(l)
, then l
is a latin square; same for g
. The function sd
, which computes the standard deviation, is an easy way to check whether all values of a vector are equal. Note that it doesn't work for the trivial cases \$n=0\$ and \$n=1\$ , which is OK according to the OP.
A final note: as often in R code golf, I used the variable T
, which is initialized as TRUE
, to gain a few bytes. But this means that when I needed the actual value TRUE
in the definition of m
(parameter replace
in sample
), I had to use 1
instead of T
. Similarly, since I am redefining !
as a function different from negation, I had to use 1-all(...)
instead of !all(...)
.
JavaScript (ES6), 159 147 140 bytes
Returns a flat array of \$n\times n\$ pairs of non-negative integers.
This is a simple brute force search, and therefore very slow.
n=>(g=(m,j=0,X=n*n)=>j<n*n?!X--||m.some(([x,y],i)=>(X==x)+(Y==y)>(j/n^i/n&&j%n!=i%n),g(m,j,X),Y=X/n|0,X%=n)?o:g([...m,[X,Y]],j+1):o=m)(o=[])
Try it online! (with prettified output)
Commented
n => ( // n = input
g = ( // g is the recursive search function taking:
m, // m[] = flattened matrix
j = 0, // j = current position in m[]
X = n * n // X = counter used to compute the current pair
) => //
j < n * n ? // if j is less than n²:
!X-- || // abort right away if X is equal to 0; decrement X
m.some(([x, y], i) => // for each pair [x, y] at position i in m[]:
(X == x) + // yield 1 if X is equal to x OR Y is equal to y
(Y == y) // yield 2 if both values are equal
// or yield 0 otherwise
> // test whether the above result is greater than:
( j / n ^ i / n && // - 1 if i and j are neither on the same row
j % n != i % n // nor the same column
), // - 0 otherwise
// initialization of some():
g(m, j, X), // do a recursive call with all parameters unchanged
Y = X / n | 0, // start with Y = floor(X / n)
X %= n // and X = X % n
) ? // end of some(); if it's falsy (or X was equal to 0):
o // just return o[]
: // else:
g( // do a recursive call:
[...m, [X, Y]], // append [X, Y] to m[]
j + 1 // increment j
) // end of recursive call
: // else:
o = m // success: update o[] to m[]
)(o = []) // initial call to g with m = o = []