# Sudoku Solver: what are good ways to avoid the deepcopy?

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.

Full code (400 lines) can be found here: github/sudoku.py

My Questions:

1. Understanable?
2. How Pythonic is this?
3. Glaring Bugs / Convention mistakes / Missuses of Structures?
4. How can I introduce Unit testing?

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 = []

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__():
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.

-
New style classes should be derived from object. i.e. class SudokuGrid: should be class SudokuGrid(object): –  ebarr Mar 31 '14 at 12:18
Use __str__ instead of print_Grid for SudokuGrid. docs.python.org/2/reference/datamodel.html#special-method-names –  alexwlchan Mar 31 '14 at 14:02

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)


## ----------

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.

-
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. –  Bakuriu Mar 31 '14 at 15:39
TIL : dict.fromkeys(). Thanks! –  Josay Mar 31 '14 at 15:55
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. –  Underdetermined Mar 31 '14 at 17:51
Is there a reason for using range(0,10) instead of range(10)? –  WChargin Mar 31 '14 at 22:19
No good reason : I have updated my answer. –  Josay Apr 1 '14 at 8:27

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

-
Thank you for the prompt answers. These are things I can easily implement. –  Underdetermined Mar 31 '14 at 17:52

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

-