Magic Square là một ma trận có kích thước n x n. Trong đó, khi cộng các số trên cùng một hàng hoặc một cột bất kỳ, hoặc trên một trong hai đường chéo của ma trận, bạn đều nhận được một số giống nhau, số đó gọi là The Magic Constant.
Ví dụ xét Magic Square có kích thước 3 x 3 sau:
8 1 6
3 5 7
4 9 2
Hàng 1: 8 + 1 + 6 = 15
Hàng 2: 3 + 5 + 7 = 15
Hàng 3: 4 + 9 + 2 = 15
Cột 1: 8 + 3 + 4 = 15
Cột 2: 1 + 5 + 9 = 15
Cột 3: 6 + 7 + 2 = 15
Đường chéo 1: 8 + 5 + 2 = 15
Đường chéo 2: 4 + 5 + 6 = 15
Đề bài:
Đây là một bài tập mà tôi được gặp trên HackerRank: https://www.hackerrank.com/challenges/magic-square-forming. Bài có độ khó Medium. Yêu cầu của bài tập sẽ cho một ma trận 3 x 3 bất kỳ, ma trận này chưa phải là Magic Square, hãy tính chi phí tối thiểu để chuyển ma trận này thành Magic Square.
Ví dụ, cho ma trận gốc sau:
5 3 4
1 5 8
6 4 2
Magic Square tốt nhất có thể tạo nên từ ma trận gốc là:
8 3 4
1 5 9
6 7 2
Để chuyển từ ma trận gốc thành Magic Square trên, cần phải sửa 3 số ở vị trí [0,0]=5, [1,2]=8, và [2,1]=4.
Chi phí để chuyển được từ ma trận gốc thành Magic Square được tính như sau:
|5 - 8| + |8 - 9| + |4 - 7| = 3 + 1 + 3 = 7.
Vậy 7 là đáp án cần tìm.
Lời bàn:
Lúc đầu, tôi khá lúng túng để tìm giải thuật cho bài tập này. Dự định ban đầu của tôi là từ ma trận gốc, sẽ cố gắng tìm sự liên quan giữa các con số hoặc giá trị của hàng và cột để tính toán ra chi phí tối thiểu. Tuy nhiên, tất cả các giải thuật đều không thể vượt mọi test cases. Sau khi tìm hiểu kỹ hơn về Magic Square trên Wiki, tôi phát hiện có thể giải bài tập này bằng cách sử dụng bảng tra cứu. Vì thật sự chỉ có tất cả 8 Magic Square kích thước 3 x 3, nên chúng ta có thể chuẩn bị sẵn 8 Magic Square, sau đó đối chiếu từng Magic Square với ma trận gốc, và trả về chi phí tốt nhất.
Cho input của chương trình là ma trận gốc bên dưới:
5 3 4
1 5 8
6 4 2
Chúng ta có cài đặt C của chương trình như sau:
#include <stdio.h>
#include <limits.h>
#include <math.h>
int main() {
int m[8][3][3] = {
{{8, 1, 6}, {3, 5, 7}, {4, 9, 2}},
{{6, 1, 8}, {7, 5, 3}, {2, 9, 4}},
{{4, 9, 2}, {3, 5, 7}, {8, 1, 6}},
{{2, 9, 4}, {7, 5, 3}, {6, 1, 8}},
{{8, 3, 4}, {1, 5, 9}, {6, 7, 2}},
{{4, 3, 8}, {9, 5, 1}, {2, 7, 6}},
{{6, 7, 2}, {1, 5, 9}, {8, 3, 4}},
{{2, 7, 6}, {9, 5, 1}, {4, 3, 8}}
};
int a[3][3];
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
scanf("%d", &a[i][j]);
int min = INT_MAX;
for (int h = 0; h < 8; h++) {
int cost = 0;
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
cost += abs(a[i][j] - m[h][i][j]);
if (cost < min) min = cost;
}
printf("%d", min);
return 0;
}
Chú thích:
- Để chuẩn bị sẵn bảng tra cứu, tôi sử dụng một mảng 3 chiều m có kích thước 8 x 3 x 3 để chứa tất cả 8 trường hợp Magic Square 3 x 3.
- Để đọc đầu vào từ dòng lệnh, tôi sử dụng một mảng 2 chiều 3 x 3 để lưu ma trận gốc.
- Để lưu chi phí tối thiểu, tôi dùng biến min. Dùng 3 vòng lặp lồng nhau để chạy qua 8 ma trận Magic Square và so sánh từng phần tử của mỗi Magic Square với từng phần tử của ma trận gốc. Chi phí được tính bằng tổng các trị tuyệt đối của hiệu giữa hai phần tử.
- Sau khi có chi phí, so sánh với min, nếu cost < min thì cập nhật giá trị của cost và min và tiếp tục với các Magic Square còn lại.
- Sau cùng, min sẽ lưu giữ chi phí tốt nhất.
Mở rộng
Tuy nhiên, thay vì gán sẵn các trường hợp của Magic Square, nếu có thể tự sinh ra tất cả các Magic Square thì vẫn tốt hơn. Giải thuật để sinh ra Magic Square bất kỳ có kích thước bất kỳ, các bạn có thể tham khảo ở trang GeeksForGeeks. Cảm ơn các bạn đã đọc bài viết.
Loading...