How to tell if a tri dimensional square is a Latin Square

Question

I need to design an algorithm that tells if a given matrix of integers is a valid latin square or not. I've never worked with Latin Sqares before so I don't know where to begin. After some research I only found algorithms for writing a Latin square. The only thing that occured to me is that the sum of all columns and rows should be the same but then I have to check for every number if it's repeated in that same row and column. Doing it that way the program will have a big time cost. I'm using C++.

Answer 1

Doing it that way the program will have a big time cost.

No, since you can reject a lot of matrix before you reach the end. So algorithm will fail fast. Worst estimation of working algorithm is O(n*(n+1)) (I assuming that you evaluate only square matrix where dimension is n*n). But average algorithm will be much better - because it will fail as first in-equality found.

Update: The average complexity can be rough and approximately estimated as number of real Latin Squares to number of possible squares. To do this we need introduce understand normalized square. Two squares bellow are intuitively the same :

[ 1 2       [5 7
  2 1 ]      7 5]

So to normalize this we can use substitution for numbers 1...n of n*n square. So first form wins.

For normalized squares Wiki provides an estimation

Are you scared? But for average we also need to divide this formula by total number of matrix. To do this see this formula http://en.wikipedia.org/wiki/Combination