I am not sure that this particular challenge should be listed under "easy" as written. All the other challenges up to this point have been straightforward "in the head" problems. This one requires quite a bit more set-up.

The "easy" portion of this task is to evaluate cost as defined is simply comparing lists of lists (in python, anyway). Generating the matrix of possible magic squares is far more time-consuming than anything up to this point, and might best have been it's own "Generate 3x3 Magic Squares" challenge, with "Magic Square Forming" following directly after.

Were I to see this particular excercise in a "team-coding" evaluation for a job interview, my first suggestion to my partner would be to google for the list of possible 3x3 magic squares and just use that as a look up table, since the boundaries are well understood and fast and lazy will always win!

class Magic(object):

    pre = [
            [[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]],
            ]

    def evaluate(self, s):
        totals = []
        for p in self.pre:
            total = 0
            for p_row, s_row in zip(p, s):
                for i, j in zip(p_row, s_row):
                    if not i == j:
                        total += max([i, j]) - min([i, j])
            totals.append(total)
        return min(totals)

All of the posted solutions require pre-computing all eight magic squares. I wanted to offer a few suggestions on how to generate them -- or at least show what I did.

We can start with two observations: a) the "middle" of any 3x3 magic square must be 5, and b) the "magic sum" must be 15.

Here's a way to think about the "magic sum". The sum of numbers 1-9 is 45. The three horizontal rows will include all 9 numbers (and thus sum to 45). And since there are three rows, each row will sum to 45/3 = 15.

It takes a bit of pen and paper to see that the middle must be 5 (or at least, it took me some trial and error). But once we know these two things, we can think in terms of the 4 "pairs" that can go on opposite sides of the 5:

1 and 9
2 and 8
3 and 7
4 and 6

So for example, if 4 goes Top/Left, we know that 6 must go Bottom/Right (since the "magic sum" must be 15, and 5 is in the middle)

A bit more on pen/paper will show that only two of these pairs fit in the "corners":

2 and 8
4 and 6

The other two pairs must be "wedged" inside the corner paris (e.g., top middle, bottom middle). And once we set our four corners, there is only 1 way to place the rest of the numbers.

This is enough to show that there are 8 magic matrices. There are 4 possible ways to place the 4 and 6 pair (the 4 could go in Top/Left, Top/Right, Bottom/Right, Bottom/Left). Then once we place the 4 and 6, there are two different ways we could place the 2 and 8.

To acutally generate these matrices, I started with one "seed" (which happend to be the first magic matrix I found):

[4 3 8]
[9 5 1]
[2 7 6]

From ths seed, we can rotate it clockwise 4 times (so the 4 appears in each corner). And then from each rotation, we can place the remaining digits either clockwise, or counterclockwise around the 5 (going counterclockwise is equivalent to getting the "mirror" of the matrix along a diagonal).

These two matrix manipulations are also great helper functions to have handy on other problems.

I approached this problem by first identifying all the different 3x3 magic squares.

Demonstrate that all 3x3 magic squares have a 5 in the center

Let's call the center value 'C'. Let's call the sum of all other values 'Others'.

A 3x3 magic square contains all numbers from 1 to 9. So the sum of the values of a 3x3 magic square is 45 (= 1 + 2 + ... + 8 + 9).

Therefore,

C + Others = 45 (eq. 1)

In addition, the sum of the numbers on each row, column, and diagonal has to be 15 (the magical number). Now, consider the sum of the middle row, the middle column, and the two diagonals. They add to 60 (= 4 * 15). And this sum is equivalent to adding all the numbers in the square once and four times the central number.

Therefore,

4 * C + Others = 60 (eq. 2)

From equations 1 and 2, we infer C = 5. Hence, all 3x3 magic squares have a 5 in the center.

Desmonstrate that corner values are always even numbers

Since we necessarily have a 5 in the center, it follows that each row, column, and diagonal that comprises this five will have two other numbers that add to 10. Hence we can establish candidate pairs:

• (1, 9)
• (2, 8)
• (3, 7)
• (4, 6)

Notice that two of these pairs have odd numbers and two have even numbers.

Imagine we place one of the odd pairs on a diagonal. We would then have an odd number in one of the top corners. Consider the first row (starting from the top). Since it alreay has an odd number in a corner, and the row has to sum to 15, the two other numbers both need to be odd, or both even. But we don't have enough odd pairs (we only have one left). And neither do we have enough even pairs, because if we place two of these vertically, then we have none left for the column containing the odd corner number. Hence, we reach a contradiction. This implies that our original hypothesis was incorrect. Namely, the corner numbers can't be odd, and therefore, should be even.

Since we have two even pairs, there are 4 ways to place the first pair in the corners (for example, the (2, 8) pair can be placed with the 2 in the top-left, top-right, bottom-left, bottom-right). And for each of those 4 positions, there are two ways to place the second pair. Hence, 8 in total.

Once the corner pairs have been placed, there is only one way to place the remaining numbers.

Therefore, we have demonstrated that there are 8 different 3x3 magic squares. And we know how to generate them.

For C:

int magic_mat[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_cost = 81;
for (int k = 0; k < 8; k++) {
    int crt_cost = 0;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++)
            crt_cost += abs( A[i][j] - magic_mat[k][i][j] );
    }
    if (crt_cost < min_cost)
        min_cost = crt_cost;
}

printf("%d", min_cost);

JAVA

    int cost[] = {0,0,0,0,0,0,0,0};
    int t[][] = 
    {
        {4,9,2,3,5,7,8,1,6},
        {4,3,8,9,5,1,2,7,6},
        {2,9,4,7,5,3,6,1,8},
        {2,7,6,9,5,1,4,3,8},
        {8,1,6,3,5,7,4,9,2},
        {8,3,4,1,5,9,6,7,2},
        {6,7,2,1,5,9,8,3,4},
        {6,1,8,7,5,3,2,9,4},
    };

    for(int i=0;i<8;i++)
    {        
    cost[i] = Math.abs(t[i][0]-s[0][0]) + Math.abs(t[i][1]-s[0][1]) + Math.abs(t[i][2]-s[0][2]);
    cost[i] = cost[i] + Math.abs(t[i][3]-s[1][0]) + Math.abs(t[i][4]-s[1][1]) + Math.abs(t[i][5]-s[1][2]);
    cost[i] = cost[i] + Math.abs(t[i][6]-s[2][0]) + Math.abs(t[i][7]-s[2][1]) + Math.abs(t[i][8]-s[2][2]);
    }   

    Arrays.sort(cost);
    System.out.println(cost[0]);