I have written a python program with backtracking that fills a n * n magic square. It solves for n = 4 in 4.5 seconds but gets stuck when I run it for n = 5 on my machine. How can I optimize the algorithm to make it run faster?
from time import perf_counter
def fillMatrix(n):
nSquared = n * n
lineSum = n * (nSquared + 1) / 2
candidates = set(range(1, nSquared + 1))
matrix = [[None for _ in range(n)] for _ in range(n)]
def isValid(row, col):
# row
rowSum = 0
isFull = True
for item in matrix[row]:
if not item:
isFull = False
continue
rowSum += item
if rowSum > lineSum:
return False
if isFull and rowSum != lineSum:
return False
# column
colSum = 0
isFull = True
for i in range(n):
item = matrix[i][col]
if not item:
isFull = False
continue
colSum += item
if colSum > lineSum:
return False
if isFull and colSum != lineSum:
return False
# diagonal
if row != col and row + col != n - 1:
return True
diagSum = 0
isFull = True
for i in range(n):
item = matrix[i][i]
if not item:
isFull = False
continue
diagSum += item
if diagSum > lineSum:
return False
if isFull and diagSum != lineSum:
return False
diagSum = 0
isFull = True
for i in range(n):
item = matrix[n - i - 1][i]
if not item:
isFull = False
continue
diagSum += item
if diagSum > lineSum:
return False
if isFull and diagSum != lineSum:
return False
return True
def solve(row, col):
if matrix[row][col] == None:
for candidate in candidates.copy():
matrix[row][col] = candidate
if not isValid(row, col):
matrix[row][col] = None
continue
candidates.remove(candidate)
if row == n - 1 and col == n - 1:
return True
currentSolution = False
if col == n - 1:
currentSolution = solve(row + 1, 0)
else:
currentSolution = solve(row, col + 1)
if currentSolution:
return True
candidates.add(candidate)
matrix[row][col] = None
return False
return True
t1 = perf_counter()
print(solve(0, 0))
print(matrix)
t2 = perf_counter()
print(f'{t2 - t1}s')
fillMatrix(5)
