Hello Programmers, In this post, you will know how to solve the HackerRank Forming a Magic Square Solution. This problem is a part of the HackerRank Algorithms Series.

HackerRank Forming a Magic Square Solution
HackerRank Forming a Magic Square Solution

One more thing to add, don’t directly look for the solutions, first try to solve the problems of Hackerrank by yourself. If you find any difficulty after trying several times, then you can look for solutions.

HackerRank Forming a Magic Square Solution

Task

We define a magic square to be an n matrix of distinct positive integers from 1 to n2 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.

HackerRank Forming a Magic Square Solution

Forming a Magic Square Solution in C

#include<stdio.h>
int main()
{
    int inp[3][3],arr1[3][3]={2,9,4,7,5,3,6,1,8},arr2[3][3]={6,1,8,7,5,3,2,9,4},arr3[3][3]={2,7,6,9,5,1,4,3,8},arr4[3][3]={4,3,8,9,5,1,2,7,6},arr5[3][3]={8,1,6,3,5,7,4,9,2},arr6[3][3]={4,9,2,3,5,7,8,1,6}
    ,arr7[3][3]={8,3,4,1,5,9,6,7,2},arr8[3][3]={6,7,2,1,5,9,8,3,4},i,j,cost,min=10000;
    for(i=0;i<3;i++)
        for(j=0;j<3;j++)
        scanf("%d",&inp[i][j]);
    cost=0;
    for(i=0;i<3;i++)
    {
        for(j=0;j<3;j++)
        {
            cost+=abs(arr1[i][j]-inp[i][j]);
        }
    }
    if(cost<min)
        min=cost;
    cost=0;
    for(i=0;i<3;i++)
    {
        for(j=0;j<3;j++)
        {
            cost+=abs(arr2[i][j]-inp[i][j]);
        }
    }
    if(cost<min)
        min=cost;
    cost=0;
    for(i=0;i<3;i++)
    {
        for(j=0;j<3;j++)
        {
            cost+=abs(arr3[i][j]-inp[i][j]);
        }
    }
    if(cost<min)
        min=cost;
    cost=0;
    for(i=0;i<3;i++)
    {
        for(j=0;j<3;j++)
        {
            cost+=abs(arr4[i][j]-inp[i][j]);
        }
    }
    if(cost<min)
        min=cost;
    cost=0;
    for(i=0;i<3;i++)
    {
        for(j=0;j<3;j++)
        {
            cost+=abs(arr5[i][j]-inp[i][j]);
        }
    }
    if(cost<min)
        min=cost;
    cost=0;
    for(i=0;i<3;i++)
    {
        for(j=0;j<3;j++)
        {
            cost+=abs(arr6[i][j]-inp[i][j]);
        }
    }
    if(cost<min)
        min=cost;
    cost=0;
    for(i=0;i<3;i++)
    {
        for(j=0;j<3;j++)
        {
            cost+=abs(arr7[i][j]-inp[i][j]);
        }
    }
    if(cost<min)
        min=cost;
    cost=0;
    for(i=0;i<3;i++)
    {
        for(j=0;j<3;j++)
        {
            cost+=abs(arr8[i][j]-inp[i][j]);
        }
    }
    if(cost<min)
        min=cost;
    cost=0;
    printf("%d\n",min);
    return 0;
}

Forming a Magic Square Solution in Cpp

#include <iostream>
using namespace std;
int main() {
	
	int m1[3][3], m2[3][3], best = 2000000000;
	
	for( int i=0; i<3; i++ )
		for(int j=0; j<3; j++ )
				cin >> m1[i][j];
				
	for( int a=1; a<=9; a++ )
	for( int b=1; b<=9; b++ ) {
		if( b==a) continue;
	for( int c=1; c<=9; c++ ) {
		if( c==a || c==b ) continue;
	for( int d=1; d<=9; d++ ) {
		if( d==a || d==b || d==c ) continue;
	for( int e=1; e<=9; e++ ) {
		if( e==a || e==b || e==c || e==d ) continue;
	for( int f=1; f<=9; f++ ) {
		if( f==a || f==b || f==c || f==d || f==e ) continue;
	for( int g=1; g<=9; g++ ) {
		if( g==a || g==b || g==c || g==d || g==e || g==f ) continue;
	for( int h=1; h<=9; h++ ) {
		if( h==a || h==b || h==c || h==d || h==e || h==f || h==g ) continue;
	for( int i=1; i<=9; i++ ) {
		if( i==a || i==b || i==c || i==d || i==e || i==f || i==g || i==h ) continue;
		
		m2[0][0] = a;
		m2[0][1] = b;
		m2[0][2] = c,
		m2[1][0] = d;
		m2[1][1] = e;
		m2[1][2] = f;
		m2[2][0] = g;
		m2[2][1] = h;
		m2[2][2] = i;
		
		if( a + b + c  == d + e + f && d + e + f == g + h + i && 
			a + d + g == b + e + h && b + e + h == c + f + i &&
			a + b + c  == a + e + i && a + b + c == c + e + g ) {
				int cost = 0;
				for( int r=0; r<3; r++ )
					for( int s=0; s<3; s++ )
						cost += abs( m1[r][s] - m2[r][s] );
			best = min( best, cost );			
			}
	}}}}}}}}
	
	cout << best;
	return 0;
}

Forming a Magic Square Solution in Java

import java.io.*;
import java.util.*;
import java.lang.*;
import java.awt.*;
import java.awt.geom.*;
import java.math.*;
import java.text.*;
class ProblemC{
	BufferedReader in;
	StringTokenizer st;
	
	public static void main (String [] args){
		new ProblemC();
	}
	
	public int minCost (int [] []arr1, int [] [] arr2){
		int cost = 0;
		for(int x = 0; x < 3; x++){
			for(int y = 0; y < 3; y++){
				cost += Math.abs(arr1[x][y] - arr2[x][y]);
			}	
		}	
		return cost;
	}
	
	public ProblemC(){
		try{
			in = new BufferedReader(new InputStreamReader(System.in));
			int [] [] arr = new int[3][3];
			for(int y = 0; y < 3; y++)
				for(int x = 0; x < 3; x++)
					arr[x][y] = nextInt();
					
			int[][] arr1 = new int[][]{
				{ 8, 1, 6,},
				{ 3, 5, 7, },
				{ 4, 9, 2,},
			};	
			
			int[][] arr2 = new int[][]{
				{ 6, 1, 8,},
				{ 7, 5, 3, },
				{ 2, 9, 4,},
			};	
			
			int[][] arr3 = new int[][]{
				{ 4, 9, 2,},
				{ 3, 5, 7, },
				{ 8, 1, 6,},
			};	
			
			int[][] arr4 = new int[][]{
				{ 2, 9, 4,},
				{ 7, 5, 3, },
				{ 6, 1, 8,},
			};	
			
			int[][] arr6 = new int[][]{
				{ 8, 3, 4,},
				{ 1, 5, 9, },
				{ 6, 7, 2,},
			};	
			
			int[][] arr7 = new int[][]{
				{ 4, 3, 8,},
				{ 9, 5, 1, },
				{ 2, 7, 6,},
			};	
			
			int[][] arr8 = new int[][]{
				{ 6, 7, 2,},
				{ 1, 5, 9, },
				{ 8, 3, 4,},
			};	
			
			int[][] arr9 = new int[][]{
				{ 2, 7, 6,},
				{ 9, 5, 1, },
				{ 4, 3, 8,},
			};	
			int ans = Integer.MAX_VALUE;
			ans = Math.min(ans, minCost(arr, arr1));
			ans = Math.min(ans, minCost(arr, arr2));
			ans = Math.min(ans, minCost(arr, arr3));
			ans = Math.min(ans, minCost(arr, arr4));
			//ans = Math.min(ans, minCost(arr, arr5));
			ans = Math.min(ans, minCost(arr, arr6));
			ans = Math.min(ans, minCost(arr, arr7));
			ans = Math.min(ans, minCost(arr, arr8));
			ans = Math.min(ans, minCost(arr, arr9));
			System.out.println(ans);
		}
		catch(IOException e){
			System.out.println("IO: General");
		}
	}
	
	String next() throws IOException {
		while (st == null || !st.hasMoreTokens())
	   	 	st = new StringTokenizer(in.readLine().trim());
		return st.nextToken();
	}
	long nextLong() throws IOException {
		return Long.parseLong(next());
	}
	int nextInt() throws IOException {
		return Integer.parseInt(next());
	}
	double nextDouble() throws IOException {
		return Double.parseDouble(next());
	}
	String nextLine() throws IOException {
		return in.readLine().trim();
	}
}

Forming a Magic Square Solution in Python

import itertools
n1,n2,n3 = map(int, raw_input().strip().split(' '))
n4,n5,n6 = map(int, raw_input().strip().split(' '))
n7,n8,n9 = map(int, raw_input().strip().split(' '))
l = [n1,n2,n3,n4,n5,n6,n7,n8,n9]
tests = [[0,1,2], [3,4,5], [6,7,8], [0,3,6], [1,4,7], [2,5,8], [0,4,8], [2,4,6]]
def im(l):
    sums = [l[i[0]] + l[i[1]] + l[i[2]] for i in tests]
    return len(set(sums)) == 1
squares = [(2, 7, 6, 9, 5, 1, 4, 3, 8),
(2, 9, 4, 7, 5, 3, 6, 1, 8),
(4, 3, 8, 9, 5, 1, 2, 7, 6),
(4, 9, 2, 3, 5, 7, 8, 1, 6),
(6, 1, 8, 7, 5, 3, 2, 9, 4),
(6, 7, 2, 1, 5, 9, 8, 3, 4),
(8, 1, 6, 3, 5, 7, 4, 9, 2),
(8, 3, 4, 1, 5, 9, 6, 7, 2)]
r = []
for i in squares:
    if im(i):
        cost = sum([abs(l[j] - i[j]) for j in range(9)])
        r.append(cost)
print min(r)

Forming a Magic Square Solution using JavaScript

function processData(input) {
  // Make our 2D array...
  var myArr = input.split('\n').map(n => n.split(' ').map(Number));
  // Flatten array for ease of access
  myArr = [].concat.apply([], myArr);
  // We know a 3x3 magic square has all sums === 15
  // We also know that there are 8 unique solutions to a 3x3 magic square
  var squares = [
    [8, 1, 6, 3, 5, 7, 4, 9, 2],
    [4, 3, 8, 9, 5, 1, 2, 7, 6],
    [2, 9, 4, 7, 5, 3, 6, 1, 8],
    [6, 7, 2, 1, 5, 9, 8, 3, 4],
    [6, 1, 8, 7, 5, 3, 2, 9, 4],
    [8, 3, 4, 1, 5, 9, 6, 7, 2],
    [4, 9, 2, 3, 5, 7, 8, 1, 6],
    [2, 7, 6, 9, 5, 1, 4, 3, 8]
  ];
  // Now we just track which given magic square is the least distance from our matrix
  // This will report the least cost (abet, brute force-y)
  var cost = Math.min();
  for (let magicSquareEntry = 0; magicSquareEntry < squares.length; magicSquareEntry += 1) {
    let currCost = 0;
    for (i = 0; i < 9; i += 1) {
      currCost += Math.abs(squares[magicSquareEntry][i] - myArr[i]);
    }
    if (currCost < cost) {
      cost = currCost;
    }
  }
  console.log(cost);
} 
process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});
process.stdin.on("end", function () {
   processData(_input);
});

Forming a Magic Square Solution in Scala

object Solution {
    
    val theMagicSquare = Array(Array(2,7,6),Array(9,5,1),Array(4,3,8))
    val theMagicSquares = Array(theMagicSquare, theMagicSquare.reverse, theMagicSquare.map(_.reverse), theMagicSquare.map(_.reverse).reverse, theMagicSquare.transpose, theMagicSquare.transpose.reverse, theMagicSquare.transpose.map(_.reverse), theMagicSquare.transpose.map(_.reverse).reverse)
    def main(args: Array[String]): Unit = {
//        println(theMagicSquares.map(_.map(_.mkString).mkString(sep = "\n")).mkString(sep = "\n\n"))
        val input = Array.fill(3)(readLine().split(" ").map(_.toInt))
        println(theMagicSquares.map(compSquares(input)).min)
    }
    
    def compSquares(s1: Array[Array[Int]])(s2: Array[Array[Int]]): Int = {
        s1.zip(s2).map({ case (r1,r2) => r1.zip(r2).map({ case (e1,e2) => (e1-e2).abs }).sum }).sum
    }
}

Forming a Magic Square Solution in Pascal

Disclaimer: This problem (Forming a Magic Square) is generated by HackerRank but the Solution is Provided by BrokenProgrammers. This tutorial is only for Educational and Learning purposes.

Next: HackerRank Climbing the Leaderboard Solution

Leave a Reply

Your email address will not be published. Required fields are marked *