Deepcopy usage in a Sudoku solver

Question

In an effort to teach myself some python and programming in general I made a Sudoku Solver (as many others have done before me from what I can tell). The one thing that bugs me a little is my use of deepcopy which I think I can avoid by implementing __eq__ in my classes.

My questions:

1. Is this understanable?
2. How Pythonic is this?
3. Are there any glaring bugs / convention mistakes / missuses of structures?
4. How can I introduce unit testing?

Full code (400 lines) can be found here.

class SudokuCell:
    """Most Basic Sudoku Cell
    -Contains 9 Possible values, initialized at true
    -Can return the possible cases
    """
    def __init__(self):
        self.values = {1: True,2:True,3:True,4:True,5:True,6:True,7:True,8:True,9:True}

    def check_cell(self):
        """return all values still possible"""
        out = []
        for k,d in self.values.items():
            if d==True:
                out.append(k) 
        return out

    def set_cell(self, val):
        """set all values to False except val"""    
        for k,d in self.values.items():
            if k != val:
                self.values[k] = False
        self.values[val]=True

    def reset_cell(self):
        self.values = {1: True,2:True,3:True,4:True,5:True,6:True,7:True,8:True,9:True}

class SudokuGrid:
    def __init__(self):
        self.Cells = []
        for x in range(0,81):
            Cell = SudokuCell()
            self.Cells.append(Cell)
        self.groups = self.__define_groups__()

    def __eq__(self, other):
        return self.Cells == other.Cells

    def print_Grid(self):
        """print Sudoku Grid"""
        values=self.__str_fill__()
        print '-------------------'
        for x in range (0,3):
            print '|'+values[x*9] +' '+ values[x*9+1] +' ' + values [x*9+2] + '|'+values[x*9+3] +' '+ values[x*9+4] +' ' + values [x*9+5] + '|'+values[x*9+6] +' '+ values[x*9+7] +' ' + values [x*9+8] + '|'
        print '*-----*-----*-----*'
        for x in range (3,6):
            print '|'+values[x*9] +' '+ values[x*9+1] +' ' + values [x*9+2] + '|'+values[x*9+3] +' '+ values[x*9+4] +' ' + values [x*9+5] + '|'+values[x*9+6] +' '+ values[x*9+7] +' ' + values [x*9+8] + '|'
        print '*-----*-----*-----*'
        for x in range (6,9):
            print '|'+values[x*9] +' '+ values[x*9+1] +' ' + values [x*9+2] + '|'+values[x*9+3] +' '+ values[x*9+4] +' ' + values [x*9+5] + '|'+values[x*9+6] +' '+ values[x*9+7] +' ' + values [x*9+8] + '|'
        print '-------------------'


    def check_gridsolved(self):
        for x in self.Cells:
            if len(x.check_cell())!=1:
                return False
        return True

    def __define_groups__(self):
        """we need to know how the grid is formed"""
        groups=[]
        #rows
        for x in range(0,9):
            groups.append([x*9,x*9+1,x*9+2,x*9+3,x*9+4,x*9+5,x*9+6,x*9+7,x*9+8])

        #collumns
        for x in range(0,9):
            groups.append([x,x+9,x+18,x+27,x+36,x+45,x+54,x+63,x+72])

        #squares 1
        for x in range(0,3):
            groups.append([x*3,x*3+1,x*3+2,x*3+9,x*3+10,x*3+11,x*3+18,x*3+19,x*3+20])
        #squares 2
        for x in range(9,12):
            groups.append([x*3,x*3+1,x*3+2,x*3+9,x*3+10,x*3+11,x*3+18,x*3+19,x*3+20])
        #squares 3
        for x in range(18,21):
            groups.append([x*3,x*3+1,x*3+2,x*3+9,x*3+10,x*3+11,x*3+18,x*3+19,x*3+20])            

        return groups

    def __str_fill__(self):
        """get Row for Print"""
        out =[]
        i=0
        for x in self.Cells:
            out.append('*')
            if len(x.check_cell())==1:
                out[i]=str(x.check_cell()[0])
            i+=1
        return out

class Sudoku_Solver():
    '''This class is an iterative non-exhaustive search algorithm for the SudokuGrid'''
    def __init__(self):
        self.Branch = collections.OrderedDict() #{} #stores the Branch info
        self.inputGrid = SudokuGrid()
        self.workingGrid = SudokuGrid()
        self.solved = False
        self.unsolvable = False
        self.solutionGrids = []

    def load(self,SudokuGrid):
        self.inputGrid = copy.deepcopy(SudokuGrid)
        self.workingGrid = copy.deepcopy(SudokuGrid)

    def simple_solver(self):
        iteration = 1
        laststate = SudokuGrid()
        while ((laststate == self.workingGrid)==False): #
            laststate = copy.deepcopy(self.workingGrid) #want to get rid of deepcopy...
            iteration += 1
            if 0==self.__slv_iterate_truncation__():
                #print 'er'
                return 0 #cannot solve
            if 0==self.__slv_iterate_singlefind__():
                #print 'bad eval'
                return 0 #cannot solve            
            if iteration > 30:
                print 'ERROR too many iterations'
                break

        return iteration


    def solve(self):
        iteration = 0
        simple_iteration = self.simple_solver()
        if (simple_iteration)==0:
            self.unsolvable = True

        if (self.workingGrid.check_gridsolved()==False): #start branching
            self.workingGrid.print_Grid()
            print len(Solver.Branch)
            self.Branch.update(self.__slv_find_firstchoice__()) #seed
            self.__slv_iterate_over_branch()

        self.solutionGrids.append(self.workingGrid)
        self.workingGrid.print_Grid()
'''MORE CODE'''

Functionality: basic block is a SudokuCell which can be a value from 1 to 9. A SudokuGrid contains 81 cells as the traditional puzzle. Groups signify the rules of the game (i.e Groups in which a number can only occur once). I have a simple solver which iterates through the groups and checks for inconsistencies (values in a cell that shouldn't be elsewhere) and single values (only one cell has this). After that it is just continuing guesswork. The solver works on all the sudokus I have tried (maybe 5).

I also wanted to learn about unit testing unfortunately had so many implementation questions and too little time to really consider it, but I am thinking of introducing that next.

Answer 1

First : the comments about aesthetic.

You can use List/set/dict comprehension more than you do :

---

self.values = {1: True,2:True,3:True,4:True,5:True,6:True,7:True,8:True,9:True}

becomes :

self.values = {n:True for n in range(10)}

or

self.values = dict.fromkeys(range(10), True)

---

    out = []
    for k,d in self.values.items():
        if d==True:
            out.append(k) 

becomes :

    out = [k for k,d in self.values.items() if d]

From PEP 8 :

Don't compare boolean values to True or False using ==.

---

print '|'+values[x*9] +' '+ values[x*9+1] +' ' + values [x*9+2] + '|'+values[x*9+3] +' '+ values[x*9+4] +' ' + values [x*9+5] + '|'+values[x*9+6] +' '+ values[x*9+7] +' ' + values [x*9+8] + '|'

becomes :

print '|'+ ' '.join(values[x*9+i] for i in range(9)) + '|'

From PEP 8 :

For example, do not rely on CPython's efficient implementation of in-place string concatenation for statements in the form a += b or a = a + b. This optimization is fragile even in CPython (it only works for some types) and isn't present at all in implementations that don't use refcounting. In performance sensitive parts of the library, the ''.join() form should be used instead. This will ensure that concatenation occurs in linear time across various implementations.

---

    for x in self.Cells:
        if len(x.check_cell())!=1:
            return False
    return True

becomes :

    return all(len(x.check_cell()) == 1 for x in self.Cells)

---

groups.append([x*9,x*9+1,x*9+2,x*9+3,x*9+4,x*9+5,x*9+6,x*9+7,x*9+8])

becomes :

groups.append([x*9+i for i in range(9)])

.

groups.append([x,x+9,x+18,x+27,x+36,x+45,x+54,x+63,x+72])

becomes :

groups.append([x+9*i for i in range(9)])

.

groups.append([x*3,x*3+1,x*3+2,x*3+9,x*3+10,x*3+11,x*3+18,x*3+19,x*3+20])

becomes :

groups.append([x*3+i*9+j for i in range(3) for j in range(3)])

.

---

    out =[]
    i=0
    for x in self.Cells:
        out.append('*')
        if len(x.check_cell())==1:
            out[i]=str(x.check_cell()[0])
        i+=1

becomes first using enumerate :

    out =[]
    for i,x in enumerate(self.Cells):
        out.append('*')
        if len(x.check_cell())==1:
            out[i]=str(x.check_cell()[0])

then, with ternary operator

    out =[]
    for x in self.Cells:
        out.append(str(x.check_cell()[0]) if len(x.check_cell())==1 else '*')

finally with list comprehension :

    out =[str(x.check_cell()[0]) if len(x.check_cell())==1 else '*' for x in self.Cells]

----------

Underscore is a conventional variable name for a value that we don't use (more info here).

    for x in range(81):
        Cell = SudokuCell()
        self.Cells.append(Cell)

becomes :

    for _ in range(81):
        Cell = SudokuCell()
        self.Cells.append(Cell)

----------

Now, more relevant comments :

Data structure : at the moment, you are representing cells with dictionnary mapping values to whether they are possible or not. A dictionnary is likely to be a bit overkill here : you might as well use :

• a simple list to perform exactly the same mapping (reindexing your 1 to 9 range to a 0 to 8 range would be a good option).
• a set to convey the same information : a value is possible if and only if it is in the set.

---

Whenever you are using this kind of logic, you should try to keep your structure as small as possible for performance reasons but also because it will make things harder to get wrong. In your case, there probably no need to store the result of __define_groups__() in each instance of the class because the value returned is always the same, you could compute this one and for all and use it for all instances.

Answer 2

Instead of having lots of numbers, replace them with constants ...

ROW_STARTS = range(0, 73, 9)
COLUMN_STARTS = range(9)
COLUMN_INCREMENTS = range(0, 73, 9)
SQUARE_STARTS = [0, 3, 6, 27, 30, 33, 54, 57, 60]
SQUARE_INCREMENTS = [0, 1, 2, 9, 10, 11, 18, 19, 20]

ROWS = [[x+y for y in range(9)] for x in ROW_STARTS]
COLUMNS = [[x+y for y in COLUMN_INCREMENTS] for x in COLUMN_STARTS]
SQUARES = [[x+y for y in SQUARE_INCREMENTS] for x in SQUARE_STARTS]

Then, in your define_groups function, you would ...

groups = []
groups.append([x[:] for x in ROWS])
groups.append([x[:] for x in COLUMNS])
groups.append([x[:] for x in SQUARES])

Answer 3

in your class SudokuCell()

add a function that sets all the values to a boolean, e.g. ...

def reset_all_values(self, new_value):
    self.values = {}
    for i in range(1, 10):
        self.values[i] = new_value

Then, init can call this with True and it can replace reset_cell(). Also, in set_cell, you can just call reset_all_values(False) and then do

self.values[val] = True