Forming a Magic Square | HackerRank Solution

Hello coders, today we are going to solve Forming a Magic Square HackerRank Solution which is a Part of HackerRank Algorithms Series.

Task

We define a magic square to be an n x n matrix of distinct positive integers from 1 to n² 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 x 3 matrix s 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]: a 3 x 3 array of integers

Returns

• int: the minimal total cost of converting the input square to a magic square

Input Format

Each of the 3 lines contains three space-separated integers of row s[i].

Constraints

• s|i||j| belongs to [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]->8 at a cost of |8 – 6| = 2,

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

Solution – Forming a Magic Square

C++

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
    int arr[9] =    {4,9,2,3,5,7,8,1,6} ;
    int arr1[9] =   {2,7,6,9,5,1,4,3,8} ;
    int arr2[9] =   {6,1,8,7,5,3,2,9,4};
    int arr3[9] =   {2,9,4,7,5,3,6,1,8};
    int arr4[9] =   {6,7,2,1,5,9,8,3,4};
    int arr5[9] =   {8,1,6,3,5,7,4,9,2};
    int arr6[9] =   {8,3,4,1,5,9,6,7,2};
    int arr7[9] =   {4,3,8,9,5,1,2,7,6};
    int ans[8] = {0};
    for(int i =0;i<9;i++)
    {
        int k;cin>>k;
        ans[0] += abs(k - arr[i]);
        ans[1] += abs(k - arr1[i]);
        ans[2] += abs(k - arr2[i]);
        ans[3] += abs(k - arr3[i]);
        ans[4] += abs(k - arr4[i]);
        ans[5] += abs(k - arr5[i]);
        ans[7] += abs(k - arr7[i]);
        ans[6] += abs(k - arr6[i]);
        
    }
    int min =ans[0];
    for(int i=0;i<8;i++)
        if(ans[i]<min)
            min = ans[i];
    cout<<min<<endl;
        return 0;
}

Python

import itertools
s = []
for i in range(3):
    s.extend(list(map(int, input().split(" "))))

min_cost = 1000
best = None
def is_magic(s):
    for i in range(3):
        if sum(s[i*3:i*3+3]) != 15:
            return False
        if sum(s[i::3]) != 15:
            return False
    if s[0] + s[4] + s[8] != 15:
        return False
    if s[2] + s[4] + s[6] != 15:
        return False
    return True

best = None
for p in itertools.permutations(range(1,10)):
    cost = sum([abs(p[i] - s[i]) for i in range(len(s))])
    if cost < min_cost and is_magic(p):
        min_cost = cost
        best = p
        
print(min_cost)

Java

import java.io.*;
import java.util.*;
public class crap {
    public static int diff(int[][] s1,int[][] s2){
        int d=0;
        for(int i=0;i<3;i++)
            for(int j=0;j<3;j++)
                d+=Math.abs(s1[i][j]-s2[i][j]);
        return d;
    }
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int s[][]=new int[3][3];
        for(int i=0;i<3;i++)
           for(int j=0;j<3;j++)
           {s[i][j]=sc.nextInt();}
        int a[][]={{2,7,6},{9,5,1},{4,3,8}};
        int b[][]={{2,9,4},{7,5,3},{6,1,8}};
        int c[][]={{4,3,8},{9,5,1},{2,7,6}};
        int d[][]={{4,9,2},{3,5,7},{8,1,6}};
        int e[][]={{6,1,8},{7,5,3},{2,9,4}};
        int f[][]={{6,7,2},{1,5,9},{8,3,4}};
        int g[][]={{8,1,6},{3,5,7},{4,9,2}};
        int h[][]={{8,3,4},{1,5,9},{6,7,2}};
        ArrayList<int[][]> val=new ArrayList<>();
        int res=Integer.MAX_VALUE;
        val.add(a);val.add(b);val.add(c);val.add(d);val.add(e);val.add(f);val.add(g);val.add(h);
        for(int[][] x:val){
            res=Math.min(res, diff(x, s));
        }
        System.out.println(res);
    }
}

Disclaimer: The above Problem (Forming a Magic Square) is generated by Hacker Rank but the Solution is Provided by CodingBroz. This tutorial is only for Educational and Learning Purpose.