Latin Squares

The con­tent of this note mostly be­longs to the first sec­tion of TAoCP, Vol. 4A.

Definition

Given a square ma­trix of size $M$ where each el­e­ment is in the set $0,1,\cdots ,M-1$, we con­struct a ma­trix such that each el­e­ment $i$ in the set $0,1,\cdots ,M-1$ ap­pears ex­actly once in every row and col­umn.

Examples

We have 16 cards which com­prise a com­bi­na­tion of 4 ranks, i.e., J, K, Q, A, and 4 suits: $\mathrm{♡},\mathrm{♢},\mathrm{♣},\mathrm{♠}$. We arrange the cards such that for each col­umn or row, we have 4 ranks and 4 suits (Jacques Ozaman, Mathématiques et Physiques, Paris 1725).

Applications

While study­ing math­e­mat­ics, some­times we can­not find an ob­vi­ous ap­pli­ca­tion to mo­ti­vate our­selves to study the con­cept. However, since I am a com­puter sci­ence en­gi­neer who is more prag­matic than math­e­mat­i­cally in­clined, I am es­pe­cially in­ter­ested in con­cepts which have ap­pli­ca­tions in real life. Regarding the Latin square, we get sev­eral:

• Sudoku: a vari­ant of the Latin square is one of the most pop­u­lar puz­zles in the world.
• Design of ex­per­i­ments.
• Error cor­rect­ing codes.
• Cryptography.

War Story

In 1779, a puz­zle sim­i­lar to the afore­men­tioned ex­am­ple at­tracted the fa­mous math­e­mati­cian Leonhard Euler:

Thirty-six of­fi­cers of six dif­fer­ent ranks, taken from six dif­fer­ent reg­i­ments, want to march in a $6\times 6$ for­ma­tion so that each row and each col­umn will con­tain one of­fi­cer of each rank and one of each reg­i­ment. How can they do it?

Even though he was al­most blind, Euler was de­ter­mined to solve the puz­zle and tried to gen­er­al­ize the prob­lem for other cases $M=1,2,\cdots$. However, when $M\mathrm{mod}4=2$, he could not solve it. Later, he stated a con­jec­ture that there is no so­lu­tion for $M\mathrm{mod}4=2$.

However, the puz­zle Euler tack­led is quite dif­fer­ent com­pared to the de­f­i­n­i­tion given in the pre­vi­ous sec­tion. More pre­cisely, let $\mathrm{♡}=1,\mathrm{♢}=2,\mathrm{♣}=3,\mathrm{♠}=4$, and we di­vide ranks and suits into 2 sep­a­rate ma­tri­ces, we get two Latin squares:

and

Fig. 1 be­comes:

Two Latin squares are or­thog­o­nal if, when we com­bine two el­e­ments with the same po­si­tion to­gether, each el­e­ment in the new ma­trix is unique. The puz­zle of Euler is: given a Latin square, how do we find an­other Latin ma­trix which is or­thog­o­nal to the given one?

The com­bined ma­trix is called a Graeco-Latin ma­trix.

In or­der to prove Euler’s con­jec­ture, math­e­mati­cians spent al­most 180 years with the sup­port of com­put­ers. In 1957, Paige and Tompkins pro­grammed on SWAC to find a coun­terex­am­ple with $M=10$. After 10 hours run­ning with­out any re­sults, they ter­mi­nated the pro­gram.

In 1960, Parker et al. proved that it is pos­si­ble to find an or­thog­o­nal Latin square when $M\ge 6$ and dis­proved the con­jec­ture. In ad­di­tion, they also wrote a pro­gram on UNIVAC 1206 which was able to gen­er­ate the ma­trix. The pro­gram only took nearly 1 hour to find a so­lu­tion for the in­put in 1957:

0 1 2 3 4 5 6 7 8 9
1 8 3 2 5 4 7 6 9 0
2 9 5 6 3 0 8 4 7 1
3 7 0 9 8 6 1 5 2 4
4 6 7 5 2 9 0 8 1 3
5 0 9 4 7 8 3 1 6 2
6 5 4 7 1 3 2 9 0 8
7 4 1 8 0 2 9 3 5 6
8 3 6 0 9 1 5 2 4 7
9 2 8 1 6 7 4 0 3 5

One in­stance of the so­lu­tion (TAoCP):

0 2 8 5 9 4 7 3 6 1
1 7 4 9 3 6 5 0 2 8
2 5 6 4 8 7 0 1 9 3
3 6 9 0 4 5 8 2 1 7
4 8 1 7 5 3 6 9 0 2
5 1 7 8 0 2 9 4 3 6
6 9 0 2 7 1 3 8 4 5
7 3 5 1 2 0 4 6 8 9
8 0 2 3 6 9 1 7 5 4
9 4 3 6 1 8 2 5 7 0

Transversals

Parker uti­lized a con­cept called trans­ver­sal which was pre­vi­ously pro­posed by Euler. A trans­ver­sal is a way to choose a se­quence of $M$ el­e­ments such that there is only 1 el­e­ment in each row, each col­umn, and each is unique in the se­quence.

For ex­am­ple: 0859734216 means that we choose 0 in col­umn 1, 8 in col­umn 2, 5 in col­umn 3, etc. Suppose that $k$ is the first item of a trans­ver­sal; based on the fol­low­ing el­e­ments, we re­place them by $k$. Given $M$ trans­ver­sals of $k=0,1,\cdots ,M-1$, we are able to con­struct an or­thog­o­nal ma­trix.

The al­go­rithm be­low counts the num­ber of trans­ver­sals of a Latin square.

typedef vector<vector<int>> mat;
class transversal {
private:
    int n;
    vector<bool> row;
    vector<bool> nums;
    mat input;
    int cnt;
public:
    transversal(const mat& in_): n(in_.size()), input(in_),
    row(n, false), nums(n, false), cnt(0) {
        assert(in_.size() == in_[0].size());
    }

    void print() { // debugging
        for (auto& rows: input) {
            for (auto& e: rows) cout << e << " ";
            cout << endl;
        }
    }

    int compute(int idx) {
        cnt = 0;
        fill(row.begin(), row.end(), false);
        fill(nums.begin(), nums.end(), false);
        nums[input[idx][0]] = true;
        row[idx] = true;
        comp(1);
        return cnt;
    }

private:
    void comp(int idx) { // idx = index of column
        if (idx == n) {
            cnt++;
            return;
        }

        for (int i = 0; i < n; ++i) {
            if (!row[i] && !nums[input[i][idx]] ) {
                row[i] = true;
                nums[input[i][idx]] = true;
                comp(idx+1);
                row[i] = false;
                nums[input[i][idx]] = false;
            }
        }

    }

};

From the above in­put, we get the out­put:

79 96 76 87 70 84 83 75 95 63

It is ex­actly the same as in the book. We can later mod­ify the code to find all trans­ver­sals given an in­put. After that, for every trans­ver­sal $k$, we choose a set such that there are no du­pli­cate el­e­ments, which be­comes the out­put ma­trix. The de­tails of the al­go­rithm will be dis­cussed in later posts about Dancing Links.

References

1. Knuth, Donald E. The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1.
2. Latin square - Wikipedia
3. http://​elscor­cho.50webs.com/​latin­squares.pdf