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:

Is this understanable?
How Pythonic is this?
Are there any glaring bugs / convention mistakes / missuses of structures?
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.

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

Community · Accepted Answer · 2017-05-23 12:40:57Z

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.

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
– Bakuriu, Commented Mar 31, 2014 at 15:39
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
– Underdetermined, Commented Mar 31, 2014 at 17:51
Is there a reason for using range(0,10) instead of range(10)? — wchargin
– wchargin, Commented Mar 31, 2014 at 22:19
Hmm.. that underscore notation is pretty neat! What would be the convention for a nested loop with another don't-care? Double underscore? — flakes
– flakes, Commented Apr 1, 2014 at 13:41

jcfollower · Accepted Answer · 2014-03-31 14:25:30Z

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
– Underdetermined, Commented Mar 31, 2014 at 17:52

jcfollower · Accepted Answer · 2014-03-31 13:16:48Z

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

Stack Exchange Network

Deepcopy usage in a Sudoku solver

3 Answers 3

----------

----------

You must log in to answer this question.

Hot Network Questions

Deepcopy usage in a Sudoku solver

3 Answers 3

----------

----------

You must log in to answer this question.

Related

Hot Network Questions