1
$\begingroup$

We say that an $n\times n$ table of integers in $\{1,\dots,n\}$ has the weak-sudoku property if each number appears exactly once in each row and each column.

The main question is: how many weak-sudoku tables are there, depending on $n$?

Yet, this seems a quite unapproachable question, hence we can ask some hopefully easier questions such as:

  • How does this number $\varphi(n)$ grow asymptotically?
  • If we say that two tables are equivalent if we can obtain one from another by row and column permutations, and/or by operations on the table induced by permutations of $\{1,\dots , n\}$ (i.e. renaming the numbers in the table), how many equivalence classes $\varepsilon(n)$ are there?

Here are some observations:

  • $\varphi(1)=1, \varphi(2)=2, \varphi(3)=12$
  • $\varepsilon(1)=\varepsilon(2)=\varepsilon(3)=1, \varepsilon(4)=4, \varepsilon(5)=56, \varepsilon(6)=9408$

We observe that, numerically, it seems that $\varepsilon(n)\sim e^{(n-3)^2}$.

Moreover we can identify some canonical representatives for the equivalence classes that are the weak-sudoku tables of the form below: $$ \begin{pmatrix} 1& 2 & 3& \cdots & n\\ *& 1 & *& \cdots& *\\ *&* & 1 & \cdots&*\\ \vdots& \vdots&\vdots & \ddots& \vdots\\ *& *&*&\cdots&1 \end{pmatrix} $$

By this canonical form we can implement an Octave function that calculates $\varepsilon(n)$ by which we have calculated the above values of $\varepsilon$.

A=diag(ones(1,n));
A(2:end,1)=2:j;

function count=table(A,count)
count=0;
n=size(A)(1);
if((A==0)==A*0)
 A;
 count=count+1;
 return 
endif
[i,j]=find(A==0);
i=i(1);
j=j(1);
for k=2:n
 if (all([A(i,:);A(:,j)']!=k))
   B=A;
   B(i,j)=k;
   count=count+table(B);
 endif
endfor
end

Finally we also observe that $\varphi(n)\leq (n!)^2\varepsilon(n)$ and that therefore, if the above estimation is correct, $\varphi(n)\sim \varepsilon(n)$.

$\endgroup$
  • $\begingroup$ "We say that an $n\times n$ table of integers in $\{1,\ldots,n\}$ has the weak-sudoku property if each number appears exactly once in each row and each column." That's what mathematicians call a Latin square en.wikipedia.org/wiki/Latin_square $\endgroup$ – Lord Shark the Unknown May 19 at 15:44
1
$\begingroup$

Your table is known as a Latin square. According to Wikipedia, there are no good estimates for the number of Latin squares. The OEIS contains some counts for $n \leq 11$: A002860. In particular, for $n = 9$ the answer is 5524751496156892842531225600.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.