Magic Square

I attempted the Forming a Magic Square problem from HackerRank. After doing some reading regarding magic squares here and there decided to try different approaches. Very educational and I had fun with it.

The problem at hand is with 3 x 3 matrices. You are given a matrix and are supposed to determine the minimum cost to convert it to a magic square. The cost function is the absolute value of the difference between each changed cell in the original and the magic square matrix.

There are only 8 magic squares of 3 x 3 entries. An approach would be to compare the given matrix with each of the eight magic squares and determine the minimum cost. Of course you would have to store the eight matrices which require some additional space O(n**2). The other approach is to compute each magic square when needed. This is where I left it for this problem.

Following are edited (added the word “cost:” and the magic square generated from the provided matric) screen console outputs generated by my solution:

5 3 4
1 5 8
6 4 2

8 3 4
1 5 9
6 7 2

cost: 7

4 9 2
3 5 7
8 1 5

4 9 2
3 5 7
8 1 6

cost: 1

4 8 2
4 5 7
6 1 6

4 9 2 
3 5 7 
8 1 6 

cost: 4

1 2 3
4 5 6
7 8 9

8 3 4 
1 5 9 
6 7 2 

cost: 24

7 2 9
6 6 2
5 1 2

6 1 8 
7 5 3 
2 9 4 

cost: 19

4 4 7
3 1 5
1 7 9

6 1 8 
7 5 3 
2 9 4 

cost: 20

2 7 6
9 1 5
4 3 8

2 7 6 
9 5 1 
4 3 8 

cost: 8

2 7 5
9 1 5
4 3 5

2 7 6 
9 5 1 
4 3 8 

cost: 12

The goal is to develop the body for the formingMagicSquare() function. My Java code follows:

    // Complete the formingMagicSquare function below.
    static int formingMagicSquare(int[][] s) {

    	// **** save original matrix ****
    	int[][] ss = new int[3][3];
    	for (int r = 0; r < 3; r++) {
    		for (int c = 0; c < 3; c++) {
    			ss[r] = s[r];
    		}
    	}

    	// **** loop selecting the minimum cost ****
    	int minCost = Integer.MAX_VALUE;
    	for (int pass = 0; pass < 8; pass++) {
    		
    		// **** restore original matrix ****
        	for (int r = 0; r < 3; r++) {
        		for (int c = 0; c < 3; c++) {
        			s[r] = ss[r];
        		}
        	}

        	// **** get a magic square ****
        	int[][] ms = rotationOrReflection(pass);
      
//        	// **** display this magic square ****
//        	displayMatrix("ms", ms);

        	// **** compute cost for this pass ****
	    	int cost	= 0;
	    	for (int row = 0; row < 3; row++) {
	    		for (int col = 0; col < 3; col++) {
	    			if (ms[row][col] != s[row][col]) {
	    				cost += Math.abs(s[row][col] - ms[row][col]);
	    			}
	    		}
	    	}
	    	    	
//	    	// **** display resulting matrix ****
//	    	displayMatrix("s", s);
//	    	
//	    	// **** display cost ****
//	    	System.out.println("cost: " + cost);

	    	// **** update minimum cost ****
	    	minCost = Math.min(minCost, cost);
    	}

    	// **** return minimum cost ****
    	return minCost;
    }

For starters we save the matrix to be restored on each of the eight loops.  For each loop, we restore the original matrix and compute one of eight magic squares. We then compute the cost to change the original matrix to become the current magic square.  Finally we update the minimum cost.

If you are interested, I have placed my entire solution in my GitHub repository.

Keep on learning, experimenting, developing new software and having fun.

If you have a question regarding this or any other post in this blog, or if you need help in any aspect of the software life cycle for a product or service you are planning or is already in development, please leave me a note bellow. Notes do not show up until I approve them.

John

Follow me on Twitter:  @john_canessa