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

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.