GIẢI MA PHƯƠNG KỲ ẢO

(The Magic Square Tutorial)

writer: @arieswhite

---

TỔNG QUAN

Định nghĩa:

Ma trận kì ảo (Magic Square) trong bài viết là một cách sắp xếp n² 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, đường chéo chính và đường chéo phụ đều bằng nhau.

Tồn tại ma trận kì ảo chuẩn cho mọi bậc n ≥ 1 trừ n = 2.

Ma phương lẻ

Là ma trận với bậc n là số lẻ (n%2==0)

Ma phương chẵn

Là ma trận với bậc có dạng 4n

Ma phương chẵn lẻ

Là ma trận với bậc có dạng 4n + 2

Chú ý: Để đơn giản cho việc tính toán và code, chúng ta sẽ bắt đầu bằng chỉ số [0][0] trên mảng 2 chiều

---

MA PHƯƠNG LẺ

Cách dựng MSO

Có nhiều cách, trong bài viết này tác giả xin trình bài 1 cách đi như sau:

• Bước 1: Chọn vị trí bắt đầu tại ô thuộc hàng đầu tiên, cột chính giữa [0][n/2]
• Bước 2: Tại mỗi bước, di chuyển lên ô phía trên bên trái [i-1][j+1]
  • Nếu đi quá bảng về phía trên, di chuyển đến ô ở hàng cuối cùng, cùng cột
  • Nếu đi quá bảng về phía bên phải, di chuyển đến ô ở cột đầu tiên, cùng hàng
  • Nếu đi đến ô góc của bảng, lùi xuống một hàng
  • Nếu ô hướng đến đã điền rồi, lùi xuống một hàng
    -> Lặp lại cho tới khi đã điền hết bảng

CODE MSO

CODE

int i = 0, j = n >> 1;
FOR(t,1,n*n)
{
    f[i][j] = t;
    if(i == 0 && j == n-1) i++;
    else
        i = (i-1+n)%n, j = (j+1)%n;
    if(f[i][j]!=0) i+=2, j-=1;
}

Mẹo

 i = (i-1+n)%n, j = (j+1)%n;

Vì chúng ta chọn chỉ số 0,0 nên ta dễ dàng dùng phép Mod cho n mỗi khi đi quá bảng

---

MA PHƯƠNG CHẴN

Cách dựng MSE

• Bước 1: chia bảng thành từng nhóm 4x4 (trên mỗi nhóm sẽ có 1 đường chéo chính và 1 đường chéo phụ)
• Bước 2: Điền số từ trái sang phải từ trên xuống dưới
  • Ô nào thuộc 2 đường chéo của mỗi nhóm thì điền, không thì chỉ tăng biến đếm lên
• Bước 3: Điền những số còn lại vào bảng từ phải sang trái từ dưới lên trên
  • Ô nào còn trống thì điền

CODE MSE

Code

int val = 0;
    FOR(i,0,n-1)
    {
        FOR(j,0,n-1)
        {
            val++;
            if(i%4 - j%4 == 0 || i%4 + j%4 == 3) f[i][j] = val;
        }
    }
    val = 0;
    FOD(i,n-1,0)
    {
        FOD(j,n-1,0)
        {
            val++;
            if(!f[i][j]) f[i][j] = val;
        }
    }

Mẹo

• Cách xác định đường chéo chính: Các ô trên đường chéo sẽ có hiệu chỉ số bằng nhau (ở đây: i-j == 0)
• Cách xác định đường chéo phụ: Các ô trên đường chéo sẽ có tổng chỉ số bằng nhau (ở đây: i+j == 3)
• Xác định đường chéo chính phụ của từng nhóm: Do bảng được chia đều thành các ma trận nhỏ 4x4 nên chỉ số khi %4 sẽ lặp lại theo chu kỳ
  -> CTTQ:
  • Đường chéo chính: i%4 - j%4
  • Đường chéo phụ: i%4 + j%4,

---

MA PHƯƠNG CHẴN LẺ

Cách dựng MSEO

• Chia ma trận thành từng nhóm 2x2
• Xem mỗi nhóm như một ô vuông
  -> Ta có: Thứ tự điền theo nhóm giống với cách đi trên ma phương lẻ

Quy tắc điền số vào mỗi ô trong nhóm

• Theo thứ tự điền vào từng ô trong nhóm ta có được 3 quy tắc điền là: L, U, X (xem hình)
  

• Ta có bậc của ma phương sẽ có dạng: 4n + 2
  Tính từ trên xuống sẽ có
  -> n+1 hàng đầu tiên điền theo quy tắc L
  -> 1 hàng tiếp theo điền theo quy tắc U
  -> n - 1 hàng tiếp theo điền theo quy tắc X

  Chú ý
  • Nhóm thuộc ô chính giữa (tức là tại vị trí hàng giữa, cột giữa) sẽ được điền theo quy tắc U
  • Nhóm ở dưới ô đó sẽ được điền theo quy tắc L
    (nghĩa là đổi quy tắc 2 ô f[m][m] và f[m+1][m]) (với m = n/4)
    

CODE MSEO

Code

//Hàm kiểm tra loại L
bool typeL(int i, int j, int m)
{
    int sl = n / 4 + 1;
    if(i==m && j==m) return false;
    if(i==m+1 && j == m) return true;
    if(i < sl) return true;
    return false;
}
//Hàm kiểm tra loại U
bool typeU(int i, int j, int m)
{
    int sl = n / 4 + 1;
    if(i==m && j == m) return true;
    if(i==sl && j == m) return false;
    if(i==sl) return true;
    return false;
}
//Hàm điền theo nhóm 2x2
void mgfill(int i, int j, int m, int &val)
{
    int x = i*2 + 1, y = j * 2 + 1;
    /*
        N = 4n + 2
        -> L : n + 1 rows
        -> U : 1 rows
        -> X : n - 1 rows;
    */
    //loai L
    if(typeL(i,j,m >> 1))
    {
        f[x-1][y] = val;
        f[x][y-1] = val+1;
        f[x][y] = val+2;
        f[x-1][y-1] = val+3;
        val += 4;
    }
    else //loai U
    if(typeU(i,j,m >> 1))
    {
        f[x-1][y-1] = val;
        f[x][y-1] = val+1;
        f[x][y] = val+2;
        f[x-1][y] = val+3;
        val += 4;
    }
    else // loai X
    {
        f[x-1][y-1] = val;
        f[x][y] = val+1;
        f[x][y-1] = val+2;
        f[x-1][y] = val+3;
        val += 4;
    }
}
//The Magic Square 4n+2
void mgEvenOdd()
{
    int m = n >> 1;
    bool mark[100][100];

    memset(mark, 0, sizeof(mark));

    int i = 0, j = m >> 1;
    int val = 1;

    FOR(t,1,m*m)
    {
        mark[i][j] = 1;

        mgfill(i,j,m,val);

        if(i == 0 && j == m-1) i++;
        else
            i = (i-1+n)%m, j = (j+1)%m;

        if(mark[i][j]!=0) i+=2, j-=1;
    }
}

Code rút ngắn hàm fill

const int dx[5] = {-1,0,0,-1};
const int dy[5][5] =
{{0,-1,0,-1},//L
{-1,-1,0,0},//U
{-1,0,-1,0}//X
};
void mgfill(int i, int j, int m, int &val)
{
    int x = i*2 + 1, y = j * 2 + 1;
    /*
        N = 4n + 2
        -> L : n + 1 rows
        -> U : 1 rows
        -> X : n - 1 rows;
    */

    //loai L : 0, U : 1, X : 2
    int t = 2;
    if(typeL(i,j,m >> 1)) t = 0;
    else
    if(typeU(i,j,m >> 1)) t = 1;
    
    FOR(i,0,3)
    {
        f[x + dx[i]][y + dy[t][i]] = val;
        val++;
    }
}

Mẹo
Sử dụng các mẹo đã làm ở 2 ma phương trước + code cờ-lin vừa code vừa check bug

Chương trình check đáp án

Code

void resultError()
{
​​  cout << "This is not Magic Square!" << "\n";
}
bool mgCheck()
{
​​  int Val = (n*(n*n+1))/2;
​​  int sumCol[100], sumRow[100], priA = 0, secA = 0;
​​  memset(sumCol,0,sizeof(sumCol));
​​  memset(sumRow,0,sizeof(sumRow));
​​  FOR(i,0,n-1)
​​  {
​​      FOR(j,0,n-1)
​​      {
​​          sumRow[i] += f[i][j];
​​          sumCol[j] += f[i][j];
​​          if(i == j) priA += f[i][j];
​​          if(i+j == (n-1)*2) secA += f[i][j];
​​      }
​​  }
​​  FOR(i,0,n-1)
​​  {
​​      if(sumRow[i] != Val || sumCol[i] != Val) {resultError(); return 0;}
​​  }
​​  if(priA != Val && secA != Val) {resultError(); return 0;}
​​  return 1;
}

---

LỜI KẾT

Bài này chỉ cần nắm được các quy luật, code trâu chắc, biết thêm một vài mẹo để code được clean, nhanh, đỡ bug hơn, vậy thôi!

Thân chào và Gudluk!

Từ nay về sau không còn sợ Magic Square nữa nhé! :> trừ bài Super Magic Square

---

Nguồn tham khảo:

Thuật Toán giải ma phương (ma trận kì ảo) - ITS
Một vài đặc tính của ma phương - GS Tiến Sĩ Tô Đồng
Magic Square - Wiki

fullsourcecode

Tags: Thuật toán giải ma phương, ma phương chẵn, ma phương lẻ, ma phương chẵn lẻ, giải ma phương