We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Implementation
  4. Forming a Magic Square
  5. Discussions

Forming a Magic Square

  • onyalioscar
     + 0 comments

    Solution without hardcoding any of the possible 3x3 magic sqaures. Magic squares are generated for odd sized matrices using the Siamese method by placing "1" in any of the positions matrix(0,1), matrix(1,0), matrix (1,2) or matrix(2,1) and then rotating at 90 or 180 or 270 deg or reflecting.

        /*
     * Complete the 'formingMagicSquare' function below.
     *
     * The function is expected to return an INTEGER.
     * The function accepts 2D_INTEGER_ARRAY s as parameter.
     */

    public static int formingMagicSquare(List<List<Integer>> s) {
        Moves[] moveList = new Moves[]{
            new Moves(0,1,1,1,true),
            new Moves(0,1,1,-1,true),
            new Moves(2,1,-1,1,true),
            new Moves(2,1,-1,-1,true),
            new Moves(1,0,-1,-1,false),
            new Moves(1,0,1,-1,false),
            new Moves(1,2,-1,1,false),
            new Moves(1,2,1,1,false),
        };
        
        Integer minCost = null;
        for(Moves move: moveList) {
            int[][] magicSquare = new int[3][3];
            magicSquare[move.startX][move.startY] = 1;
            int posX = move.startX;
            int posY = move.startY;
            int cost = Math.abs(s.get(posX).get(posY) - 1);

            for (int i = 2; i < 10; i++) {
                int newX = posX - move.vert;
                if (newX < 0) newX = 2;
                if (newX > 2) newX = 0;

                int newY = posY + move.hz;
                if (newY > 2) newY = 0;
                if (newY < 0) newY = 2;

                if (magicSquare[newX][newY] != 0) {
                    if (move.isVertFirst) {
                        newX = posX  + move.vert;
                        newY = posY;
                    }
                    else {
                        newY = posY + (-move.hz);
                        newX = posX;
                    }
                }


                magicSquare[newX][newY] = i;
                cost += Math.abs(s.get(newX).get(newY) - i);
								if (minCost != null && cost > minCost) break;
                posX = newX;
                posY = newY;

            }

            if (minCost == null || minCost > cost) minCost = cost;
        }
        
        return minCost;
    }
}

class Moves {
    int startX;
    int startY;
    int vert;
    int hz;

    boolean isVertFirst;

    public Moves(int startX, int startY, int vert, int hz, boolean isVertFirst) {
        this.startX = startX; this.startY = startY; this.vert = vert; this.hz = hz; this.isVertFirst = isVertFirst;
    }
}