Sudoku Solver in Python

Question

I wrote this sudoku solver in Python. This is my first substantial project, and I would love any comments or feedback.

import csv
import copy 

def main() :
  cells = [cell() for i in range(81)] #creates a list of 81 instances of the cell() class.
  openpuzzle(cells)
  printboard(cells)
  cells = solve(cells) 
  printboard(cells)

class cell() : 
  """This class stores the state of each cell on the board. 
  If self.value = 0, the cell is still unknown."""
  def __init__(self) :
    self.value = 0
    self.poss = [1,2,3,4,5,6,7,8,9]
  def __repr__(self) : 
    return "Value: {0} Possibles: {1}".format(self.value, self.poss)

def openpuzzle(cells) : 
  '''Open puzzle, copy into "cells" list'''
  with open('puzzle1.csv') as csvfile : 
    newCells = next(csv.reader(csvfile, delimiter=","))  #read first line
    for i in range(len(cells)) : 
      cells[i].value = int(newCells[i])
  return cells

def printboard(cells) :
  """prints out the board"""
  divider = "." * 21 
  print divider
  for i in range(len(cells)) :
    if cells[i].value == 0 : 
      cValue = " " 
    else : 
      cValue = str(cells[i].value)
    if i % 27 == 0 and i != 0 : 
      print "------+-------+------"
    if (i + 1) % 9 != 0 :
      if i % 9 in [2,5] : 
        print "{} |".format(cValue),
      else :
        print cValue ,
    else : 
      print cValue
  print divider , "\n"

def printposs(cells) :

  possList = []
  for row in range(27) : #iterates over rows to print
    if row % 9 == 0 and row != 0 : #dividers 
      print "{0}\n{0}".format("*" * 76)
    elif row % 3 == 0 and row != 0 : 
      print "{}{}{}{}{}".format("-" * 24 , "**" , "-" * 25 , "**" , "-" * 24) #end dividers 
    for cell in range(9) : #iterates over cells in the row
      for i in range((row % 3) * 3 ,((row % 3) * 3) + 3 ) : #iterates over the three slots for each cell in a row.
        if cells[cell + (row / 3 * 9)].value != 0 : 
          if row % 3 in [0,2] :
            possList.append("#") 
          elif i % 3 in [0,2] : 
            possList.append("#") 
          else :
            possList.append(cells[cell + (row / 3 * 9)].value)
        elif (i + 1) in cells[cell + (row / 3 * 9)].poss :
          possList.append(i + 1)
        else : 
          possList.append(" ")
    print" {} {} {} | {} {} {} | {} {} {}  **  {} {} {} | {} {} {} | {} {} {}  **  {} {} {} | {} {} {} | {} {} {}".format(*possList)
    possList = []

def printkey() :
  """prints out a key of cell indicies"""
  divider = "." * 30
  print divider
  for i in range(81) :
    if i % 27 == 0 and i != 0 : 
      print "---------+----------+---------"
    if (i + 1) % 9 != 0 :
      if i % 9 in [2,5] : 
        print "{1}{0} |".format(i , " " * (len(str(i)) % 2)),
      else :
        print "{1}{0}".format(i ," " * (len(str(i)) % 2)) ,
    else : 
      print "{1}{0}".format(i ," " * (len(str(i)) % 2))
  print divider , "\n"

def elim(cells, check) :
  """recieves the board and a check cell, eliminates possibles in check cell based on known values in the row, column, and square."""
  printStats = False
  #Is value known? 
  if check.value != 0 : 
    check.poss = [] 
  else :
    #row
    for i in range((cells.index(check) / 9) * 9 , (cells.index(check) / 9) * 9 + 9) :
      if cells[i].value in check.poss :
        check.poss.remove(cells[i].value)
    #column 
    start = cells.index(check) % 9 
    for i in range(9) :
      if cells[start + i * 9].value in check.poss :
        check.poss.remove(cells[start + i * 9].value)
    #square
    start = ((cells.index(check) / 3) * 3) % 9 + ((cells.index(check) / 27) * 27)
    for i in range(3) : 
      for j in range(3) : 
        if cells[start + (i * 9) + j].value in check.poss : 
          check.poss.remove(cells[start + (i * 9) + j].value)
    #Check if one poss is left
    if len(check.poss) == 1 :
      check.value = check.poss[0]
      if printStats :
        print "elimination......." , cells.index(check) 
      check.poss = []
  return cells

def unique(cells, check) : 
  '''Recieves the board and a check cell, checks if any possibles are unique to row, column, or box. Must be run AFTER elim(). '''
  printStats = False
  #Row
  if check.value == 0 : 
    for i in range(len(check.poss)) : #iterates the check procedure over posslibles for the cell 
      for ref in range((cells.index(check) / 9) * 9 , (cells.index(check) / 9) * 9 + 9) : #iterates over reference cells
        if check.poss[i] in cells[ref].poss and cells.index(check) != ref : #checks if ref cell contains poss, breaks if true, moving to next check.poss 
          break 
      else : 
        check.value = check.poss[i] 
        check.poss = [] 
        if printStats : 
          print "unique in Row....." , cells.index(check)
        break
  #Column
  if check.value == 0 :
    start = cells.index(check) % 9 
    for i in range(len(check.poss)) : #iterates the check procedure over posslibles for the cell 
      for ref in range(9) : #iterate over ref cells 
        if check.poss[i] in cells[start + ref * 9].poss and cells.index(check) != start + ref * 9 : 
          break 
      else : 
        check.value = check.poss[i] 
        check.poss = [] 
        if printStats : 
          print "unique in Column.." , cells.index(check)
        break
  #Square 
  if check.value == 0 : 
    start = ((cells.index(check) / 3) * 3) % 9 + ((cells.index(check) / 27) * 27)
    for i in range(len(check.poss)) : #iterates over possibles for cell
      dupFound = False
      for boxRow in range(3) : #iterates over ref cells
        if not dupFound : 
          for boxCol in range(3) : 
            if check.poss[i] in cells[start + (boxRow * 9) + boxCol].poss and cells.index(check) != start + (boxRow * 9) + boxCol : 
              dupFound = True 
              break
      if not dupFound : 
        check.value = check.poss[i] 
        check.poss = [] 
        if printStats : 
          print "unique in Square.." , cells.index(check)        
        break
  return cells

def subset(cells,check) : 
  '''Recieves a cell to check and the board, checks if other cells have identical poss lists in the row, column, or box, and the number of identical cells is equal to the number of possibilities. If so, remove those possibilities from the rest of the row, column, or box.'''
  printStats = False
  if check.value == 0 : 
    #Row 
    dups = [cells.index(check)]
    for ref in range((cells.index(check) / 9) * 9 , (cells.index(check) / 9) * 9 + 9) : #iterates over reference cells
      if check.poss == cells[ref].poss and cells.index(check) != ref : #checks if poss lists are equivalent
        dups.append(ref)
        if printStats : 
          print "Found subset row candidate, cell {}.".format(cells.index(check)) 
        if len(dups) == len(check.poss) : #checks if the number of duplicate cells is equal to number of possibles 
          if printStats : 
            print "***Found subset row, cell {}!".format(cells.index(check))
          for remove in range((cells.index(check) / 9) * 9 , (cells.index(check) / 9) * 9 + 9) : #iterates over cells to remove from 
            if remove not in dups : #if we're not in one of the duplicates
              for poss in check.poss :
                if poss in cells[remove].poss :
                  cells[remove].poss.remove(poss)
    #Column
    dups = [cells.index(check)] 
    start = cells.index(check) % 9 
    for ref in range(9) : #iterates over reference cells
      if check.poss == cells[start + ref * 9].poss and cells.index(check) != start + ref * 9 : # check if equiv
        dups.append(start + ref * 9)
        if printStats : 
          print "Found subset column candidate, cell {}.".format(cells.index(check)) 
        if len(dups) == len(check.poss) : #check if number of dups equals the number of possibles 
          if printStats : 
            print "***Found subset column, cell {}!".format(cells.index(check))
          for remove in range(9) : #iterates over cells to remove from 
            if (start + remove * 9)  not in dups : #if we're not in one of the duplicates
              for poss in check.poss :
                if poss in cells[start + remove * 9].poss :
                  cells[start + remove * 9].poss.remove(poss)
    #Square
    dups = [cells.index(check)] 
    start = ((cells.index(check) / 3) * 3) % 9 + ((cells.index(check) / 27) * 27)
    for boxRow in range(3) : #iterate over ref cells
      for boxCol in range(3) : 
        if check.poss == cells[start + (boxRow * 9) + boxCol].poss and cells.index(check) != start + (boxRow * 9) + boxCol : #check if equiv 
          dups.append(start + (boxRow * 9) + boxCol)
          if printStats : 
            print "Found subset square candidate, cell {}.".format(cells.index(check)) 
          if len(dups) == len(check.poss) : #check if number of dups equals the number of possibles 
            if printStats : 
              print "***Found subset square, cell {}!".format(cells.index(check))
            for boxRowRem in range(3) : #iterate over ref cells
              for boxColRem in range(3) : 
                if (start + (boxRowRem * 9) + boxColRem) not in dups : #if we're not in one of the duplicates
                  for poss in check.poss :
                    if poss in cells[start + (boxRowRem * 9) + boxColRem].poss :
                      cells[start + (boxRowRem * 9) + boxColRem].poss.remove(poss)

  return cells       

def solve(cells) : 
  printStats = False
  change = True
  passes = 0 
  while change : #iterates check process with elim() and unique() until either solved or can't solve
    if printStats : 
      print "Ran Loop {0}".format(passes)
    cellsHist = copy.deepcopy(cells) # create history of cells 
    for i in range(len(cells)) : #iterates elim(), unique(), and subset() over cells of the board. 
      elim(cells,cells[i])
      unique(cells,cells[i])
      subset(cells,cells[i])
    for j in range(len(cells)) : #check if cells is equal to its history, call guess() if so. 
      if cells[j].value != cellsHist[j].value or cells[j].poss != cellsHist[j].poss : 
        cells = guess(cells)
        break 
    else : 
      change = False 
    passes += 1 
    if printStats : 
      printboard(cells)
  for i in range(len(cells)) : #check if puzzle was solved 
    if cells[i].value == 0 : 
      print "Could not solve."
      printposs(cells) 
      break 
  else: 
    print "Solved!"
    checkpuzzle(cells) 
  return cells

def backgroundsolve(cells) : 
  ''' same as solve() without any printouts, gets called by guess()'''
  printStats = False
  change = True
  passes = 0 
  while change : #iterates check process with elim() and unique() until either solved or can't solve
    if printStats : 
      print "Ran Loop {0}".format(passes)
    cellsHist = copy.deepcopy(cells) # create history of cells 
    for i in range(len(cells)) : #iterates elim() and unique() over cells of the board. 
      elim(cells,cells[i])
      unique(cells,cells[i])
      subset(cells,cells[i])
    for j in range(len(cells)) : #check if cells is equal to its history, break while loop if so. 
      if cells[j].value != cellsHist[j].value : 
        break 
      elif cells[j].poss != cellsHist[j].poss : 
        break 
    else : 
      change = False 
    passes += 1 
    if printStats : 
      printboard(cells)
  return cells 

def checkpuzzle(cells) : 
  ''' checks the puzzle to make sure there were no errors in solving''' 
  noError = True 
  #Rows 
  for row in range(9) : 
    checkList = [] 
    for cell in range(9) : #Build checklist
      checkList.append(cells[(row * 9) + cell].value)
    for i in range(1,10) : 
      if i not in checkList : 
        print "ERROR: {} NOT IN ROW {}".format(i, row + 1)
        noError = False
  #Columns 
  for column in range(9) :
    checkList = []
    for cell in range(9) : #Build checklist
      checkList.append(cells[column + (cell * 9)].value)
    for i in range(1,10) : 
      if i not in checkList : 
        print "ERROR: {} NOT IN COLUMN {}".format(i, column + 1)
        noError = False
  #Squares 
  for square in range(9) :
    checkList = [] 
    for boxRow in range(3) :
      for boxColumn in range(3) :
        checkList.append(cells[(square / 3) * 27 + ((square % 3) * 3) + (boxRow * 9) + boxColumn].value)
    for i in range(1,10) : 
      if i not in checkList : 
        print "ERROR: {} NOT IN BOX {}".format(i, square + 1)
        noError = False
  #Print Results 
  if noError : 
    print "Check complete. No Errors."
  else : 
    print "Check complete."

def backgroundcheckpuzzle(cells) :
  ''' same as checkpuzzle() but without any printouts.''' 
  noError = True 
  #Rows 
  for row in range(9) : 
    checkList = [] 
    for cell in range(9) : #Build checklist
      checkList.append(cells[(row * 9) + cell].value)
    for i in range(1,10) : 
      if i not in checkList : 
        noError = False
  #Columns 
  for column in range(9) :
    checkList = []
    for cell in range(9) : #Build checklist
      checkList.append(cells[column + (cell * 9)].value)
    for i in range(1,10) : 
      if i not in checkList : 
        noError = False
  #Squares 
  for square in range(9) :
    checkList = [] 
    for boxRow in range(3) :
      for boxColumn in range(3) :
        checkList.append(cells[(square / 3) * 27 + ((square % 3) * 3) + (boxRow * 9) + boxColumn].value)
    for i in range(1,10) : 
      if i not in checkList : 
        noError = False
  return noError

def guess(cells) :
  '''Iterates over cells and selects each possibility and sees if that will solve the puzzle with backgroundsolve() and checks it with backgroundcheckpuzzle().'''
  continueCheck = True
  while continueCheck :
    for i in range(len(cells)) : 
      for j in range(len(cells[i].poss)) :
        cellsHist = copy.deepcopy(cells) 
        cells[i].value = cells[i].poss[j] 
        backgroundsolve(cells) 
        if backgroundcheckpuzzle(cells) : 
          continueCheck = False 
          break
        else : 
          cells = cellsHist
    else : 
      continueCheck = False 
  return cells

main()

This is what puzzle1.csv contains:

3,0,5,0,0,0,0,8,7,0,4,0,0,0,0,0,3,2,7,0,1,0,0,0,0,5,0,0,0,9,5,0,0,0,0,0,0,0,3,0,6,2,0,0,0,0,0,0,0,0,7,0,2,0,0,6,0,0,0,0,0,0,4,0,0,0,0,1,0,0,0,6,0,0,0,4,3,0,8,0,0

Answer 1

1. I'll go one step farther than @AndrewAu's suggestion. You dedicate a lot of code and time to iterating rows, columns, and squares. Since these are "fixed" for a cell, why not build some shared data structures and link to them from each cell?

   That is, in the cell object, create:

   cell.row = {set of cells, including this one, in the row}
   cell.col = {set of cells, including this one, in the col}
   cell.square = {set of cells, including this one, in the square}
   

   Those sets will be identical for 9 cells- each cell in the same col will have the same .col value, etc., and they're just lists of references to cells, so they should be space efficient.

   That said, you could then iterate over the members quickly, without computing anything.

2. You use lists for the possible values of a cell. Try using a set, it will make your code shorter since it supports .discard(elem) which doesn't require checking:

   def elim(cells, check):
       # ...
   
       for i in range((cells.index(check) / 9) * 9, (cells.index(check) / 9) * 9 + 9):
           if cells[i].value in check.poss:
               check.poss.remove(cells[i].value)
   

   Becomes:

       for other in check.row:
           check.poss.discard(other.value)
   

   And unique looks like:

   def unique(cells, check): 
       '''Recieves the board and a check cell, checks if any possibles
       are unique to row, column, or box. Must be run AFTER elim().
   
       '''
       printStats = False
   
       if not check.value:
           this_row = check.row - {check}    # set difference
   
           for p in check.poss:
               if not any(p in other.poss for other in this_row):
                   check.value = p
                   check.poss.clear()
                   if printStats : 
                       print "unique in Row....." , cells.index(check)
                   break
   

3. You need to go watch nedbat's "Loop Like a Native" presentation, all the way through! You are writing code like this:

   for i in range(len(check.poss)):
   

   This is automatically wrong in almost every case. If you want to iterate over the possibles, then iterate over them! Watch the talk, and then write:

   for p in check.poss:
   

   or write:

   for i, p in enumerate(check.poss):
   

   as appropriate.

Answer 2

Congratulations to the completion of your substantial project. It is really smart and brave for you to ask for feedback. I am going to tell you what is not so perfect about your code, after all, that's the whole point, right? But don't be discouraged, for you have done a decent job!

Let's begin with the high level algorithm:

The first thing I would like to point out is the usage on memory, in various places you make deep copies of all the cells. This is pretty convenient to do, but it also take up a lot of space. For the unique/elim/subset functions, you can simply return a flag if the board is changed, and save a copy in the solve function.

It might be difficult to remove the deepcopy in the guess function, and that's probably fine, as you might be making a lot of changes.

Try save some space, you should notice a performance change.

Then let's talk about the code:

The checkpuzzle function and the backgroundcheckpuzzle is almost identical, why don't you just parameterize it just like you did in unique?

A lot of the code have the structure of going through each of the row/column/squares. It looks like a lot of duplication to me. What if you abstract them into a concept called block, and just iterate through all blocks?

Last, and probably least, you made a few typos, 'recieve', 'posslibles' 'indicies', and I highly doubt the word 'possibles', although Wikipedia say it is a plural of an adjective.

Answer 3

In theory you should not even need elim at all, because subset should cover what it does plus more. ("If you have N empty squares in a group, and they all have only the same N possible values, then all other squares in the same group cannot have any of those same values.") The elim function should be the same thing as subset where N is restricted to 1.

There is also a more general version of unique that will cover what it does, that will allow you to solve harder puzzles and remove the unique function as redundant. ("If you have N empty squares in a group, and they are the only ones in that group that could have certain N possible values, then those squares cannot have any other values.")

I think there is no need to artificially restrict the order in which elim and unique (or their super-operations) run. It should be safe to execute them in any order, and sometimes it will take fewer steps to solve when run in a different order. I don't have a suggestion though for optimal recalculation order, because I never figured it out myself. But if you found that your solver breaks when you change the order in which rules are applied, that may be evidence of a bug in your implementation.

I don't know how many automated solvers use an equivalent of your guess function, but I never wrote one for my own solver. In most places I've seen, the "how to play" explanations of Sudoku stress "without guessing", to emphasize the logical deduction aspect. This implies that if you cannot make any logical deduction about the puzzle using static analysis alone, it is not a "fair puzzle". Although on the other hand, some puzzles published in news-stand books and online as high difficulty are not by that definition "fair puzzles" (and more than a few even have multiple valid solutions). If your solver stops without finding a solution to a puzzle given in a book on on the web, that doesn't automatically mean your solver is broken.

I guess it's a judgement call whether to have a guess function as part of the solver. But I believe it definitely should be a last resort if all static analysis fails to make progress at a given point. That policy will help performance as well as honor the spirit of the game. Instead of your existing while change loop, have two nested loops:

while change:
  while change:
    # current activity, but no call to guess(), update change variable
  if not change:
    # call to guess(), update change variable

Note that with this approach, as before, once you have guessed the solver may actually reach a contradiction in the puzzle state, where there are no possible values for a cell or multiple cells in a group with the same value. You haven't implemented back-tracking for your guesses, so this will remain a possibility. Your checkpuzzle routine will only stop execution one step away from this, it is not full-fledged guess backtracking.

Answer 4

Try writing it as a recursive solution - you will have a lot fewer lines. Define a function that takes the unsolved puzzle as a parameter, find one number that is a valid number for an empty cell and is the only valid number for it, update the puzzle, and then send it back to the original function.