HackerRank Forming a Magic Square Solution

In this post, We are going to solve HackerRank Forming a Magic Square Problem. We define a magic square to be an n x m matrix of distinct positive integers from 1 to n square 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 matrix 3×3 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 this s, 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 [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}.

Function Description

Complete the formingMagicSquare function in the editor below.

formingMagicSquare has the following parameter(s):

int s[3][3]: a 3×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].

Sample Input 0

4 9 2
3 5 7
8 1 5

Sample Output 0

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.

Table of Contents

Forming a Magic Square C Solution

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int main() {

    /* Enter your code here. Read input from STDIN. Print output to STDOUT */ 
    int matrix[3][3];
    int magicArray1[8] = {4,9,2,7,6,1,8,3};
    int magicArray2[8] = {2,9,4,3,8,1,6,7};
    int indexes[8] = {0,1,2,12,22,21,20,10};
    int i, j, shift = 0;
    int costResult = 100, costTmp = 0;
    int found = 0;
    
    for (i = 0; i < 3; i++) {
        for (j = 0; j < 3; j++) {
            scanf("%d", &matrix[i][j]);
        }
        scanf("\n");
    }
    
    for (shift = 0; shift < 8 && !found; shift += 2){
        costTmp = 0;
        for (i = 0, j = shift; i < 8 ; i++) {
            costTmp += abs(matrix[indexes[i]/10][indexes[i]%10] - magicArray1[j]);
            j = (j + 1) % 8;
        } 
        if (costTmp == 0){
            found = 1;
            costResult = 0;
        } else if (costTmp < costResult) {
            costResult = costTmp;
        }
    }

    for (shift = 0; shift < 8 && !found; shift += 2){
        costTmp = 0;
        for (i = 0, j = shift; i < 8 ; i++) {
            costTmp += abs(matrix[indexes[i]/10][indexes[i]%10] - magicArray2[j]);
            j = (j + 1) % 8;
        } 
        if (costTmp == 0){
            found = 1;
            costResult = 0;
        } else if (costTmp < costResult) {
            costResult = costTmp;
        }
    }

    costResult += abs(matrix[1][1] - 5);
    
    printf("%d", costResult);
    
    return 0;
}

Forming a Magic Square C++ Solution

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

const int magic_squares_3x3[8][9] = {
    {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}
};
int matrix[9];

int main() {
    
    for (int i = 0; i < 9; i++) scanf("%d", &matrix[i]);
    int min_cost = 100;
    for (int i = 0; i < 8; i++) {
        int cost = 0;
        for (int j = 0; j < 9; j++) cost += abs(matrix[j] - magic_squares_3x3[i][j]);
        if (cost < min_cost) min_cost = cost;
    }
    printf("%d\n", min_cost);
    return 0;
}

Forming a Magic Square C Sharp Solution

public static void FormMagicSquare(int n)
{
    int[,] magicSquare = new int[n, n];
    int row = n / 2;
    int col = n - 1;
 
    for (int num = 1; num <= n * n; )
    {
        if (row == -1 && col == n)
        {
            col = n - 2;
            row = 0;
        }
        else
        {
            if (col == n)
                col = 0;
            if (row < 0)
                row = n - 1;
        }
 
        if (magicSquare[row, col] != 0)
        {
            col -= 2;
            row++;
            continue;
        }
        else
            magicSquare[row, col] = num++;
 
        col++;
        row--;
    }
 
    Console.WriteLine("The Magic Square for {0}x{0}:", n);
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            Console.Write("{0} ", magicSquare[i, j]);
        }
        Console.WriteLine();
    }
}

Forming a Magic Square Java Solution

import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner scan = new Scanner(System.in);
        int[] square = new int[9];
        for (int i = 0; i < 9; i++) {
            square[i] = scan.nextInt();
        }
        int[][] matrix={{4,9,2,3,5,7,8,1,6},
                        {2,7,6,9,5,1,4,3,8},
                        {6,1,8,7,5,3,2,9,4},
                        {8,3,4,1,5,9,6,7,2},
                        {2,9,4,7,5,3,6,1,8},
                        {6,7,2,1,5,9,8,3,4},
                        {8,1,6,3,5,7,4,9,2},
                        {4,3,8,9,5,1,2,7,6}};
        
        int minOff = 99;
        for (int i = 0; i < 8; i++) {
            int off = 0;
            for (int j = 0; j < 9; j++) {
                if (square[j] != matrix[i][j]) {
                    off += Math.abs(square[j] - matrix[i][j]);
                }
            }
            if (off < minOff) minOff = off;
        }
        
        System.out.println(minOff);
    }
}

Forming a Magic Square JavaScript Solution

process.stdin.resume();
process.stdin.setEncoding('ascii');

var input_stdin = "";
var input_stdin_array = "";
var input_currentline = 0;

process.stdin.on('data', function (data) {
    input_stdin += data;
});

process.stdin.on('end', function () {
    input_stdin_array = input_stdin.split("\n");
    main();    
});

function readLine() {
    return input_stdin_array[input_currentline++];
}

/////////////// ignore above this line ////////////////////

function main() {
    var square = new Array();
    for(var i = 0; i < 3; i++){
        square.push(readLine().split(' ').map(Number));
    }
    var perm = [[[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]]];
    var min = 10000;
    for(var i = 0; i < 8; i++) {
        var sum = 0;
        for(var x = 0; x < 3; x++) {
            for(var y = 0; y < 3; y++) {
                sum+=Math.abs(perm[i][x][y]-square[x][y]);
            }
        }
        if (sum < min) {
            min = sum;
        }
    }
    console.log(min);
}

Forming a Magic Square Python Solution

s = []
for i in range(3):
    s.append([int(i) for i in input().split()])
orig = [[4, 9, 2], [3, 5, 7], [8, 1, 6]]
all_squares = [orig]
all_squares.append(orig[::-1])
all_squares.append([i[::-1] for i in orig])
all_squares.append(all_squares[2][::-1])
all_squares.append([[4, 3, 8], [9, 5, 1], [2, 7, 6]])
all_squares.append(all_squares[4][::-1])
all_squares.append([i[::-1] for i in all_squares[4]])
all_squares.append(all_squares[6][::-1])

#for i in all_squares:
#    for j in i:
#        print(j)
#    print("\n")

least = 99
for i in all_squares:
    temp = 0
    for j in range(3):
        for k in range(3):
            temp += abs(s[j][k]-i[j][k])
    if temp < least:
        least = temp

print(least)

Other Solution