• + 1 comment

    Probably the simplest solution you could think of

    // All eight possible magic squares
    static const vector<vector<int>> squares[8] = {
        {
            { 8, 3, 4 },
            { 1, 5, 9 },
            { 6, 7, 2 }
        },
        {
            { 6, 7, 2 },
            { 1, 5, 9 },
            { 8, 3, 4 }
        },
        {
            { 4, 3, 8 },
            { 9, 5, 1 },
            { 2, 7, 6 }
        },
        {
            { 2, 7, 6 },
            { 9, 5, 1 },
            { 4, 3, 8 }
        },
        {
            { 6, 1, 8 },
            { 7, 5, 3 },
            { 2, 9, 4 }
        },
        {
            { 2, 9, 4 },
            { 7, 5, 3 },
            { 6, 1, 8 }
        },
        {
            { 8, 1, 6 },
            { 3, 5, 7 },
            { 4, 9, 2 }
        },
        {
            { 4, 9, 2 },
            { 3, 5, 7 },
            { 8, 1, 6 }
        }
    };
    
    int computeCost(const vector<vector<int>> &a, const vector<vector<int>> &b) {
        int cost = 0;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                cost += abs(a[i][j] - b[i][j]);
            }
        }
        return cost;
    }
    
    int formingMagicSquare(vector<vector<int>> s) {
        int minCost = computeCost(s, squares[0]);
        
        for (int i = 1; i < 8; i++) {
            int c = computeCost(s, squares[i]);
            if (c < minCost) minCost = c;
        }
        
        return minCost;
    }