Bài toán : Forming a Magic Square
Mức độ: Medium

Link: https://www.hackerrank.com/challenges/magic-square-forming/problem
Tóm tắt bài toán : Tìm minCost để chuyển 1 ma trận input thành 1 Magic Square với size 3×3 có tổng tất cả các hàng, cột,chéo đều bằng 15 với các số từ 1-9.
Solution:
Quá trình đến lời giải: Sau khi đọc lướt qua đề, tôi cũng hiểu được yêu cầu bài toán là gì. Ngồi ngẫm bài toán được 5 phút thấy bế tắc với cách so sánh từng hàng, cột, đường chéo của 2d array input sao cho có thể thay đổi về 2d array cần tìm, kiểu như ta sẽ phải xác định từng điểm một rồi cộng, trừ,… Tôi đi đến ngõ cụt với có nhiều trường hợp có thể xảy ra và cách thức làm sẽ rẩt phức tạp. Sau đó tham khảo ý kiến của anh rất Pro ngồi cạnh và đã được khai sáng bằng câu nói “Bài Magic Square này nó có một khuân mẫu “. Ồ khuôn mẫu, đúng rồi ! Tôi liền bắt tay vào kiểm tra thì thấy quả thật là như vậy. Vì trong Magic Square này càc số được sắp xếp từ 1 đến 9 trong 3×3 nên để có tổng hàng,cột, chéo bằng 15 chắc chắn phải có quy tắc sắp xếp nào đấy. Tôi nhận ra để có thể có được Magic Square tâm của ma trận đó bắt buộc phải bằng 5 và các số xung quanh 2 bên nó cộng lại phải bằng 10. Ok! Đến đây mọi chuyệncoi như đã giải quyết xong. Tôi lấy ví dụ của bài toán làm khuôn mẫu rồi dùng hoán vị các vị trí xung quanh theo quy tắc, loáy ngoáy một hồi tôi đã ra được 8 khuôn mẫu Magic Square cần tìm. Việc còn lại chỉ là tính tổng cost của mỗi matrix để chuyển matrix input đầu vào xem cái nào nhỏ nhất là xong.
Kết luận: bài toán rất khó nếu không biết cách làm và rất dễ nếu biết cách làm 🙂

Code mẫu tham khảo :

int MagicSquare1[3][3] = {
        {8,3,4},
        {1,5,9},
        {6,7,2}
    };
    int MagicSquare2[3][3] = {
        {6,1,8},
        {7,5,3},
        {2,9,4}
    };
    int MagicSquare3[3][3] = {
        {2,7,6},
        {9,5,1},
        {4,3,8}
    };
    int MagicSquare4[3][3] = {
        {4,9,2},
        {3,5,7},
        {8,1,6}
    };
     int MagicSquare5[3][3] = {
        {8,1,6},
        {3,5,7},
        {4,9,2}
    };
    int MagicSquare6[3][3] = {
        {6,7,2},
        {1,5,9},
        {8,3,4}
    };
    int MagicSquare7[3][3] = {
        {2,9,4},
        {7,5,3},
        {6,1,8}
    };
    int MagicSquare8[3][3] = {
        {4,3,8},
        {9,5,1},
        {2,7,6}
    };
int formingMagicSquare(vector<vector<int>> s) {
    int sum1=0;
    int sum2=0;
    int sum3=0;
    int sum4=0;
    int sum5=0;
    int sum6=0;
    int sum7=0;
    int sum8=0;
    for(int i=0;i<3;i++) {
        for(int j=0;j<3;j++) {
            if(s[i][j]!=MagicSquare1[i][j])
                sum1+=abs(s[i][j]-MagicSquare1[i][j]);
            if(s[i][j]!=MagicSquare2[i][j])
                sum2+=abs(s[i][j]-MagicSquare2[i][j]);
            if(s[i][j]!=MagicSquare3[i][j])
                sum3+=abs(s[i][j]-MagicSquare3[i][j]);
            if(s[i][j]!=MagicSquare4[i][j])
                sum4+=abs(s[i][j]-MagicSquare4[i][j]);
            if(s[i][j]!=MagicSquare5[i][j])
                sum5+=abs(s[i][j]-MagicSquare5[i][j]);
            if(s[i][j]!=MagicSquare6[i][j])
                sum6+=abs(s[i][j]-MagicSquare6[i][j]);
            if(s[i][j]!=MagicSquare7[i][j])
                sum7+=abs(s[i][j]-MagicSquare7[i][j]);
            if(s[i][j]!=MagicSquare8[i][j])
                sum8+=abs(s[i][j]-MagicSquare8[i][j]);
        }
    }
    int minCost = (sum1<=sum2) ? sum1 : sum2;
    minCost=(minCost<=sum3) ? minCost : sum3;
    minCost=(minCost<=sum4) ? minCost : sum4;
    minCost=(minCost<=sum5) ? minCost : sum5;
    minCost=(minCost<=sum6) ? minCost : sum6;
    minCost=(minCost<=sum7) ? minCost : sum7;
    minCost=(minCost<=sum8) ? minCost : sum8;
    return minCost;

Note: Mình dùng C++ để viết nhưng bạn hoàn toàn có thể dùng các ngôn ngữ khác cũng tương tự như vậy. Code mình dùng hơi xấu vì chưa nghĩ ra cách để clean code cho nó đẹp. Nhưng ít ra dễ hiểu mà 😀

Conal Dev