MemoryError and generators

Question

I'm trying to create a way to solve a problem where there's a 3x4 table with the 4 corners missing. The goals is to create a algorithm to fill that table with numbers from 1~8 where neither of those numbers can be 1 block close to a cell of it's prior number (eg: 2 can't be close to 1), both in vertical, horizontal and diagonally.

Since I'm new to programing I'm probably doing it the wrong way, I'm generating a list of all the possible placements of the numbers in the cells. But with a 3x4-4 grid it is around 8^8 possible cases(from [1,2,3,4,5,6,7,8] to [8,7,6,5,4,3,2,1])

I'm doing this because my first idea was to make a function to test the data if it matches the criteria afterwards, not requiring to generate the numbers everytime. I'm using pickle to dump the data into a txt file. But the file is 280mb and it freezes my computer for a couple of mintues and then it prints Memory Error.

Sorry if this doesn't make sense, I've started programing a montth ago.

My current code to generate this list is:

for a in xrange(1,9):
    for b in xrange(1, 9):
        for c in xrange(1, 9):
            for d in xrange(1, 9):
                for e in xrange(1, 9):
                    for f in xrange(1, 9):
                        for g in xrange(1, 9):
                            for h in xrange(1, 9):
                                if a != (b and c and d and e and f and g and h) and b != (
                                    a and c and d and e and f and g and h) and c != (
                                    b and a and d and e and f and g and h) and d != (
                                    b and c and a and e and f and g and h) and e != (
                                    b and c and d and a and f and g and h) and f != (
                                    b and c and d and e and a and g and h) and g != (
                                    b and c and d and e and f and a and h) and h != (b and c and d and e and f and g and a):
                                    probs.append((a, b, c, d, e,f,g,h))

And you might want to look into `itertools` to produce your specific combinations, instead. — Martijn Pieters, Dec 15 '13 at 09:07
You should seriously consider [`itertools.product`](http://docs.python.org/2/library/itertools.html#itertools.product) — thefourtheye, Dec 15 '13 at 09:07
You're createing an array with 9x9x9x9x9x9x9x9 elements, and those elements are arrays of 8 numbers. That's huge. — Barmar, Dec 15 '13 at 09:22

score 1 · Accepted Answer · edited Dec 15 '13 at 09:31

1

As the comments suggest, there are more efficient inbuilt methods for doing your permutation, but the first big bug is your uniqueness check.

In python, (7 and 12) simply evaluates to 12, while (7 and 12 and 9) evaluates to 9. It doesn't, mean "Apply the inequality to all of these". Therefore you're getting the equivalent of if a != h and b != h and ... There's rather a lot of combinations where h is unique, and the others can be whatever they want. You're adding all of these to probs, and that's using a lot of memory.

The second problem is that, as far as I can see, you're not actually checking the rules of the challenge. You don't want to store the possibilities where 1 is right next to 2, because even with the uniqueness check sorted out, you still have 8! combinations.

edited Dec 15 '13 at 09:31

Burhan Khalid

169,990
18
245
284

answered Dec 15 '13 at 09:26

Josiah

1,072
6
15

Thanks for the reply. I'm aware of that, my first thougth was to create the data, then select only the ones(or one) which meet the rules, that's because for me it's kinda hard to see ahead. I'll take a look at the test, I could'nt even see the result because it gave me memory error. – f.rodrigues Dec 15 '13 at 10:06
If you're in any doubt, you can find out how the python interpreter understands little snipits just by typing them in. Once you start to optimise it, you'll need to use a pair of for loops, but for the moment you might find the test `(a not in [b, c, d, e, f, g, h])` helps. That creates a list containing the values the later variables, and then confirms that the earlier value doesn't appear. Note that if a isn't b, b isn't a either. Therefore you only have to check whether b is in [c .. h], as a has already been ruled out. – Josiah Dec 15 '13 at 13:50
So, I have changed a bit the code, still didn't figure out how itertools works and just by changing the If statements from one big block in the end of the For loops to one in each For loop. I manage to reduce the computing time from 1 min to less than 3 secs! And I made the a function at the end of all those For statements, and got the answer! Thanks so much. – f.rodrigues Dec 15 '13 at 21:12

score 0 · Answer 2 · answered Dec 15 '13 at 14:01

I can not offer a direct answer to your question, however I had recently stumbled on a webpage that is very comprehensive about solving sudokus with python: http://norvig.com/sudoku.html Your question, to me anyway seems to have similarities, grids, non repeating single digit #'s, rules for # position, Constraint Propagation, etc... good Luck!

MemoryError and generators

2 Answers2