Minimum cost to convert 3 X 3 matrix into magic square

 We define a magic square to be a matrix of distinct positive integers from  to  where the sum of any row, column, or diagonal of length  is always equal to the same number: the magic constant

• You will be given a matrix 3X3 of integers in the inclusive range  [1,9]. We can convert any digit to any other digit in the range [1,9] at cost of  |a-b|. 
• Given, convert it into a magic square at a minimal cost. Print this cost on a new line.

Note: The resulting magic square must contain distinct integers in the inclusive range

Input : mat[][] = { { 4, 9, 2 },
                    { 3, 5, 7 },
                    { 8, 1, 5 }};
Output : 1
Given matrix s is not a magic square. To convert
it into magic square we change the bottom right 
value, s[2][2], from 5 to 6 at a cost of | 5 - 6 |
= 1.

Input : mat[][] = { { 4, 8, 2 },
                    { 4, 5, 7 },
                    { 6, 1, 6 }};
Output : 4

Using 0-based indexing, if we make

• -> at a cost of 
• -> at a cost of 
• -> at a cost of  |8-6|=2

then the total cost will be 1+1+2=4.

here is an easier way to see that 15 is the only sum: notice that in a completed magic square with the numbers 1 to 9, the sum of all the numbers is 1 + 2 + ... + 9 = 45, and this sum is split evenly into the 3 rows/columns, so each row and column must have sum 15.

#include <bits/stdc++.h>

using namespace std;

// Complete the formingMagicSquare function below.

bool is_magic(vector<int> v){

int sum=0,a[3][3];

// Convert vector into 3 X 3 matrix

for(int i=0;i<3;i++){

for(int j=0;j<3;j++){

a[i][j]=v[3*i+j];

}

}

int sum1,sum2;

 // Checking if each row sum is same && each columan sum is same

for(int i=0;i<3;i++){

sum1=0,sum2=0;

for(int j=0;j<3;j++){

sum1+=a[i][j];

sum2+=a[j][i];

}

if((sum1!=15) ||(sum2!=15)){

return 0;

}

}

sum1=0,sum2=0;

  // Checking if each diagonal sum is same

for(int i=0;i<3;i++){

sum1+=a[i][i];

sum2+=a[2-i][i];

}

if((sum1!=15)||(sum2!=15))

return 0;

return 1;

}

// Generating all magic square

void find_magic(vector<vector<int>> &k){

    // Initialing the vector

vector<int> v(9);

for(int i=0;i<9;i++)

v[i]=i+1;

    // Producing all permutation of vector

    // and checking if it denote the magic square or not.

do{

if(is_magic(v)){

k.push_back(v);

}

}while(next_permutation(v.begin(),v.end()));

}

/ Return sum of difference between each element of two vector

int diff(vector<int> a,vector<int> b){

int s=0;

for(int i=0;i<a.size();i++){

s+=abs(a[i]-b[i]);

}

return s;

}

// Wrapper function

int formingMagicSquare(vector<vector<int>> s) {

int res=INT_MAX;

vector<int> v;

for(int i=0;i<3;i++){

for(int j=0;j<3;j++){

v.push_back(s[i][j]);

}

}

vector<vector<int>> k;

 // generating all magic square

find_magic(k);

  // Finding the difference with each magic square

        // and assigning the minimum value.

for(int i=0;i<k.size();i++){

res=min(res,diff(v,k[i]));

}

return res;

}

int main()

{

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];

}

}

int result = formingMagicSquare(s);

fout << result << "\n";

fout.close();

return 0;

}