Forming a Magic Square

Sort by

recency

|

36 Discussions

|

  • + 0 comments

    Python 3:

    import itertools
    from collections.abc import Iterable
    
    
    def formingMagicSquare(s: Iterable[Iterable[int]]) -> int:
        s_flat = (*itertools.chain.from_iterable(s),)
        return min(
            sum(abs(i - j) for i, j in zip(magic_square, s_flat))
            for magic_square in (
                (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),
            )
        )
    
  • + 0 comments

    Solution in CPP, building all magic squares:

    #include <iostream>
    #include <vector>
    using namespace std;
    
    typedef vector<vector<int>> matrix;
    
    vector<matrix> magicSquares;
    matrix m;
    
    int cost(int a, int b) {
      return abs(a - b);
    }
    
    int complement(int a) {
      return 10 - a;
    }
    
    bool between(int a, int b, int c) {
      return a >= b && a <= c;
    }
    
    void generateMagicSquares() {
      for (int a = 1; a <= 9; ++a) {
        for (int c = 1; c <= 9; ++c) {
          if (a == c || a == complement(c)) continue;
    
          int d = 5 + c - a;
          int b = 15 - c - a;
    
          if (a == b || a == complement(b)) continue;
          if (a == d || a == complement(d)) continue;
          if (b == c || b == complement(c)) continue;
          if (b == d || b == complement(d)) continue;
          if (c == d || c == complement(d)) continue;
    
          if (between(d, 1, 9) && between(b, 1, 9)) {
            vector<int> line1 = {a, b, c};
            vector<int> line2 = {d, 5, complement(d)};
            vector<int> line3 = {complement(c), complement(b), complement(a)};
            matrix m = {line1, line2, line3};
            magicSquares.push_back(m);
          }
        }
      }
    }
    
    int distance(matrix& a, matrix& b) {
      int dist = 0;
    
      for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
          dist += cost(a[i][j], b[i][j]);
        }
      }
    
      return dist;
    }
    
    int main () {
      int aux, minCost = INT32_MAX;
      generateMagicSquares();
    
      for (int i = 0; i < 3; ++i) {
        m.push_back(vector<int>());
        for (int j = 0; j < 3; ++j) {
          cin >> aux;
          m[i].push_back(aux);
        }
      }
    
      for (matrix& magicSquare : magicSquares) {
        minCost = min(minCost, distance(m, magicSquare));
      }
    
      cout << minCost << endl;
      return 0;
    }
    
  • + 0 comments

    Not as bad a question as some people here make out.

    1. Generate all permutations of list [1,2,3,4,5,6,7,8,9] (the list is a flattened square 3x3 2D array)

    2. Filter for lists that are magic (the criteria are in the question)

    3. Calculate distance from input array to each magic square

    4. Return minimum distance

  • + 0 comments

    Python3 2 line:

    def formingMagicSquare(s):
        # base = (
        #     (8,3,4),
        #     (1,5,9),
        #     (6,7,2))
        # def v(m):
        #     return m[::-1]
        # def r(m):
        #     return tuple(r[::-1] for r in zip(*m))
        # M = [base]
        # for _ in range(3):
        #     M.append(r(M[-1]))
        # M.append(v(base))
        # for _ in range(3):
        #     M.append(r(M[-1]))
        # for m in M:
        #     print(m)
        
        M = (
            ((8, 3, 4), (1, 5, 9), (6, 7, 2)),
            ((6, 1, 8), (7, 5, 3), (2, 9, 4)),
            ((2, 7, 6), (9, 5, 1), (4, 3, 8)),
            ((4, 9, 2), (3, 5, 7), (8, 1, 6)),
            ((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)),
            ((2, 9, 4), (7, 5, 3), (6, 1, 8))
        )
        
        return min(sum(abs(m[i][j] - s[i][j]) for i in range(3) for j in range(3)) for m in M)
    
  • + 0 comments

    Java, O(1)

    int[][][] magicSquares = {
                {{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 minCost = Integer.MAX_VALUE;
            for (int[][] magicSquare : magicSquares) {
                int cost = 0;
                for (int i = 0; i < 3; i++) {
                    for (int j = 0; j < 3; j++) {
                        cost += Math.abs(s.get(i).get(j) - magicSquare[i][j]);
                    }
                }
                minCost = Math.min(minCost, cost);
            }
            
            return minCost;
        }