Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Uncategorized category for Magic Square by Moff
class Puzzle(object):
def __init__(self, m):
self.size = len(m)
self.line_sum = (1 + self.size ** 2) * self.size // 2
unused = list(range(1, self.size ** 2 + 1))
for row in m:
for v in row:
if v:
unused.remove(v)
self.solution = None
self.solve(m, unused)
@staticmethod
def find_hole(m):
for i, row in enumerate(m):
for j, v in enumerate(row):
if v == 0:
return i, j
def is_line_valid(self, line):
return not (all(line) and sum(line) != self.line_sum)
def is_valid(self, m):
for row in m:
if not self.is_line_valid(row):
return False
for c in range(self.size):
if not self.is_line_valid([m[r][c] for r in range(self.size)]):
return False
if not self.is_line_valid([m[i][i] for i in range(self.size)]):
return False
if not self.is_line_valid([m[i][self.size - i - 1] for i in range(self.size)]):
return False
return True
def solve(self, m, unused):
if self.solution is not None:
return
if not self.is_valid(m):
return
if not unused:
self.solution = m
return
r, c = self.find_hole(m)
for i, n in enumerate(unused):
mn = [row[:] for row in m]
mn[r][c] = n
self.solve(mn, unused[:i] + unused[i+1:])
def checkio(m):
return Puzzle(m).solution
Aug. 29, 2015