Sudoku Solver in Python Using Backtracking

Question

I wrote a Sudoku solver in Python and would love any feedback you can give on anything you see fit - the code, the solution, layout, coding principals, format etc.

The program awaits input of an 81 character string representing game data (zero is a blank space) like the below which is an 'evil' Sudoku game from an online website

010000370000006082000400000003510000700908003000023900000004000820300000065000010

The solver then identifies any certain values in the game based on this configuration as well as identifying viable values for every unfilled box. A backtrack is the performed to reach either a solution or identify an impossible puzzle. The solution (or impossible puzzle) is printed to the screen at the end.

thanks :)

class Cell:
    """defines an individual cell in a sudoku puzzle"""
    def __init__(self,box,row,column,value):
        self.box = box
        self.row = row
        self.column = column
        self.value = value
        
        if value == 0:
            self.value = ' '
            self.viable_values = {1,2,3,4,5,6,7,8,9}
                
class SudokuPuzzle:
    """defines an entire sudoku puzzle grid"""
    def __init__(self,puzzle_string):
        self.data_map = []

        if not self.parse_data_string(puzzle_string):
            raise ValueError('Puzzle string parse failed')
        if not self.validate():
            raise ValueError('Invalid game configuration passed')
            
    def parse_data_string(self,passed_string):
        """ingests passed puzzle string into Cell objects"""      
        if len(passed_string) != 81:
            raise ValueError("Passed string not 81 characters long")
            return False
        
        self.data_map = []
        r,c,b = 1,1,1 #row, col, box

        box_col_1,box_col_2,box_col_3 = 1,2,3 
        offset = 0 #offset increments by 3 at the 4th row and 3 again at the 7th row, used to work out which 'box' we are in
        
        for i in passed_string:
            try:
                cell_data = int(i)
            except:
                raise ValueError("Non interger present in game string")
                return False
                   
            # to calculate which of the 9 boxes (3x3 grids) this cell is in
            if r > 6:
                offset = 6
            elif r > 3:
                offset = 3
                
            if c > 6:
                b = box_col_3+offset
            elif c > 3:
                b = box_col_2+offset
            else:
                b = box_col_1+offset

            new_cell = Cell(b,r,c,cell_data)
            self.data_map.append(new_cell)
            #if we reach end of the column, reset colum to 1 and increment row by 1
            if c == 9: 
                c = 1
                r += 1
            else:
                c += 1
                
        return True
                        
    def validate(self):
        """checks that puzzle in current configuration is valid"""
        self.filled_cells = 0
        for cell in [x for x in self.data_map if x.value != ' ']:
            self.filled_cells += 1
            for other_cell in [y for y in self.data_map if y != cell and y.value != ' ' and y.value == cell.value and (y.row == cell.row or y.column == cell.column or y.box == cell.box)]: 
                return False
        return True
    
    def show(self):
        """prints Sudoku grid to console"""
        for i in self.data_map:
            print(i.value,end=' ')
            if i.column == 3 or i.column == 6:
                print('|',end=' ')
            if i.column == 9:
                print('')
            if (i.row == 3 or i.row == 6) and i.column == 9:
                print('------+-------+------')

        print('Filled cells:',self.filled_cells)

    def solve(self):
        """identifies solution to current puzzle firstly through deductions, then backtracking"""
        change_made = True

        while change_made:
            change_made = False
            self.__deductions()
                
            for cell in [x for x in self.data_map if x.value == ' ']:
                if len(cell.viable_values) == 1:
                    cell.value = cell.viable_values.pop()
                    change_made = True
                    
        if self.validate() and self.filled_cells != 81:
            self.__backtrack()
            
        if self.validate() and self.filled_cells == 81:
            return True
        else:
            return False

    def __backtrack(self):
        """creates a new SudokuPuzzle object to work through backtrack until every viable value for every cell has been evaluted."""
        cell_count = 0
        temp_game = SudokuPuzzle(self.export())
        empty_cells = [] #creates a list of just empty cells for working through
        temp_vv = [] #creates a list of 'set' for each cells viable values.  Maintains same index as empty_cells.  Ensure we can re-set the viable-values if we backtrack
        for cell in [x for x in temp_game.data_map if x.value == ' ']:     
            temp_vv.append(cell.viable_values.copy())
            empty_cells.append(cell)

        while True:
            if cell_count < 0:
                print('Exhausted all viable values, unsolved')
                return
            #if there are no further viable values for this cell, reset the viable values, reset the cell value and step back 1
            if len(empty_cells[cell_count].viable_values) == 0:
                empty_cells[cell_count].viable_values = temp_vv[cell_count].copy()
                empty_cells[cell_count].value = ' '
                cell_count -= 1
            #assign cell a value from viable_values list, update neighbouring viable values
            else:
                empty_cells[cell_count].value = empty_cells[cell_count].viable_values.pop()
                temp_game.__eliminate_nonviable_values_based_on_neighbour_values(empty_cells[cell_count])
                            
                if temp_game.validate():
                    if temp_game.filled_cells == 81:
                        self.parse_data_string(temp_game.export())
                        return
                    else:
                        cell_count += 1          
           
    def __deductions(self):
        """for each row, box and column, identify any viable values that cannot exist based on neighbouring row/box/column and remove them"""
        for cell in [x for x in self.data_map if x.value == ' ']:
            self.__eliminate_nonviable_values_based_on_neighbour_values(cell)
            viable_values_in_row = []
            viable_values_in_col = []
            viable_values_in_box = []
            for sub_cell in [x for x in self.data_map if x.value == ' ' and x != cell]:
                for sub_viable in sub_cell.viable_values:
                    if sub_cell.row == cell.row:
                        viable_values_in_row.append(sub_viable)
                    if sub_cell.column == cell.column:
                        viable_values_in_col.append(sub_viable)
                    if sub_cell.box == cell.box:
                        viable_values_in_box.append(sub_viable)
                       
            values_to_remove = []
            for cell_v in [y for y in cell.viable_values if y not in viable_values_in_row]:
                for row_v in viable_values_in_row:
                    values_to_remove.append(row_v)           
            for cell_v in [y for y in cell.viable_values if y not in viable_values_in_col]:
                for col_v in viable_values_in_col:
                    values_to_remove.append(col_v)   
            for cell_v in [y for y in cell.viable_values if y not in viable_values_in_box]:
                for box_v in viable_values_in_box:
                    values_to_remove.append(box_v)
                    
            for value in values_to_remove:
                try:   
                    cell.viable_values.remove(value)
                except KeyError:
                    pass

    def __eliminate_nonviable_values_based_on_neighbour_values(self,cell):
        """for passed cell, iterate across all data to identiy which values could be valid values based on existing values in relevant row, column and box"""
        neighbour_values = set()
        for other_cell in [x for x in self.data_map if x.value != ' ' and x != cell and (x.row == cell.row or x.column == cell.column or x.box == cell.box)]:
            neighbour_values.add(other_cell.value)

        for i in range(1,10):
            if i in neighbour_values and i in cell.viable_values:
                cell.viable_values.remove(i)

    def export(self):
        """writes puzzle data to string"""
        export_string = ''
        for cell in self.data_map:
            if cell.value == ' ':
                export_string += str(0)
            else:
                export_string += str(cell.value)

        return export_string
            
def main():       
    string_input = input('Enter numbers from Sudoku grid starting from top left and enter across and down with the last digit being bottom right box. Use zero (0) for empty spaces: ')
    #string_input = '010000370000006082000400000003510000700908003000023900000004000820300000065000010'
    print('Inputted string:',string_input)
    game = SudokuPuzzle(string_input)
    game.show()
    print('')
    if game.solve():
        print('Solution found!')
        game.show()
        print('Solution string:',game.export())
    else:
        print('Solution NOT found')
        game.show()
    
if __name__ == '__main__':
    main()

```

Answer 1

PEP-8

PEP-8 is the standard style recommendation for Python. In it, it includes things like how many blank lines, how much indentation, recommendations for variable naming and casing.

There are linters (Flake8, Pylint and others) which check your code against PEP-8 and issue useful warnings. In your case there are several simple and obvious things. You are missing many spaces after commas, many lines are too long and such.

raise returns

You have return statements after your raises, which do nothing, the code is unreachable as raise immediately returns from your function to the enclosing error handler (the next try, the repl or erroring out).

            try:
                cell_data = int(i)
            except:
                raise ValueError("Non interger present in game string")
                return False

You should also avoid bare excepts. In this case it's "ok" because you immediately raise, but say I do a keyboard interrupt (Ctrl-c) while this line is running. I happen to get ValueError rather than the appropriate KeyboardInterrupt error. Always catch the minimum that you intend to handle.

Generators

You are constructing lists in-place using list comprehensions and then looping over them, e.g.:

for cell in [x for x in self.data_map if x.value != ' ']:

While these objects are not very big (81 elements at most), it should probably be a generator, which only returns the elements it needs when requested and not creating them all in advance. This change is simple and just means changing the brackets.

for cell in (x for x in self.data_map if x.value != ' '):

Better docstrings

You have docstrings which is good, but they aren't terribly helpful. Take for example:

    def validate(self):
        """checks that puzzle in current configuration is valid"""

Great, it checks it's valid, that's in the name of the function, what exactly is it checking for? duplicates in the row/col/box? Say so.

Unclear comprehensions

Comprehensions are great and concise, but you really have to ask yourself whether:

for other_cell in [y for y in self.data_map if y != cell and y.value != ' ' and y.value == cell.value and (y.row == cell.row or y.column == cell.column or y.box == cell.box)]:

Is the most readable way of expressing it. Even adding whitespace we end with

for other_cell in (y for y in self.data_map
                   if y != cell and
                   y.value != ' ' and
                   y.value == cell.value and
                   (y.row == cell.row or
                    y.column == cell.column or
                    y.box == cell.box)):

Which is still not clear to me what's going on. First, we want to filter those that are in the same row, column or box, let's turn that into a method on cell called is_neighbour or something similar.

class Cell:
    ...
    def is_neighbour(self, other: Cell) -> bool:
    """ Checks if ``other`` is in same row, column or box as ``self`` """
        return (self.row == other.row or
                self.column == other.column or
                self.box == other.box)

Which makes our generator now look like:

for other_cell in (y for y in self.data_map
                   if y != cell and
                   y.value != ' ' and
                   y.value == cell.value and
                   cell.is_neighbour(y)):

We can also make is_filled a method on cell and use that everywhere:

def is_filled(self) -> bool:
    "..."
    return self.value != ' '

And now we have:

for other_cell in (y for y in self.data_map
                   if y != cell and
                   y.is_neighbour(cell) and
                   y.is_filled() and
                   y.value == cell.value
                   ):

Which tells me what's going on a lot more.

Also, instead of looping through here and returning False, we can instead do:

if any(y != cell and
       y.is_neighbour(cell) and
       y.filled() and
       y.value == cell.value
       for y in self.data_map):
    return False

Using format

In your show method, you loop through building your array from values, honestly, I would say this is an ideal opportunity to use constants and a format string.

# Somewhere at constants level, be that class constant or module constant
# Rather than writing the table out by hand 
ROW = "{}{}{}|{}{}{}|{}{}{}\n"
SEP = "---|---|---\n"
GRID = ((ROW*3)+SEP)*2+ROW*3

# Where you want to use it
GRID.format(*self.data_map)

This is a purely stylistic choice, however.

Answer 2

Simplify Logic

b calculation (get rid of un-needed logic/variables)

b = ((c - 1) // 3 + 1) + ((r - 1) // 3 *3) # first half mimics box_offset, second the offset

validation function. for cell in [x for x in self.data_map if x.value != ' '] has 2 for loops, but because the later inner loop checks value != ' ' you could make this a single for with an inner if. Then the second inner for loop also has 2 for loops, but the logic should just be in the loop to reduce iterations

def validate(self):
    """checks that puzzle in current configuration is valid"""
    self.filled_cells = 0
    for cell in self.data_map:
        if cell.value != ' ':
            self.filled_cells += 1
        for other_cell in self.data_map:
            if other_cell != cell and not other_cell.is_empty() and other_cell.value == cell.value and (other_cell.row == cell.row or other_cell.column == cell.column or other_cell.box == cell.box):
                return False
    return True

Improve Readability

show function, update i to something like cell

Cell having a is_empty function

def is_empty(self):
  return self.value == ' '
...
for cell in [x for x in self.data_map if x.is_empty()]

SudokuPuzzle having a empty_cells function

def empty_cells(self, other_cell=Cell(0,0,0,10)):
  return [x for x in self.data_map if x.is_empty() and x != other_cell]
...
for cell in self.empty_cells():
...
for cell in temp_game.empty_cells():
...
empty_cells = temp_game.empty_cells()
for cell in empty_cells:
...
for sub_cell in self.empty_cells(cell):

Handle Exceptions

SudokuPuzzle's __init__ has the potential to raise an Error but it isn't handled in main

try:
    game = SudokuPuzzle(string_input)
except Exception as e:
    print(e)
    return

Full Code:

class Cell:
    """defines an individual cell in a sudoku puzzle"""
    def __init__(self,box,row,column,value):
        self.box = box
        self.row = row
        self.column = column
        self.value = value
        
        if value == 0:
            self.value = ' '
            self.viable_values = {1,2,3,4,5,6,7,8,9}
          
    def is_empty(self):
      return self.value == ' '
                
class SudokuPuzzle:
    """defines an entire sudoku puzzle grid"""
    def __init__(self,puzzle_string):
        self.data_map = []

        if not self.parse_data_string(puzzle_string):
            raise ValueError('Puzzle string parse failed')
        if not self.validate():
            raise ValueError('Invalid game configuration passed')

    def empty_cells(self, other_cell=Cell(0,0,0,10)):
      return [x for x in self.data_map if x.is_empty() and x != other_cell]
            
    def parse_data_string(self,passed_string):
        """ingests passed puzzle string into Cell objects"""      
        if len(passed_string) != 81:
            raise ValueError("Passed string not 81 characters long")
            return False
        
        self.data_map = []
        r,c,b = 1,1,1 #row, col, box
        
        for i in passed_string:
            try:
                cell_data = int(i)
            except:
                raise ValueError("Non interger present in game string")
                return False
                   
            # to calculate which of the 9 boxes (3x3 grids) this cell is in
            b = ((c - 1) // 3 + 1) + ((r - 1) // 3 *3)

            new_cell = Cell(b,r,c,cell_data)
            self.data_map.append(new_cell)
            #if we reach end of the column, reset colum to 1 and increment row by 1
            if c == 9: 
                c = 1
                r += 1
            else:
                c += 1
                
        return True
                        
    def validate(self):
        """checks that puzzle in current configuration is valid"""
        self.filled_cells = 0
        for cell in self.data_map:
            if cell.value != ' ':
                self.filled_cells += 1
            for other_cell in self.data_map:
                if other_cell != cell and not other_cell.is_empty() and other_cell.value == cell.value and (other_cell.row == cell.row or other_cell.column == cell.column or other_cell.box == cell.box):
                    return False
        return True
    
    def show(self):
        """prints Sudoku grid to console"""
        for cell in self.data_map:
            print(cell.value,end=' ')
            if cell.column == 3 or cell.column == 6:
                print('|',end=' ')
            if cell.column == 9:
                print('')
            if (cell.row == 3 or cell.row == 6) and cell.column == 9:
                print('------+-------+------')

        print('Filled cells:',self.filled_cells)

    def solve(self):
        """identifies solution to current puzzle firstly through deductions, then backtracking"""
        change_made = True

        while change_made:
            change_made = False
            self.__deductions()
                
            for cell in self.empty_cells():
                if len(cell.viable_values) == 1:
                    cell.value = cell.viable_values.pop()
                    change_made = True
                    
        if self.validate() and self.filled_cells != 81:
            self.__backtrack()
            
        if self.validate() and self.filled_cells == 81:
            return True
        else:
            return False

    def __backtrack(self):
        """creates a new SudokuPuzzle object to work through backtrack until every viable value for every cell has been evaluted."""
        cell_count = 0
        temp_game = SudokuPuzzle(self.export())
        empty_cells = temp_game.empty_cells() #creates a list of just empty cells for working through
        temp_vv = [] #creates a list of 'set' for each cells viable values.  Maintains same index as empty_cells.  Ensure we can re-set the viable-values if we backtrack
        for cell in empty_cells:     
            temp_vv.append(cell.viable_values.copy())

        while True:
            if cell_count < 0:
                print('Exhausted all viable values, unsolved')
                return
            #if there are no further viable values for this cell, reset the viable values, reset the cell value and step back 1
            if len(empty_cells[cell_count].viable_values) == 0:
                empty_cells[cell_count].viable_values = temp_vv[cell_count].copy()
                empty_cells[cell_count].value = ' '
                cell_count -= 1
            #assign cell a value from viable_values list, update neighbouring viable values
            else:
                empty_cells[cell_count].value = empty_cells[cell_count].viable_values.pop()
                temp_game.__eliminate_nonviable_values_based_on_neighbour_values(empty_cells[cell_count])
                            
                if temp_game.validate():
                    if temp_game.filled_cells == 81:
                        self.parse_data_string(temp_game.export())
                        return
                    else:
                        cell_count += 1          
           
    def __deductions(self):
        """for each row, box and column, identify any viable values that cannot exist based on neighbouring row/box/column and remove them"""
        for cell in self.empty_cells():
            self.__eliminate_nonviable_values_based_on_neighbour_values(cell)
            viable_values_in_row = []
            viable_values_in_col = []
            viable_values_in_box = []
            for sub_cell in self.empty_cells(cell):
                for sub_viable in sub_cell.viable_values:
                    if sub_cell.row == cell.row:
                        viable_values_in_row.append(sub_viable)
                    if sub_cell.column == cell.column:
                        viable_values_in_col.append(sub_viable)
                    if sub_cell.box == cell.box:
                        viable_values_in_box.append(sub_viable)
                       
            values_to_remove = []
            for cell_v in [y for y in cell.viable_values if y not in viable_values_in_row]:
                for row_v in viable_values_in_row:
                    values_to_remove.append(row_v)           
            for cell_v in [y for y in cell.viable_values if y not in viable_values_in_col]:
                for col_v in viable_values_in_col:
                    values_to_remove.append(col_v)   
            for cell_v in [y for y in cell.viable_values if y not in viable_values_in_box]:
                for box_v in viable_values_in_box:
                    values_to_remove.append(box_v)
                    
            for value in values_to_remove:
                try:   
                    cell.viable_values.remove(value)
                except KeyError:
                    pass

    def __eliminate_nonviable_values_based_on_neighbour_values(self,cell):
        """for passed cell, iterate across all data to identiy which values could be valid values based on existing values in relevant row, column and box"""
        neighbour_values = set()
        for other_cell in [x for x in self.data_map if not x.is_empty() and x != cell and (x.row == cell.row or x.column == cell.column or x.box == cell.box)]:
            neighbour_values.add(other_cell.value)

        for i in range(1,10):
            if i in neighbour_values and i in cell.viable_values:
                cell.viable_values.remove(i)

    def export(self):
        """writes puzzle data to string"""
        export_string = ''
        for cell in self.data_map:
            if cell.is_empty():
                export_string += '0'
            else:
                export_string += str(cell.value)

        return export_string
            
def main():       
    string_input = input('Enter numbers from Sudoku grid starting from top left and enter across and down with the last digit being bottom right box. Use zero (0) for empty spaces: ')
    #string_input = '010000370000006082000400000003510000700908003000023900000004000820300000065000010'
    print('Inputted string:',string_input)
    try:
        game = SudokuPuzzle(string_input)
    except Exception as e:
        print(e)
        return
    game.show()
    print()
    if game.solve():
        print('Solution found!')
        game.show()
        print('Solution string:',game.export())
    else:
        print('Solution NOT found')
        game.show()
    
if __name__ == '__main__':
    main()