Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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?

I am happy about any comments you can make about the following block of code:

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.

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

3 Answers 3

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.

share|improve this answer
1  
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 at 15:39
    
TIL : dict.fromkeys(). Thanks! –  Josay Mar 31 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 at 17:51
1  
Is there a reason for using range(0,10) instead of range(10)? –  WChargin Mar 31 at 22:19
    
No good reason : I have updated my answer. –  Josay Apr 1 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])
share|improve this answer
    
Thank you for the prompt answers. These are things I can easily implement. –  Underdetermined Mar 31 at 17:52

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
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.