views:

55

answers:

1

Four years ago I wrote a Sudoku puzzle solver, and now I'm trying to understand how it works so that I can reuse parts of it for a KenKen puzzle solver. I thought I'd better compactify loops into list comprehensions and pick more self-explanatory names for variables.

There's a class Puz which contains the input puzzle as a list of (81) digits; 1 through 9 where the cell's value is known, and 0 where it is not.

Class Puz also contains a working version of the puzzle, except that here each of the (81) items in the list is a set; where the answer for a cell is known, the set contains one value from 1 to 9, e.g., set([4]), and where the answer is unknown, the set contains the remaining possibilities, e.g., set([3,5,7,9]). When Puz._init__(self, puz) is called, those "maybe" sets in the work list are set to set([1,2,3,4,5,6,7,8,9]), and the first step in getting to a solution is to strike out all the values which appear as answers in that cell's row, column, and 3x3 block.

Originally, the work list was filled in using a for loop: for 0 to 80, if it's an answer, put in the answer as a set, else put in set( range( 1, 10)). I couldn't figure out how to get this kind of conditional into a list comprehension, so I broke it out into a separate "filling function", of which 3 versions are shown below. The fill_funcs differ in their "not-an-answer branches":

return set( range( 1,(self.dim+1)))
return set( self.r_dim_1_based)
return self.set_dim_1_based

As you see, increasing amounts of processing are moved outside the function back to where the little variables are initialized.

The trouble is, the first two variations slip into the Sudoku solver and work exactly the way the original code did. BUT --- the third variation breaks, saying that the 6th set in the working list is (or becomes) empty. YET --- the lists of sets produced by all three variations evaluate as equal:

p.W1 == p.W2 == p.W3 --> True

I'm stumped.

Here's some code for making the lists of sets:

#!/usr/bin/env python
import copy
from math import sqrt

'''
Puzzle #15, from The Guardian: 050624: #41: rated difficult
'''
puz = [
0,0,1, 9,0,0, 3,0,0,
0,0,0, 0,0,0, 2,0,0,
7,6,0, 0,2,0, 0,0,9,

3,0,0, 0,6,0, 0,0,5,
0,0,2, 1,0,3, 4,0,0,
4,0,0, 0,9,0, 0,0,3,

1,0,0, 0,3,0, 0,9,7,
0,0,4, 0,0,0, 0,0,0,
0,0,5, 0,0,8, 6,0,0
]

class GroupInfo: pass

class Puz(GroupInfo):
    def __init__(self, puz):
        self.A =   copy.deepcopy(puz)
        self.ncells =   len( self.A)
        self.r_ncells = range( 0,self.ncells)
        self.dim =      int( sqrt( self.ncells))
        assert (self.dim ** 2) == self.ncells, "puz is not square"
        self.r_dim_0_based = range( 0,self.dim)
        self.r_dim_1_based = range( 1, self.dim + 1)
        self.set_dim_1_based =  set( self.r_dim_1_based) ## <<---- causes to fail!
        ##### with 'empty set at W[5]' !?!?!?

        def W1_fill_func( val):
            if (val == 0):
                return set( range( 1,(self.dim+1)))
            else:
                return set( [val])

        self.W1 = [ W1_fill_func( self.A[cid])  
                   for cid in self.r_ncells ]

        def W2_fill_func( val):
            if (val == 0):
                return set( self.r_dim_1_based)
            else:
                return set( [val])

        self.W2 = [ W2_fill_func( self.A[cid])  
                   for cid in self.r_ncells ]

        def W3_fill_func( val):
            if (val == 0):
                return self.set_dim_1_based
            else:
                return set( [val])

        self.W3 = [ W3_fill_func( self.A[cid])  
                   for cid in self.r_ncells ]

        return
    #def Puz.__init__()
#class Puz

p = Puz(puz)
print p.W1 == p.W2 == p.W3
+2  A: 

self.W3 as you've coded it contains many references to the same set object -- as soon as you call any mutating method on one of those references, you've changed all the others. You need to ensure W3_fill_func returns independent copies of the set of interest, just like all others do, e.g. by changing its return to return set(self.set_dim_1_based).

Alex Martelli
THAT was fast, Alex! I was still editing the title!So, kind of pointless to try to eliminate all the processing from the 'return' line; one way or another, I'm going to have to call set(). But, a set of a set is still a set, and not some kind of "nested set". Raffiniert, sehr raffiniert. And I don't think I'd have hit on that explanation for a looooong time.
behindthefall
Also seems to be sheer dumb luck that this 'mutation of any of references to object changes that object' (which of course, when I write it out like that, I recognize, but when it's buried in an initialization I did not see in this case) hasn't risen up and bitten me before. As in, elsewhere in that Sudoku solver.
behindthefall
Right, `set(someset)` is just a shallow copy (just like `someset.copy()` but I prefer to apply the uniform and nice idiom to "call the type to make a (shallow) copy" idiom widely;-). Anyway, always happy to help!
Alex Martelli
Btw, `set(someset)` is faster than `set(somelist)` -- about twice as fast, when the list is `range(1, 81)`, `timeit` says (on my Mac laptop w/system Python 2.5).
Alex Martelli
Good to know about the speed. So, I should initialize the 'set' variable outside the function, then go set(set_vbl) inside the function, which would get me speed, independent copies, a list comprehension ... I like it.
behindthefall