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

• MPA: Apart from the suggestions given in the other replies, you could find some inspiration in looking at the absolute bare minimum sudoku solver.

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.

• Mast: "Try save some space, you should notice a performance change." What kind of space are you talking about here? It's not necessarily true when put as a blanket statement like that. If the alternative is re-reading the data every time from file, that's not exactly better. So what do you propose?
• Andrew Au: Keep a counter, trying to count how many times cells.deepcopy() is called, then you will understand what I say.

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.

• Ross Millikan: The guess question is a philosophical one, or a spec on the solver. I wrote a solver that just checked whether there were any cells that had only one possibility considering the rows, columns, and blocks. If that failed, it guessed the first possibility and tried to solve the problem. It solved puzzles "instantly" and required rather little programmer effort. If we had a billion puzzles to solve it would clearly be the wrong approach, but I had about 50.

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.

• Ross Millikan: This won't solve most Sudokus you see. You will get blocked with all empty cells having more than one possibility. Incorporating a guess function and handling failure makes this work. Just keep guessing until you find a solution.
• postoronnim: True, but recursion is still a way to go.