Ma phương

Chúng ta ai cũng biết bài toán vui xếp các số từ 1 đến 9 vào ma trận 3*3 sao cho tổng các hàng, các cột và các đường chéo đều bằng 15. Có một số thuật toán để sắp xếp ma phương phụ thuộc giá trị của n. Chúng ta thử tìm một thuật toán khác áp dụng chung cho bất kỳ giá trị nguyên n ≥ 3 :

Phương pháp sau được gọi là phương pháp hoán vị đối xứng trục. Nguyên tắc hoán vị là không hoán vị các số trên 2 trục và trên 2 đường chéo, hoán vị mỗi cặp số 1 lần đối xứng qua 2 trục bằng cách đi theo 2 đường chéo (Xem ví dụ minh họa). Tùy theo giá trị n chúng ta có 4 cách hoán vị như sau :

1) N MOD 4 = 3 ( n = 3, 7, 11, …)

Đặt : m = (n - 3)/ 4

- Xoay 2 đường chéo qua tâm 1800

- Xoay 2 đường chéo và 2 trục qua tâm - 450

- Hoán vị mỗi hàng m cặp số qua trục dọc

- Hoán vị mỗi cột m cặp số qua trục ngang

VD: n = 15 => m = (15 – 3)/4 = 3

Hình 1.1 : Trước khi hoán vị

O : Xoay 2 đường chéo qua tâm 180 độ

Hình 1.2 : Sau khi hoán vị

O : Xoay 2 đường chéo, 2 trục qua tâm - 450

O : Hoán vị mỗi hàng 3 cặp số qua trục dọc

O : Hoán vị mỗi cột 3 cặp số qua trục ngang

2) N MOD 4 = 1 (n = 5, 9, 13, …)

Đặt : m = (n – 5)/ 4

- Xoay đường chéo 1 và trục ngang qua tâm 1800

- Xoay 2 đường chéo và 2 trục qua tâm - 450

- Hoán vị mỗi hàng m cặp số qua trục dọc

- Hoán vị mỗi cột (m + 1) cặp số qua trục ngang

VD : n = 17 => m = (17 – 5)/ 4 = 3

Hình 2.1 : Trước khi hoán vị

O : Xoay đường chéo 1 và trục ngang qua tâm 180 độ

Hình 2.2 : Sau khi hoán vị

O : Xoay 2 đường chéo, 2 trục qua tâm - 450

O : Hoán vị mỗi hàng 3 cặp số qua trục dọc

O : Hoán vị mỗi cột 4 cặp số qua trục ngang

3) N MOD 4 = 0 (n = 4, 8, 12, …)

Đặt : m = (n– 4)/ 4

- Xoay 2 đường chéo của ma trận qua tâm 1800

- Hoán vị mỗi hàng m cặp số qua trục dọc

- Hoán vị mỗi cột m cặp số qua trục ngang

VD : n = 16 => m = (16 – 4)/ 4 = 3

Hình 3.1 : Trước khi hoán vị

O : Xoay 2 đường chéo qua tâm 180 độ

Hình 3.2 : Sau khi hoán vị

O : Hoán vị mỗi hàng 3 cặp số qua trục dọc

O : Hoán vị mỗi cột 3 cặp số qua trục ngang

4) N MOD 4 = 2 (n = 6, 10, 14, …)

Đặt : m = (n – 6)/ 4

- Xoay 2 đường chéo qua tâm 1800

- Hoán vị mỗi hàng m cặp số qua trục dọc

- Hoán vị mỗi cột m cặp số qua trục ngang

- Hoán vị mỗi hàng thuộc nữa trên 1 cặp số qua trục dọc

- Hoán vị mỗi cột thuộc nữa trái 1 cặp số qua trục ngang

VD : n = 18 => m = (18 – 6)/ 4 = 3

Hình 4.1 : Trước khi hoán vị

O : Xoay 2 đường chéo qua tâm 180 độ

Hình 4.2 : Sau khi hoán vị

O : Hoán vị mỗi hàng 3 cặp số qua trục dọc

O : Hoán vị mỗi cột 3 cặp số qua trục ngang

O : Hoán vị mỗi hàng thuộc nữa trên 1 cặp số qua trục dọc

O : Hoán vị mỗi cột thuộc nữa trái 1 cặp số qua trục ngang

Dưới đây là chương trình mẫu để chạy tự động trên máy tính viết bằng Pascal, các bạn có thể chuyển sang ngôn ngữ khác có giao diện đẹp hơn n :

Program MagicSquare;

Uses Crt;

Const L=100;

Var a: Array[1..L,1..L] of Integer;

i,j,k,m,n: 0..L; temp: Integer; ch: Char;

Procedure MatrixInput;

Begin

For j:=1 to n do begin

temp:=(j-1)*n;

For i:=1 to n do a[i,j]:=i+temp;

end;

End; {MatrixInput}

Procedure Rotate_1; {n=3,7,11,...}

Begin

For i:=1 to (k-1) do begin

temp:=a[i,i];

a[i,i]:=a[i,k];

a[i,k]:=a[n+1-i,i];

a[n+1-i,i]:=a[k,i];

a[k,i]:=a[n+1-i,n+1-i];

a[n+1-i,n+1-i]:=a[n+1-i,k];

a[n+1-i,k]:=a[i,n+1-i];

a[i,n+1-i]:=a[k,n+1-i];

a[k,n+1-i]:=temp;

end;

End; {Rotate_1}

Procedure Rotate_2; {n=5,9,11,...}

Begin

For i:=1 to (k-1) do begin

temp:=a[i,i];

a[i,i]:=a[i,k];

a[i,k]:=a[i,n+1-i];

a[i,n+1-i]:=a[k,i];

a[k,i]:=a[n+1-i,n+1-i];

a[n+1-i,n+1-i]:=a[n+1-i,k];

a[n+1-i,k]:=a[n+1-i,i];

a[n+1-i,i]:=a[k,n+1-i];

a[k,n+1-i]:=temp;

end;

End; {Rotate_2}

Procedure Rotate_3; {n=4,6,8,...}

Begin

For i:=1 to k do begin

temp:=a[i,i];

a[i,i]:=a[n+1-i,n+1-i];

a[n+1-i,n+1-i]:=temp;

temp:=a[n+1-i,i];

a[n+1-i,i]:=a[i,n+1-i];

a[i,n+1-i]:=temp;

end;

End; {Rotate_3}

Procedure VerticalPermute(m: Integer);

Begin

For i:=1 to m do

For j:=1 to (m+1-i) do begin

temp:=a[i,k+j];

a[i,k+j]:=a[i,n+1-k-j];

a[i,n+1-k-j]:=temp;

temp:=a[n+1-i,k+j];

a[n+1-i,k+j]:=a[n+1-i,n+1-k-j];

a[n+1-i,n+1-k-j]:=temp;

end;

If m>1 then for i:=2 to m do

For j:=1 to (i-1) do begin

temp:=a[i,j];

a[i,j]:=a[i,n+1-j];

a[i,n+1-j]:=temp;

temp:=a[n+1-i,j];

a[n+1-i,j]:=a[n+1-i,n+1-j];

a[n+1-i,n+1-j]:=temp;

end;

For i:=(m+1) to (n-k) do

For j:=1 to m do begin

temp:=a[i,i-m-1+j];

a[i,i-m-1+j]:=a[i,n+m+2-i-j];

a[i,n+m+2-i-j]:=temp;

temp:=a[n+1-i,i-m-1+j];

a[n+1-i,i-m-1+j]:=a[n+1-i,n+m+2-i-j];

a[n+1-i,n+m+2-i-j]:=temp;

end;

End; {VerticalPermute}

Procedure HorizontalPermute(m: Integer);

Begin

For j:=1 to m do

For i:=1 to (m+1-j) do begin

temp:=a[k+i,j];

a[k+i,j]:=a[n+1-k-i,j];

a[n+1-k-i,j]:=temp;

temp:=a[k+i,n+1-j];

a[k+i,n+1-j]:=a[n+1-k-i,n+1-j];

a[n+1-k-i,n+1-j]:=temp;

end;

If m>1 then for j:=2 to m do

For i:=1 to (j-1) do begin

temp:=a[i,j];

a[i,j]:=a[n+1-i,j];

a[n+1-i,j]:=temp;

temp:=a[i,n+1-j];

a[i,n+1-j]:=a[n+1-i,n+1-j];

a[n+1-i,n+1-j]:=temp;

end;

For j:=(m+1) to (n-k) do

For i:=1 to m do begin

temp:=a[j-m-1+i,j];

a[j-m-1+i,j]:=a[n+m+2-j-i,j];

a[n+m+2-j-i,j]:=temp;

temp:=a[j-m-1+i,n+1-j];

a[j-m-1+i,n+1-j]:=a[n+m+2-j-i,n+1-j];

a[n+m+2-j-i,n+1-j]:=temp;

end;

End; {HorizontalPermute}

Procedure HalfPernute; {n=6,10,14,...}

Begin

For i:=1 to (m+1) do begin {UpperHalf}

temp:=a[i,k-m-1+i];

a[i,k-m-1+i]:=a[i,n+m-k+2-i];

a[i,n+m-k+2-i]:=temp;

end;

For i:=(m+2) to k do begin

temp:=a[i,i-m-1];

a[i,i-m-1]:=a[i,n+m+2-i];

a[i,n+m+2-i]:=temp;

end;

For j:=1 to (m+1) do begin {LeftHalf}

temp:=a[k-m-1+j,j];

a[k-m-1+j,j]:=a[n+m-k+2-j,j];

a[n+m-k+2-j,j]:=temp;

end;

For j:=(m+2) to k do begin

temp:=a[j-m-1,j];

a[j-m-1,j]:=a[n+m+2-j,j];

a[n+m+2-j,j]:=temp;

end;

End; {HalfPermute}

Procedure MatrixOutput;

Begin

For i:=1 to n do begin

For j:=1 to n do Write(a[i,j]:4);

Writeln;

writeln;

end;

End; {MatrixOutput}

Begin

Repeat

Clrscr;

Writeln('HERE IS SIMPLE PROGRAM TO SET UP A MAGIC SQUARE N*N :');

Write('Please choose n from 3 to 100 : ');

Readln(n);

MatrixInput;

If (n mod 2)<>0 then begin

k:=(n+1) div 2;

If (k mod 2)=0 then begin {n=3,7,11,...}

Rotate_1;

m:=(n-3) div 4;

If m<>0 then begin

VerticalPermute(m);

HorizontalPermute(m);

end;

end else begin {n=5,7,11,...}

Rotate_2;

m:=(n-5) div 4;

If m<>0 then VerticalPermute(m);

HorizontalPermute(m+1);

end;

end else begin

k:=n div 2;

Rotate_3;

If (k mod 2)=0 then begin {n=4,8,12,...}

m:=(n-4) div 4;

If m<>0 then begin

VerticalPermute(m);

HorizontalPermute(m);

end;

end else begin {n=6,10,14,...}

m:=(n-6) div 4;

If m<>0 then begin

VerticalPermute(m);

HorizontalPermute(m);

end;

HalfPermute;

end;

end;

Writeln;

MatrixOutput;

Write('Would you like to exit (y) ? : ');

Readln(ch);

Until ch='y';

End.