Description

Submission

With brute-force, since the magic square is only of order 3

• O(9!) = O(1)

#include <bits/stdc++.h>

using namespace std;

// Complete the formingMagicSquare function below.

bool isMagicSquare(vector<vector<int>>& t)
{
    int sum = 0;
    for(int i = 0; i < t.size(); ++i) {
        int s = 0;
        for(int j = 0; j < t.size(); ++j) {
            s += t[i][j];
        }
        if(sum == 0) sum = s;
        if(sum != s) return false;
    }
    for(int j = 0; j < t.size(); ++j) {
        int s = 0;
        for(int i = 0; i < t.size(); ++i) {
            s += t[i][j];
        }
        if(sum != s) return false;
    }
    int s1 = 0, s2 = 0;
    for(int i = 0; i < t.size(); ++i) {
        s1 += t[i][i];
        s2 += t[t.size() - i - 1][i];
    }
    if(s1 != sum) return false;
    if(s2 != sum) return false;
    return true;
}

int getDistance(vector<vector<int>>& t, vector<vector<int>>& s) {
    int sum = 0;
    for(int i = 0; i < t.size(); ++i) {
        for(int j = 0; j < t.size(); ++j) {
            sum += (t[i][j] > s[i][j] ? t[i][j] - s[i][j] : s[i][j] - t[i][j]);
        }
    } 

    return sum;
}

void magicSquare(int x, int y, vector<vector<int>>& t, vector<int>& mark, vector<vector<int>>& s, int& min)
{
    for(int i = 1; i <= 9; i++) {
        if(mark[i] == 0) {
            mark[i] = 1;
            t[x][y] = i;
            int nextX = x + (y + 1) / 3;
            int nextY = (y + 1) % 3;
            if(nextX == 3 && isMagicSquare(t)) { // if it satisfies
                // get the value
                int d = getDistance(t, s);
                // update the smallest
                if(d < min) min = d;
            } else {
                magicSquare(nextX, nextY, t, mark, s, min);
            }
            mark[i] = 0;
        }
    }
}

int formingMagicSquare(vector<vector<int>> s) {
    vector<vector<int>> t = {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}};
    vector<int> mark = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
    int min = 10000;
    magicSquare(0, 0, t, mark, s, min);
    return min;
}

int main()
{
    ofstream fout(getenv("OUTPUT_PATH"));

    vector<vector<int>> s(3);
    for (int i = 0; i < 3; i++) {
        s[i].resize(3);

        for (int j = 0; j < 3; j++) {
            cin >> s[i][j];
        }

        cin.ignore(numeric_limits<streamsize>::max(), '\n');
    }

    int result = formingMagicSquare(s);

    fout << result << "\n";

    fout.close();

    return 0;
}