# Sudoku Solver in Python

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 :
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
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


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:


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.

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.

• "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?
– Mast
Jan 8 '18 at 12:02
• Keep a counter, trying to count how many times cells.deepcopy() is called, then you will understand what I say. Jan 9 '18 at 7:13

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.

• 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. Jan 9 '18 at 4:42

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.

• 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. Jan 9 '18 at 4:44
• True, but recursion is still a way to go. Jan 9 '18 at 14:42