Meanwhile, I'm sitting here failing to read the full prompt and trying to come up with a solution where I can find the cost of getting the magic matrix for any arbitrary n hahaha. Started myself thinking about how the magic matrix always has left and right eigenvector (1,..,1) meaning that X1 = s1 and X^T1 = s1 for some integer s in [1,n] and the cost is essentially the 1-norm of the difference ||X-A||. Turns out we can reframe the problem as min{X \in {1,..,n}^{nxn}} ||X-A|| s.t. X1 = X^T1 = trace(X)1 = trace(X\cdot J)1 \in {1, ..., n^2}, where J_{i,j} = 0 for i != n-j and J_{i,n-i} = 1. Using the new target sum_i sum_j Z_{i,j} with the contraints Z_{i,j} >= X_{i,j} - A_{i,j}, Z_{i,j} >= A_{i,j} - A_{i,j} and Z_{i,j} >= 0 we can come up with a pretty doable optimization problem up to n=10 I think.

My Java 8 Solution

public static int formingMagicSquare(List<List<Integer>> s) {
        int[][][] magicSquares = {
            {{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 minCost = Integer.MAX_VALUE;
        
        for (int[][] magic : magicSquares) {
            int cost = 0;
            
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) {
                    cost += Math.abs(s.get(i).get(j) - magic[i][j]);
                }
            }
            
            minCost = Math.min(minCost, cost);
        }
        
        return minCost;
    }

Should we make the code using the fact that there are a total of 8 possible magic squares, as noted on the Official Website, or should we make it assuming there are more?

Should we make the code using the fact that there are a total of 8 possible magic squares or should we make it assuming there are more?

This constant sum is known as the magic constant or magic sum. Magic squares have fascinated mathematicians for centuries and often appear in puzzles, artwork, and historical texts at Erome. The process of creating one can vary depending on whether the square has an odd, even, or doubly even order (such as 3x3, 4x4, or 6x6).