I wrote a program to solve a magic numbers puzzle. The puzzle works like this:
You have an
NxN
square where each row, column, and diagonals add up tox
except some of the numbers in the square are switched. Find the numbers that are out of place and switch them.
Here's an example:
16 16 11 09 14
17 09 29 13 01
15 05 06 16 15
07 03 17 11 12
14 17 03 08 06
The numbers that are out of place and now switched are
16 16 03 09 14
06 09 29 13 01
15 05 06 17 15
07 11 17 11 12
14 17 03 08 16
Here is a partially solved grid to which you can use as input to see that it works
16 16 03 09 14
06 09 29 13 01
15 05 06 17 15
07 16 17 11 12
14 17 03 08 11
I'm positive this code works although it takes forever to run and hasn't finished yet. The reason it hasn't finished is because it has 25^25 recursive steps at most which is an absurdly big number. If you run it with only two of the numbers unsolved then it finishes in about a second. I'm also trying to figure out a small square to test it on. I wrote another program to create one but it also takes awhile but it's getting close and I will upload that when it finishes. In the meantime does anyone have an idea of how I can speed this up?
import math
import copy
import sys
def solve(current, left, l):
if check_rows(current, l) and check_cols(current,l) and check_diag(current,l):
for i in range(0,len(current),5):
print('%02d %02d %02d %02d %02d' % (current[i], current[i+1], current[i+2], current[i+3], current[i+4]))
sys.exit(1)
for i in left:
current.append(i)
tmp = copy.deepcopy(left)
tmp.pop(tmp.index(i))
solve(current, tmp, l)
current.pop()
return
def check_rows(grid, l):
if len(grid) == l:
sq = int(math.sqrt(len(grid)))
for i in range(0,sq):
row = 0
for j in range(0,sq):
row += grid[i*sq + j]
if row != 58: return False
return True
return False
def check_cols(grid, l):
if len(grid) == l:
sq = int(math.sqrt(len(grid)))
for i in range(0,sq):
col = 0
for j in range(0,sq):
col += grid[j*sq+i]
if col != 58: return False
return True
return False
def check_diag(grid, l):
if len(grid) == l:
d1 = 0
d2 = 0
sq = int(math.sqrt(len(grid)))
for i in range(0,sq):
d1 += grid[i*sq+i]
d2 += grid[i*sq+sq-i]
if d1 != 58 or d2 != 58: return False
return True
return False
f = open('./grid.txt','r')
grid = []
for line in f:
for i in range(0, len(line), 3):
s = ''
s+=line[i]+line[i+1]
grid.append(int(s))
c = []
print len(grid)
solve(c,grid, len(grid))
print('No Solution')
For anyone interested here is the other version of this that I wrote that works as long there are not two substitutions in the same row or column. I'm currently trying to figure out how to deal with that.
import sys
ans = 0
class ints:
def __init__(self, i, j, val, tot):
self.i = i
self.j = j
self.val = val
self.tot = tot
self.switches = []
def get_grid():
with open('./files/easyNumbers.txt','r') as file_handler:
grid = [map(int, line.split()) for line in file_handler]
return grid
def get_col(c, grid):
col = []
for r in grid:
col.append(r[c])
return col
def find_intersections(grid):
intersections = []
col = []
row = []
for c in range(0,len(grid[0])):
col.append(sum(get_col(c,grid)))
for r in grid:
row.append(sum(r))
for i in range(0, len(grid[0])):
for j in range(0,len(grid[0])):
if row[i] == col[j]:
intersections.append(ints(i, j, grid[i][j], row[i]))
return intersections
def check_row(row, grid):
if sum(grid[row]) == ans: return True
return False
def check_col(col, grid): #Currently unused function
if sum(get_col(col,grid)) == ans: return True
return False
def check_diag(grid): #Currently unused function
d1, d2 = 0, 0
for index, r in enumerate(grid):
d1+=r[index]
d2+=r[len(r)-index]
if d1 == ans and d2 == ans: return True
return False
def make_move(grid):
tmp = grid
inters = find_intersections(grid)
possibles = []
for i in inters:
possibles.append(grid[i.i][i.j])
for i in inters:
for j in possibles:
previous = tmp[i.i][i.j]
tmp[i.i][i.j] = j
if check_row(i.i, tmp): break
else:tmp[i.i][i.j] = previous
for i in tmp:
for j in ' '.join(map(str, i)).split():
sys.stdout.write('%02d ' % int(j))
print('')
def main():
global ans
#ans = raw_input('Enter Sum: ')
ans = 58
grid = get_grid()
make_move(grid)
if __name__ == "__main__":
main()
58
everywhere? And "it takes forever to run and hasn't finished yet
" is not a good sign. Perhaps you should make sure it works first, and then come back? \$\endgroup\$58
that's just what the rows, cols, and diags are supposed to add up to for the puzzle I'm testing on. Even though it hasn't finished it is working as expected due to some testing I did. I also expect it to take a long time since it should be 36^36 permutations which is 106387360000000000000000000000000000000000000000000000000 calculations. aka waaaaaay to long \$\endgroup\$58
in a variable somewhere, as it's an easy number to calculate. I would also recommend building a much smaller problem to test it with first. (Hint: one can build amagic numbers square
out of all consecutive integers 1 through 9.) \$\endgroup\$