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.

• ebarr: New style classes should be derived from object. i.e. class SudokuGrid: should be class SudokuGrid(object):
• alexwlchan: Use __str__ instead of print_Grid for SudokuGrid. docs.python.org/2/reference/datamodel.html#special-method-names

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.

• Bakuriu: And self.values = {n:True for n in range(0,10)} becomes: self.values = dict.fromkeys(range(0,10), True). You can also drop the [ and ] in the join call and avoid building a useless list.
• Underdetermined: I'm am overwhelmed by the thoroughness of your answer. Thank you. Inefficiencies in the declarations was one thing I worried about. I will try to implement these in the coming week.
• wchargin: Is there a reason for using range(0,10) instead of range(10)?
• SylvainD: No good reason : I have updated my answer.
• flakes: Hmm.. that underscore notation is pretty neat! What would be the convention for a nested loop with another don't-care? Double underscore?

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])

• Underdetermined: Thank you for the prompt answers. These are things I can easily implement.

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