Latin Squares

by Le Tan Dang Khoa, Feb 1, 2018

Trong dự án dài hơi về TAoCP, những phần đầu của Vol 4A.

Định nghĩa

Cho một ma trận vuông có kích thước M và các phần tử thuộc $0, 1, \dots, M - 1$ , ta xây dựng ma trận sao cho mỗi phần tử $i$ trong tập $0, 1, \dots, M - 1$ chỉ xuất hiện đúng 1 lần trong mỗi cột và mỗi dòng.

Ví dụ

Cho 16 quân bài bao gồm tổ hợp của các quân J, K, Q, A và 4 loại $♡, ♢, ♣, ♠$ , ta sắp xếp sao cho mỗi dòng/cột có đủ 4 chất và 4 quân (Jacques Ozaman, mathematiques et physiques, Paris 1725).

Ứng dụng

Thực ra trong toán học đôi khi ta không cần một ứng dụng thực tế của một vấn đề để có động lực nghiên cứu hay tìm hiểu. Tuy nhiên, mình lại là một thanh niên học khoa học máy tính với thiên hướng “engineer” hơn là các nhà toán học cao siêu, nên mình đòi hỏi cái mình học có tính ứng dụng ít nhiều. Về khối vuông Latin này có kha khá ứng dụng:

Sudoku là một dạng của khối vuông Latin, và trò chơi này trở thành một trong những trò chơi giải đố nổi tiếng nhất thế giới.
Trong cài đặt thí nghiệm.
Mã sửa lỗi.
Mã hóa.

Câu chuyện lịch sử

Năm 1779, một câu đố tương tự như trong phần ví dụ đã thu hút nhà toán học vĩ đại: Leonhard Euler

Thirty-six ofﬁcers of six different ranks, taken from six different regiments, want to march in a $6 \times 6$ formation so that each row and each column will contain one ofﬁcer of each rank and one of each regiment. How can they do it?

Dù đã gần như mù nhưng Euler vẫn quyết tâm giải bài toán này và tổng quát hóa cho các trường hợp $M = 1, 2, \dots$ . Tuy nhiên, với $M \mod 4 = 2$ khiến ông không giải được, Sau đó ông đã đưa ra một conjecture rằng không thể giải câu đố này với trường hợp tổng quát $M \mod 4 = 2$ .

Tuy nhiên phần định nghĩa về khối Latin hơi khác 1 chút so với phần ví dụ. Nếu ta đặt $♡ = 1, ♢ = 2, ♣ = 3, ♠ = 4$ , và tách chất và quân bài ra 2 ma trận, ta được 2 ma trận Latin.

[\begin{matrix} J & A & K & Q \\ Q & K & A & J \\ A & J & Q & K \\ K & Q & J & A \end{matrix}]

và

[\begin{matrix} 2 & 1 & 4 & 3 \\ 4 & 3 & 2 & 1 \\ 3 & 4 & 1 & 2 \\ 1 & 2 & 3 & 4 \end{matrix}]

Figure 1 trở thành

[\begin{matrix} J 2 & A 1 & K 4 & Q 3 \\ Q 4 & K 3 & A 2 & J 1 \\ A 3 & J 4 & Q 1 & K 2 \\ K 1 & Q 2 & J 3 & A 4 \end{matrix}]

Hai ma trận được gọi là orthogonal khi chập các phần tử lại với nhau, mỗi phần tử trong ma trận mới là duy nhất. Bài toán lúc đó Euler phải giải là: cho 1 ma trận Latin, làm sao để tìm được một ma trận Latin khác orthogonal với nó. Ma trận sau khi được chập lại gọi là Graeco-Latin. Để chứng minh nhận định của Euler đúng hay sai, các nhà toán học đã mất gần 180 năm với sự giúp đỡ của máy tính.

Năm 1957, Paige và Tompkins đã thử lập trình trên máy SWAC để tìm ví dụ phản chứng khi $M = 10$ nhưng sau gần 5 giờ chạy liên tục không ra kết quả, họ đã tắt chương trình.

Năm 1960, Parker và đồng sự đã chứng minh rằng có thể tìm được 1 ma trận orthogonal với $M \geq 6$ và phản chứng nhận định của Euler. Đồng thời, ông cũng viết 1 chương trình trên máy UNIVAC 1206 để sinh ra ma trận đó. Chương trình chưa đến 1 giờ để có thể tìm ra lời giải với cùng input năm 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

Một solution trong sách:

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 sử dụng lại khái niệm transversal mà trước đây Euler từng định nghĩa, transversal là cách để chọn ra chuỗi $M$ phần tử sao cho chỉ có 1 phần tử duy nhất ở mỗi dòng, mỗi cột và duy nhất trong transversal.

Ví dụ: 0859734216, tức ta chọn 0 ở cột 1, 8 ở cột 2, 5 ở cột 3, … 6 ở cột 10. Giả sử ta có $k$ là giá trị đầu tiên của transversal, dựa vào giá trị từng phần tử phía sau, ta thay bằng $k$ . Chọn ra $M$ transversal của $k = 0, 1, \dots, M - 1$ ta sẽ tạo thành 1 orthogonal matrix.

Thuật toán đếm số transversal của một ma trận vuông N.

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;
            }
        }

    }
};

Lấy input từ cuốn TAoCP ra được kết quả:

79 96 76 87 70 84 83 75 95 63

Bem, đúng với kết quả trong sách. Chỉnh sửa một chút ta có thể có được toàn bộ các transversal cần tìm. Sau đó với mỗi transversal của $k$ , ta chọn ra bộ nào không có phần tử trùng (trong index của orthogonal matrix), ta sẽ tìm được ma trận. Chi tiết về phần này sẽ được đề cập trong bài viết nói về Dancing Links.

Tài liệu tham khảo

Knuth, Donald E. The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1.
Latin square - Wikipedia
http://elscorcho.50webs.com/latinsquares.pdf