CPSC120
Fundamentals of Computer Science

Activity 26

Netsted Lists

Magic Square

One intriguing application of multidimensional lists is magic squares. Magic squares are a mathematical structure that has been studied for centuries. A magic square is a matrix where the sum of the rows, columns, and diagonals are the same. Constructing a magic square is a little bit complicated, but determining if a square of numbers is magic is not too complicated.

Details

Write the function is_magic_square(square: [[int]]) -> bool. The parameter square is a square, two-dimensional list of integers. The function should return True if square is a magic square, and False otherwise.

Test Cases

import test

def is_magic_square(square: [[int]]) -> bool:
    # Put your code here

def main() -> None:
    test.equal(is_magic_square([[8, 1, 6], [3, 5, 7], [4, 9, 2]]), True)
    test.equal(is_magic_square([[17, 24, 1, 8, 15], [23, 5, 7, 14, 16], [4, 6, 13, 20, 22], [10, 12, 19, 21, 3], [11, 18, 25, 2, 9]]), True)
    # Put more test cases here
    return None

main()

Hint

This function is easier to write with additional functions. Here are some functions that will make it easier:

  • sum_row(square: [[int]], row: int) -> int: this function should return the sum of the specified row

  • sum_column(square: [[int]], col: int) -> int: this function should return the sum of the specified column

  • sum_major_diagonal(square: [[int]]) -> int: this function should return the sum of the major diagonal (the elements from the upper left to the lower right)

  • sum_minor_diagonal(square: [[int]]) -> int: this function should return the sum of the minor diagonal (the elements from the upper right to the lower left)

The is_magic_square function must compare every row, column, and diagonal to the magic number. But to do this, it must first compute the magic number. Since the sum of all rows, columns, and diagonals must be the same, pick the magic number to be any one of them. For example, choose the sum of the first column.

Sum each row and check if it's equal to the magic number. Sum each column, check if it's equal to the magic number. Sum each diagonal, and check if it's equal to the magic number. If any of them are not equal to the magic number, you don't have a magic square. Use the above functions to make writing this function easier.

Challenge 1

One additional restriction for a magic square is that every magic square element has to be unique. For example, [[1, 1], [1, 1]] is not a magic square. Add an additional check to verify you have truly magic squares.

Challenge 2

There are some relatively straightforward algorithms for generating a square that is guaranteed to be magic. Read the Wikipedia article for magic squares, and write a function called generate_magic_square(size) to generate a magic square of the specified size.