4
\$\begingroup\$

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()
\$\endgroup\$
12
  • \$\begingroup\$ 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? \$\endgroup\$ – Der Kommissar Aug 5 '15 at 18:02
  • \$\begingroup\$ @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 \$\endgroup\$ – SirParselot Aug 5 '15 at 19:20
  • \$\begingroup\$ 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.) \$\endgroup\$ – Der Kommissar Aug 5 '15 at 19:59
  • \$\begingroup\$ I tested your code with the example given and your code seems broken. \$\endgroup\$ – Mast Aug 5 '15 at 20:15
  • 1
    \$\begingroup\$ @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 \$\endgroup\$ – SirParselot Aug 6 '15 at 13:54
5
\$\begingroup\$

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.

\$\endgroup\$
7
  • \$\begingroup\$ Why would you not want to use sys.exit()? \$\endgroup\$ – SirParselot Aug 6 '15 at 17:33
  • \$\begingroup\$ 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 \$\endgroup\$ – SirParselot Aug 6 '15 at 17:52
  • 1
    \$\begingroup\$ @SirParselot That's a design problem. It's a bit like goto, if you need to use it you usually made a design error. \$\endgroup\$ – Mast Aug 6 '15 at 18:05
  • \$\begingroup\$ I can make it return all the way back but it just doesn't seem as efficient. \$\endgroup\$ – SirParselot Aug 6 '15 at 18:13
  • \$\begingroup\$ 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 \$\endgroup\$ – SirParselot Aug 6 '15 at 18:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.