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. Forming a Magic Square
  2. Discussions

Forming a Magic Square

  • victor_reial
     + 0 comments

    This is a way better problem than misery nim. Yes, you can know before hand all magic squares (as you can you know the xor solutions), but, here, you can even deduce all the magic squares or build them all during the interview, which is probably what is expected. However, building them somewhat efficiently instead of creating all 9! and then filtering

    Python best solution

    If you’re looking for solutions to the 3-month preparation kit in either Python or Rust, you can find them below: my solutions 

    def magic_squares(s):
    # Time complexity: O(1)
    # Space complexity (ignoring input): O(1)
    # Hard coded or not, both are O(1), since it's maximum of 9! to create all possible
    # squares, which is a costant (and that is the inefficient way)
    magic_squares_hard_coded = [
        [[2, 7, 6], [9, 5, 1], [4, 3, 8]],
        [[4, 9, 2], [3, 5, 7], [8, 1, 6]],
        [[8, 3, 4], [1, 5, 9], [6, 7, 2]],
        [[6, 1, 8], [7, 5, 3], [2, 9, 4]],
        [[6, 7, 2], [1, 5, 9], [8, 3, 4]],
        [[2, 9, 4], [7, 5, 3], [6, 1, 8]],
        [[4, 3, 8], [9, 5, 1], [2, 7, 6]],
        [[8, 1, 6], [3, 5, 7], [4, 9, 2]],
    ]
    magic_squares = magic_squares_creating_efficiently()

    minimum_cost = 99
    for square in magic_squares:
        cost = 0
        for i in range(0, 3):
            for j in range(0, 3):
                cost += abs(s[i][j] - square[i][j])

        minimum_cost = min(minimum_cost, cost)

    return minimum_cost


def magic_squares_creating_efficiently():
    # create magic squares
    blank_square = []
    for row in range(0, 3):
        row = []
        for column in range(0, 3):
            row.append(None)
        blank_square.append(row)

    possible_squares = []
    for row in range(0, 3):
        for column in range(0, 3):
            blank_square[row][column] = 9
            possible_squares.append([[cell for cell in row] for row in blank_square])
            blank_square[row][column] = None

    old_squares = []
    # start by big numbers to filter magic numbers faster
    for number in range(8, 0, -1):
        old_squares = possible_squares
        possible_squares = []
        for possible_square in old_squares:
            for row in range(0, 3):
                for column in range(0, 3):
                    if possible_square[row][column] is None:
                        # check row validity
                        sum_row = number
                        for j in range(0, 3):
                            if possible_square[row][j] is not None:
                                sum_row += possible_square[row][j]

                        if sum_row < 16:
                            # check column validity
                            sum_column = number
                            for i in range(0, 3):
                                if possible_square[i][column] is not None:
                                    sum_column += possible_square[i][column]

                            if sum_column < 16:
                                possible_square[row][column] = number
                                possible_squares.append(
                                    [[cell for cell in row] for row in possible_square]
                                )
                                possible_square[row][column] = None

    magic_squares = []
    for square in possible_squares:
        square_is_magic = True
        # check sum columns
        for column in range(0, 3):
            if square[0][column] + square[1][column] + square[2][column] != 15:
                square_is_magic = False
        # check sum rows
        for row in range(0, 3):
            if square[row][0] + square[row][1] + square[row][2] != 15:
                square_is_magic = False

        # check sum diagonals
        if square[0][0] + square[1][1] + square[2][2] != 15:
            square_is_magic = False
        if square[0][2] + square[1][1] + square[2][0] != 15:
            square_is_magic = False

        if square_is_magic:
            magic_squares.append(square)

    return magic_squares