Forming a Magic Square HackerRank Solution – Coder In Me

We define a magic square to be a 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|. For this Problem Forming a Magic Square 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].

For example, we start with the following matrix s:

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.

Input Format

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

Constraints

 s[i][j]  belongs to [1,9]

Output Format

Print an integer denoting the minimum cost of turning the matrix  into a magic square.

Sample Input 0

4 9 2
3 5 7
8 1 5

Sample Output 0

1
 Forming a Magic Square

HOW TO THINK:

In a 3*3 square matrix there are 8 magic squares. In this positions of certain elements are fixed like 5appears at (2,2) position odd numbers occur at the middle and the even numbers at the edges. Thus we get overall 8 magic squares in a 3*3 square matrix.

So knowing these 8 matrixes solves most of our problem.

HOW TO CODE Forming a Magic Square :

We are given a 3*3 array with positive numbers from 1 to 9.

What we need to do is to calculate the cost of converting the given array s into a magic square. Thus for doing so we compare this array one by one with all the magic squares and calculate the cost needed to turn the array s into a magic square, and store this into an array of size 8.

After doing so we calculate the minimum of the array elements thus this gives us the minimum cost to convert the given array into a magic square.

Solution of Forming a Magic Square

#include <bits/stdc++.h>
#include<cmath>

using namespace std;

int formingMagicSquare(vector < vector<int> > s) {
    int d[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 c[8],min1;
	for(int k=0;k<8;k++)
	{
		c[k] = 0;
      for(int i=0;i<3;i++)
	  {
	    for(int j=0;j<3;j++)
	    {
	    	if(s[i][j]!=d[k][i][j])
	    	{
	    		c[k]+=abs(s[i][j]-d[k][i][j]);

	    	}
 	    }
	  }
	 


	}
	min1 = c[0];
	for(int i=1;i<8;i++){
		if(c[i]<min1)
	  	{
	  		min1=c[i];
		}
	}

    return min1;
}

int main() {
    vector< vector<int> > s(3,vector<int>(3));
    for(int s_i = 0;s_i < 3;s_i++){
       for(int s_j = 0;s_j < 3;s_j++){
          cin >> s[s_i][s_j];
       }
    }
    int result = formingMagicSquare(s);
    cout << result << endl;
    return 0;
}
arr = map(int, raw_input().split())
arr.extend(map(int, raw_input().split()))
arr.extend(map(int, raw_input().split()))
magic = [[8, 1, 6, 3, 5, 7, 4, 9, 2], [6, 1, 8, 7, 5, 3, 2, 9, 4],
         [4, 3, 8, 9, 5, 1, 2, 7, 6], [2, 7, 6, 9, 5, 1, 4, 3, 8],
         [2, 9, 4, 7, 5, 3, 6, 1, 8], [4, 9, 2, 3, 5, 7, 8, 1, 6],
         [6, 7, 2, 1, 5, 9, 8, 3, 4], [8, 3, 4, 1, 5, 9, 6, 7, 2]]
mini = 2**64
for brr in magic:
    diff = 0
    for i, j in zip(arr, brr):
        diff += abs(i - j)
    mini = min(diff, mini)
print mini
#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;
}

For more Hackerrank problem solution click here

All rights reserved. No part of this Post may be copied, distributed, or transmitted in any form or by any means, without the prior written permission of the website admin, except in the case of brief quotations embodied in critical reviews and certain other noncommercial uses permitted by copyright law. For permission requests, write to the owner, addressed “Attention: Permissions Coordinator,” to the admin @coderinme

A web developer(Front end and Back end), and DBA at csdamu.com. Currently working as Salesforce Developer @ Tech Matrix IT Consulting Private Limited. Check me @about.me/s.saifi

Leave a reply:

Your email address will not be published.