Magic numbers recursive solver

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[

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 isq + j and jsq + 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

StackExchange Code Review Q#99125, answer score: 5