Find the 3x3 matrix, M, whose rows, columns and diagonals add up to 15. Condition: you must use every number from 1-9.
I'm not very clever, so I just tried this brute force method:
def solve_999():
for a in range(1, 10):
for b in range(1, 10):
for c in range(1, 10):
for d in range(1, 10):
for e in range(1, 10):
for f in range(1, 10):
for g in range(1, 10):
for h in range(1, 10):
for i in range(1, 10):
if (a+b+c == d+e+f == g+h+i == a+d+g == b+e+h == c+f+i == a+e+i == c+e+g == 15):
if check_unique([a, b, c, d, e, f, g, h, i]):
print(a, b, c)
print(d, e, f)
print(g, h, i)
return
def check_unique(L):
d = {1:0, 2:0, 3:0, 4:0, 5:0, 6:0, 7:0, 8:0, 9:0}
for letter in L:
d[letter] += 1
if d[letter] > 1:
return False
return True
It works, but it isn't very efficient. Can anyone help me find a more efficient solution?
The biggest speedup you will get will be from generating your squares so that they are already unique. The easiest way to do this is itertools.permutations. This will reduce you to checking 9! == 362880 boards rather than 387420489 boards (about 1/1000th the work) and you don't have to check to make sure they are unique.
from itertools import permutations
t1=time()
for board in permutations(list(range(1,10)),9):
if sum(board[0:3]) == 15:
if sum(board[3:6])== 15:
if board[0]+board[3]+board[6]==15:
if board[1]+board[4]+board[7]==15:
if board[0]+board[4]+board[8]==15:
if board[2]+board[4]+board[6]==15:
print(board[0:3])
print(board[3:6])
print(board[6:9])
break
One major problem with this solution is that we are still checking a ton more cases than we need to. Something to notice is that for each (a,b,d,e) there exists a maximum of 1 value for each of c, f, g, h, and i. This means that we only have to check through 9P4 == 3024 possibilities. The downside of this is that we lose guarantee that all the values are unique. But even if we add this checks, we still see another 10x speedup over our simpler code.
def solve_999():
for a,b,d,e in permutations(range(1,10),4):
c = 15 - (a + b)
f = 15 - (d + e)
g = 15 - (a + d)
h = 15 - (b + e)
i = 15 - (a + e)
if 15 == g+h+i == c+f+i == c+e+g:
if len(set([a,b,c,d,e,f,g,h,i]))==9:
print(a, b, c)
print(d, e, f)
print(g, h, i)
print()
break
To time the code:
from timeit import timeitrom itertools import permutations
def solve_999():
for a,b,d,e in permutations(range(1,10),4):
c = 15 - (a + b)
f = 15 - (d + e)
g = 15 - (a + d)
h = 15 - (b + e)
i = 15 - (a + e)
if 15 == g+h+i == c+f+i == c+e+g:
if len(set([a,b,c,d,e,f,g,h,i]))==9:
return
print(timeit(solve_999, number=1000))
yields a time of 2.9 seconds/10000 tries == .00029 sec/try