Magic numbers recursive solver

Question

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 to x 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()

• Der Kommissar: Did you intentionally hardcode the 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?
• SirParselot: @EBrown Yes I did purposely hardcode the 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
• Der Kommissar: If I knew python well I would help you out. Unfortunately I don't know much, the best I could mention is to try to store the 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 a magic numbers square out of all consecutive integers 1 through 9.)
• Mast: I tested your code with the example given and your code seems broken.
• SirParselot: @JoeWallis It's working code. I'll add a partially solved grid. It finished with it but like I said earlier to solve the entire grid at most it will have ~106387360000000000000000000000000000000000000000000000000 recursive steps which will take a super computer to solve in a reasonable amount of time. That's why I'm asking if anyone has suggestions on how to speed it up

Answer 1

First, you want to make the program more dynamic as @EBrown said.

If you could pass in a number that you should add up to, your program would be better. However not faster.

---

Opening files you should always close a file.

f.close()

Also I can't enter the number '102' into your program. This is as it is very static. You can use str.split() to split the numbers.

To do all the above in two lines you can use this:

with open('./grid.txt','r') as file_handler:
 grid = [int(num) for line in file_handle for num in line.split()]

I personally prefer having the output as a 2D array, to do this:

with open('./grid.txt','r') as file_handler:
 grid = [map(int, line.split()) for line in file_handler]

The latter doesn't work with your program. And so use the former.

---

The two functions check_rows and check_cols are very alike.

First you use int(math.sqrt(len(grid))) to find the size of the 2D array. This is a rather expensive operation. You should pass that number, or better wrap the function with that number.

You don't use the function sum. And you also don't use xrange.

You should almost always use xrange in Python2, so much so, that xrange became range in Python3.
But why? It makes a generator, and is normally faster than building a list, and then iterating through it.

If I were to re-write check_rows:

def check_rows(sq, ans):
 def inner(grid, l):
 if len(grid) != l:
 return False
 for i in xrange(sq):
 if sum(grid[i*sq + j] for j in xrange(sq)) != ans:
 return False
 return True
 return inner

If you do the same with check_col then you will find it's almost the same.

The difference is i*sq + j and j*sq + i.

If you wanted to merge this together you can use lambda, and make two functions.

def check_maker(sq, ans, fn):
 def inner(grid, l):
 if len(grid) != l:
 return False
 for i in xrange(sq):
 if sum(grid[fn(i, j, sq)] for j in xrange(sq)) != ans:
 return False
 return True
 return inner
sqr = int(math.sqrt(len(grid)))
check_rows = check_maker(sqr, 58, lambda i, j, sq: i*sq + j)
check_cols = check_maker(sqr, 58, lambda i, j, sq: j*sq + i)

This reduces the complexity of the program.

However it doesn't allow for different sized edges.

---

You can do some of the same things as above with check_diag.

There is no need to find sq again and again and again. And you can make it easier to read.

def diag_maker(sq, ans):
 def inner(grid, l):
 if len(grid) != l:
 return False
 return sum(grid[i*sq + i] for i in xrange(sq)) == ans and \
 sum(grid[(i + 1)*sq - i] for i in xrange(sq)) == ans
 return inner

---

Finally solve. You can have the if len(grid) == l check in here. That way you don't have to check three times. And then you can clean the functions to be simpler.

You shouldn't use sys.exit. Nor should you have an empty return.

A simple return True or return False can tell us if we need to print.

The % operator is discouraged. Use str.format instead. As an alternate you could use map, str and str.join.

if len(current) == l and \
 check_rows(current, l) and \
 check_cols(current, l) and \
 check_diag(current, l):
 print('\n'.join(
 ' '.join(map(str, current[i:i + sq]))
 for i in xrange(0, len(current), sq)))
 return False

---

The second half of solve is where all the slow-down is now.
To speed this up you would need to prevent re-checking the same grid.

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

Is the 'same' as:

14 17 03 08 16
07 11 17 11 12
15 05 06 17 15
06 09 29 13 01
16 16 03 09 14

The 'same' grid are when they are:

• Flipped
• Rotated 90°/180°

There is probably a way to prevent these, however I cannot think of it right now.

---

If I can figure a way to check for the above I will add it here.

The for i in left.

First, you should use enumerate to track the index of the item you are manipulating.
There is a problem with your current implementation due to this.

There is no need to import copy. You use a 1D array so splitting is enough to 'deep copy'.

To amend these things you could do:

for index, item in enumerate(left):
 current.append(item)
 solve(current, left[:index] + left[index + 1:], l)
 current.pop()

This should be faster than the previous version as, copy.deepcopy is \$O(n)\$ and lst.pop is \$O(n)\$ worst case.

Where the current implementation is amortized worst case and average case \$O(n)\$.

If you are unsure on if array slices are 'deep copys' on 1D arrays you can try:

>>> a = [1, 2, 3]
>>> b = a[1:]
>>> a[1] = 4
>>> a
[1, 4, 3]
>>> b
[2, 3]

However mutables aren't 'deep copied'.

This isn't actually deep copying, it's just how mutability works in Python. So if you use 2D arrays at a later point please use copy.deepcopy.

---

To wrap this all up you can change solve to:

def solve(current, left, l, sq): 
 if len(current) == l and \
 check_rows(current, l) and \
 check_cols(current, l) and \
 check_diag(current, l):
 print('\n'.join(
 ' '.join(map(str, current[i:i + sq]))
 for i in xrange(0, len(current), sq)))
 return False
 for index, item in enumerate(left):
 current.append(item)
 if not solve(current, left[:index] + left[index + 1:], l, sq):
 return False
 current.pop()
 return True

And then you can use it as:

if solve(c, grid, len(grid), sq):
 print('No Solution.')

---

Just to note again. This doesn't increase the speed, as I cannot think of an algorithm to do so, yet.

• SirParselot: Why would you not want to use sys.exit()?
• SirParselot: well if you don't exit the program and instead just use return then it will just return to the previous layer of recursion and will never really exit. You would have to change the recursive part to be if not solve(): return False that way it will back all the way out of the recursion. That being said, I feel like it would be more efficient to exit then back up N layers
• Mast: @SirParselot That's a design problem. It's a bit like goto, if you need to use it you usually made a design error.
• SirParselot: I can make it return all the way back but it just doesn't seem as efficient.
• SirParselot: wouldn't the difference be the how deep you are in the recursion vs exiting the program? It prints in both cases. Also the reason I have print no solution in the main is because that means it went through every permutation of the board and none met the requirements