Python Program to Count Magic Squares in a Grid in Python

In this article, we will learn how to count magic squares in a grid using Python. A Magic square is a 3 x 3 grid filled with all distinct numbers from 1 to 9 such that each column, row, and both diagonals have an equal sum. To know more about magic squares click here.

Example

Input: grid = { {4, 3, 8, 4},
                {9, 5, 1, 9},
                {2, 7, 6, 2} }
Output: 1
Explanation: 3x3 magic square is {{4, 3, 8}, {9, 5, 1}, {2, 7, 6}}

Count Magic Squares in a Grid in Python

Approach: We are going to check every 3×3 subgrid in the given grid whether the numbers are unique from 1 to 9 and the sum of every row and column and both diagonals are equal. A magic square always has 5 in its center. Hence we can skip the subgrids with 5 as its center.

1. Load the gird.

2. Tranverse through every row for range (0, row-2)  as outer loop i.e. row is the number of rows.

3. Tranverse through every column for range (0, col-2)  as inner loop i.e. col is the number of columns.

4. Check whether the center of the current subgrid is equal to 5 if not skip the subgrid.

5. Else, check the current subgrid is magic square.

  • Create a function MagicSquare that takes elements of the current subgrid as arguments.
  • Now, check every element is unique numbers between 1 to 9.
  • And the sum of column and row and both diagonal is equal to 15.
  • If it is a magic square return True else, False.

6. If the current subgrid is magic square increment count by 1.

7. Finally, return the count.

def MagicSquare(a, b, c, d, e, f, g, h, i):
    num = set([1, 2, 3, 4, 5, 6, 7 ,8 ,9])
    grid_num = set([a, b, c, d, e, f, g, h, i])

    if (num == grid_num and (a+b+c) == 15 and (d+e+f) == 15 and (g+h+i) == 15 and
       (a+d+g) == 15 and (b+e+h) == 15 and (c+f+i) == 15 and (a+e+i) == 15 and (c+e+g) == 15):
       return True
    return False
def CountMagicSquare(grid):
    row = len(grid)
    col = len(grid[0])
    count = 0
    for i in range(0, row-2):
        for j in range(0, col-2):
            if (grid[i+1][j+1] != 5):
                continue
            if(MagicSquare(grid[i][j], grid[i][j+1], grid[i][j+2], grid[i+1][j],
            grid[i+1][j+1], grid[i+1][j+2], grid[i+2][j], grid[i+2][j+1], grid[i+2][j+2])):
                count += 1
    return count

grid = [[4, 3, 8, 4, 3, 8],
        [9, 5, 1, 9, 5, 1],
        [2, 7, 6, 2, 7, 6]]
print("The given grid", end="\n")
r = len(grid)
c = len(grid[0])
for i in range(r):
    for j in range(c):
        print(grid[i][j], end=" ")
    print()
print("The total number of magic squares in the gird: ", CountMagicSquare(grid))

Output

The given grid
4 3 8 4 3 8
9 5 1 9 5 1
2 7 6 2 7 6
The total number of magic squares in the gird: 2

Also, read

Leave a Reply

Your email address will not be published.