Ma phương – ma trận kì ảo

Trong toán vui, một ma trận kì ảo bậc n (còn gọi là ma phương hay hình vuông ma thuật) là một cách sắp xếp n² số, thường là các số nguyên phân biệt, trong một bảng vuông sao cho tổng n số trên mỗi hàng, cột, và đường chéo đều bằng nhau. Ma trận kì ảo chuẩn chứa các số nguyên từ 1 đến n².

Tồn tại ma trận kì ảo chuẩn cho mọi bậc n ≥ 1 trừ n = 2. Ma trận kì ảo bậc 1 là trường hợp tầm thường, nó chứa duy nhất 1 ô với giá trị 1. Trường hợp không tầm thường có kích thước nhỏ nhất là ma trận kì ảo bậc 3.

Hằng số là tổng của mỗi hàng, cột, và đường chéo được gọi là hằng số kì ảo. Giá trị này của ma trận kì ảo chuẩn chỉ phụ thuộc vào n và có giá trị

Với các ma trận kì ảo bậc n = 3, 4, 5, …, các hằng số kì ảo tương ứng là:

15, 34, 65, 111, 175, 260, … (chuỗi A006003 trong từ điển bách khoa về các chuỗi số nguyên OEIS).

Bài toán ma phương:

Viết chương trình nhập vào một số tự nhiên N (N lẻ), sau đó điền các số từ 1 đến n² vào trong một bảng ô vuông sao cho tổng các hàng ngang, hàng dọc và 2 đường chéo đều bằng nhau (bảng này được gọi là Ma phương).

Ví dụ: Với N=3 và N=5 ta có

Phương pháp thành lập ma phương bậc lẻ (phương pháp Siamese)

• Xuất phát từ ô giữa của dòng đầu tiên đi theo hướng Đông Bắc để điền các số từ 1, 2,…, n²
• Khi điền số cần chú ý một số nguyên tắc sau:
  + Nếu vượt ra phía ngoài bên phải của bảng thì quay lại cột đầu tiên.
  + Nếu vượt ra phía ngoài bên trên của bảng thì quay lại dòng cuối cùng.
  + Nếu số đã điền k chia hết cho N thì số tiếp theo phải được viết vào ô ngay bên dưới ô đã điền k.

Cài đặt bằng ngôn ngữ Pascal:

PROGRAM Ma_Phuong;

VAR a:ARRAY[1..100,1..100] OF LONGINT;
    n, n2, k, i, j: LONGINT;

BEGIN
    write('n = ');
    readln(n);

    k:=1;
    i := 1;
    j := n DIV 2 + 1;
    n2 := n * n;
    WHILE k <= n2 DO
    BEGIN
         A[i,j] := k;
         IF k MOD n = 0 THEN
         BEGIN
            i :=  i + 1;
            IF i > n THEN i:=i-n;
         END
         ELSE
         BEGIN
             IF i = 1 THEN i := n ELSE dec(i);
             IF j = n THEN j := 1 ELSE inc(j);
         END;
         inc(k);
    END;

    FOR i:=1 TO n DO
    BEGIN
        FOR j:=1 TO n DO write(A[i,j]:3,' ');
        writeln;
    END;

    readln;                

END.

Mở rộng: thành lập ma phương bậc chẵn

Đối với ma phương bậc chẵn người ta chia thành 2 loại theo cách thành lập: Ma phương bậc chẵn – chẵn và ma phương bậc chẵn – lẻ

Ma phương bậc chẵn – chẵn là ma phương bậc 4n. Ví dụ như ma phương bậc 4, 8, 12, …

Có cách giải chung cho các loại ma phương bậc 4n. Để dễ nắm được phương pháp, trước tiên giải ma phương bậc 4.

Cách giải ma phương bậc 4.

- Bước 1: Kẻ ô vuông 4 hàng, 4 cột và 2 đường chéo.

- Bước 2: Đánh số từ 1 đến 16 theo hình chữ z, những số nào không nằm trên đường chéo thì xóa đi.

- Bước 3: Đánh lùi lại từ 16 tới 1 cũng theo hình chữ z, những số nào nằm trên đường chéo thì xóa đi.

- Bước 4: Gộp 2 hình vuông ở trên lại ta được ma phương bậc 4.

Cách giải ma phương bậc 4n (n > 1)

- Bước 1: Chia hình vuông ra làm các nhóm nhỏ mỗi nhóm có 4 dòng, 4 cột. Vẽ tất cả các đường chéo chính của các nhóm nhỏ này.

- Bước 2: Đánh số từ số nhỏ nhất đến số lớn nhất theo hình chữ z, số nào không nằm trên đường chéo thì xóa đi.

- Bước 3: Đánh lùi lại từ số lớn nhất đến số nhỏ nhất cũng theo hình chữ z, số nào nằm trên đường chéo thì xóa đi.

- Bước 4: Gộp 2 hình vuông đã lập ở trên lại với nhau, ta được ma phương cần lập.

Ma phương bậc chẵn – lẻ là ma phương bậc 2n trong đó n là số lẻ.

Ta sẽ thành lập thuật toán tổng quát giải ma phương bậc chẵn – lẻ: 4n + 2  (không có ma phương cấp 2)

Ta sẽ chia nhỏ hình vuông ra các ô lớn. Mỗi ô lớn có 2 ô dọc, 2 ô ngang. Sau đó thì tiến hành đi các ô lớn như cách di chuyển khi thiết lập ma phương lẻ. Kết hợp với quy tắc đi riêng cho các ô nhỏ (quy tắc LUX (nguồn gốc của nó là do các cách viết ở hình vẽ dưới đây của J. H. Conway). Trong đó 1 ma phương sẽ có tổng cộng n + 1 dòng L, đúng 1 dòng U và n – 1 dòng X. Luôn có 1 chữ U ở trung tâm ma phương và ta sẽ hoán đổi vị trí với L trên nó.

Áp dụng cho ma phương cấp 6. Ta có n = 1 nên có 1 + 1 = 2 dòng L, 1 dòng U và 1 – 1 = 0 dòng X. Các bước tiến hành như sau:

- Bước 1: Đi các ô vuông lớn

- Bước 2: Sắp xếp các số trong các ô vuông lớn theo qui tắc LUX

Áp dụng cho ma phương cấp 10. Lúc này ta có n = 2 nên sẽ có n + 1 = 3 dòng chữ L, 1 dòng chữ U và n – 1 = 1 dòng chữ X. Kết hợp Siamese cho ma phương lẻ và LUX ta có kết quả.

Cài đặt bằng C++ cho trường hợp tổng quát với mọi n>2

#include <iostream>
#include <iomanip>
using namespace std;
#define MAX 100

void maPhuongBacLe(int A[][MAX+1], int n)
{
    int i = 1;
    int j = n / 2 + 1;
    int k = 1;
    int n2 = n*n;
    while (k <= n2)
    {
        A[i][j] = k;

        if (k % n == 0)
        {
            i = i + 1;
            if ( i > n ) i = i - n;
        }
        else
        {
            if (i == 1)
                i = n;
            else
                i--;
            if (j == n)
                j = 1;
            else
                j++;
        }
        k++;
    }
}

void maPhuongBacChanChan(int A[][MAX+1], int n)
{
    int k = 1;
    int i = 1;
    int j = 1;
    int n2 = n * n;

    do
    {
        if ( (i - j) % 4 == 0 || (i + j -1) % 4 == 0)
            A[i][j] = k;
        else
            A[i][j] = n2 + 1 - k;

        k++;

        if (j==n)
        {
            j = 1;
            i++;
        }
        else
            j++;
    }
    while (k <= n2);
}

void LUX(int A[][MAX+1], int i, int j, int num, char ch)
{
    num = 1 + (num-1)*4;
    i = 1 + (i-1)*2;
    j = 1 + (j-1)*2;
    switch (ch)
    {
    case 'L':
        A[i][j] = num + 3;
        A[i][j+1] = num;
        A[i+1][j] = num + 1;
        A[i+1][j+1] = num + 2;
        break;
    case 'U':
        A[i][j] = num;
        A[i][j+1] = num + 3;
        A[i+1][j] = num + 1;
        A[i+1][j+1] = num + 2;
        break;
    case 'X':
        A[i][j] = num;
        A[i][j+1] = num + 3;
        A[i+1][j] = num + 2;
        A[i+1][j+1] = num + 1;
    }
}

void maPhuongBacChanLe(int A[][MAX+1], int n)
{
    int m = n / 2;
    int B[MAX+1][MAX+1];
    maPhuongBacLe(B, m);

    char ch;
    int m2 = m / 2;
    int i, j;
    for (i = 1; i <= m; i++)
        for (j = 1; j <= m; j++)
        {
            if (i <= m2)
                ch = 'L';
            else if (i == m2 + 1)
            {
                if (j == m2+1)
                    ch = 'U';
                else
                    ch = 'L';
            }
            else if (i == m2 + 2)
            {
                if (j == m2 + 1)
                    ch = 'L';
                else
                    ch = 'U';
            }
            else
                ch = 'X';
            LUX(A, i, j, B[i][j], ch);
        }

}

int main()
{

    int A[MAX+1][MAX+1];
    int n;
    do
    {
        cout << "n =  ";
        cin >> n;
    }
    while (n < 3 || n > MAX);

    if (n % 2 == 1)
    {
        maPhuongBacLe(A, n);
    }
    else if (n % 4 == 0)
    {
        maPhuongBacChanChan(A, n);
    }
    else
    {
        maPhuongBacChanLe(A, n);
    }

    int i, j;

    for (i = 1; i <= n; i++)
    {
        for (j = 1; j <= n; j++)
            cout << setw(3) << A[i][j] << " ";
        cout << endl;
    }

    return 0;
}

Nguồn: kithuatlaptrinh.tk