We define a magic square to be an n*n matrix of distinct positive integers from 1 to n^2 where the sum of any row, column, or diagonal of length n is always equal to the same number: the magic constant.
You will be given a 3*3 matrix of integers in the inclusive range [1,9]. We can convert any digit a to any other digit b in the range [1,9] at cost of [a,b]. Given s, convert it into a magic square at minimal cost. Print this cost on a new line.
Note: The resulting magic square must contain distinct integers in the inclusive range [1,9].
Example
$s = [[5, 3, 4], [1, 5, 8], [6, 4, 2]]
The matrix looks like this:
5 3 4
1 5 8
6 4 2
We can convert it to the following magic square:
8 3 4
1 5 9
6 7 2
This took three replacements at a cost of |5-8| +|8-9|+|4-7|=7.
Function Description
Complete the formingMagicSquare function in the editor below.
formingMagicSquare has the following parameter(s):
- int s[3][3]: a3*3 array of integers
Returns
- int: the minimal total cost of converting the input square to a magic square
Input Format
Each of the lines contains three space-separated integers of row s[i] .
Constraints
- s[i][j] ranges[1,9]
Sample Input 0
4 9 2
3 5 7
8 1 5
Sample Output 0
1
Explanation 0
If we change the bottom right value, s[2][2], from 5 to 6 at a cost of |6-5|=1,s becomes a magic square at the minimum possible cost.
Sample Input 1
4 8 2
4 5 7
6 1 6
Sample Output 1
4
Explanation 1
Using 0-based indexing, if we make
- s[0][1]->9 at a cost of |9-8|=1
- s[1][0]->3 at a cost of |3-4|=1
- s[2][0]-> at a cost of |8-6|=2,
then the total cost will be 1+1+2=4
Python Implementation
#!/bin/python3
import math
import os
import random
import re
import sys
#
# Complete the 'formingMagicSquare' function below.
#
# The function is expected to return an INTEGER.
# The function accepts 2D_INTEGER_ARRAY s as parameter.
#
def formingMagicSquare(s):
magic_squares = [
[[2, 9, 4], [7, 5, 3], [6, 1, 8]],
[[4, 9, 2], [3, 5, 7], [8, 1, 6]],
[[6, 1, 8], [7, 5, 3], [2, 9, 4]],
[[8, 1, 6], [3, 5, 7], [4, 9, 2]],
[[8, 3, 4], [1, 5, 9], [6, 7, 2]],
[[4, 3, 8], [9, 5, 1], [2, 7, 6]],
[[2, 7, 6], [9, 5, 1], [4, 3, 8]],
[[6, 7, 2], [1, 5, 9], [8, 3, 4]]
]
min_cost = float('inf')
for magic_square in magic_squares:
cost = 0
for i in range(3):
for j in range(3):
cost += abs(s[i][j] - magic_square[i][j])
min_cost = min(min_cost, cost)
return min_cost
# Write your code here
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
s = []
for _ in range(3):
s.append(list(map(int, input().rstrip().split())))
result = formingMagicSquare(s)
fptr.write(str(result) + '\n')
fptr.close()
C Implementation
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
int formingMagicSquare(int s[3][3]) {
// List of all possible 3x3 magic squares
int magic_squares[8][3][3] = {
{{2, 9, 4}, {7, 5, 3}, {6, 1, 8}},
{{4, 9, 2}, {3, 5, 7}, {8, 1, 6}},
{{6, 1, 8}, {7, 5, 3}, {2, 9, 4}},
{{8, 1, 6}, {3, 5, 7}, {4, 9, 2}},
{{8, 3, 4}, {1, 5, 9}, {6, 7, 2}},
{{4, 3, 8}, {9, 5, 1}, {2, 7, 6}},
{{2, 7, 6}, {9, 5, 1}, {4, 3, 8}},
{{6, 7, 2}, {1, 5, 9}, {8, 3, 4}}
};
int min_cost = INT_MAX;
for (int k = 0; k < 8; k++) {
int cost = 0;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
cost += abs(s[i][j] - magic_squares[k][i][j]);
}
}
min_cost = (cost < min_cost) ? cost : min_cost;
}
return min_cost;
}
int main() {
// Example usage:
int matrix[3][3];
// Input 3x3 matrix
printf("Enter the elements of the 3x3 matrix:\n");
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
scanf("%d", &matrix[i][j]);
}
}
int result = formingMagicSquare(matrix);
printf("Minimum cost to form a magic square: %d\n", result);
return 0;
}
