Sudoku Solver in Python

A great way to learn a new language is to simulate a game using it. Implementing a solution for something that seems so simple as a black jack game or texas holdem usually presents enough of a challenge to at least get the feeling of the language.

Sudoku seemed like interesting puzzle to me when stacked in a NYC subway wagon I was watching the guy next to me scribbling numbers on his paper trying to solve it. It got my attention, but I admit that after solving a couple of them later that night, I quickly lost my interest to it. I guess us developers we are more interested in general solutions as opposed to repeating the same thinking process over and over solving the same problem with different parameters.

So, it was more natural for me to write a simple Sudoku Solver in Python program something that this wonderful language allowed me to implement a relatively brutal solution very quickly in a matter of an hour or two! If I have time I will re-implement it using a more sophisticated algorithm but even this one seems to be reasonably fast…

If you are interested here you can see the code that you can run in any system supporting python (for ms-windows systems you might need to commend out the very first line)…

Here you can see a web interface around this code that is calling the python code from a wordpress / php environment

Please let me know if you find any bug or you have a question about the algorithm…

#!/usr/bin/python
#!/usr/bin/python

# sudoku_solver.py

'''
You can test the module using the following command:

nosetests -v --with-doctest sudoku_solver.py

>>> s = Sudoku()
>>> test_values = ( (0,2,5), (0,3,3), (1,0,8), (1,7,2), (2,1,7), (2,4,1), (2,6,5), (3,0,4), (3,5,5), (3,6,3), (4,1,1), (4,4,7), (4,8,6), (5,2,3), (5,3,2), (5,7,8), (6,1,6), (6,3,5), (6,8,9), (7,2,4), (7,7,3), (8,5,9), (8,6,7))
>>> for v in test_values: s.set_at(*v)
>>> s.solve()
True
>>> str(s)
'145327698839654127672918543496185372218473956753296481367542819984761235521839764'

'''

class Cell:
'''
Represents a single cell of the sudoku matrix
Holds the selected value for the cell and a list
with all the possible values it can accept at any time
based in the groups that it belongs
'''
def __init__(self):
self.selection = None
self.rewind()

def rewind(self):
self.acceptable = [] if self.selection else range(1,10)

class Sudoku:
'''
Represents the sudoko grid, mainting a list of all the cells
allowing the user to set and get their values and to
solve it by calling the corresponding function.
'''

# groups :
#
# All the possible groups of values that need
# to contain the values from 1 to 9 are defined
# in the class level variable groups. Note that based
# in how the game is played, we are going to have exactly
# 27 groups:
#
# 9 groups for each horizontal line
#
# 9 groups for each vertical line
#
# 9 groups for each 3X3 box

groups = [
[0, 1, 2, 3, 4, 5, 6, 7, 8],
[9, 10, 11, 12, 13, 14, 15, 16, 17],
[18, 19, 20, 21, 22, 23, 24, 25, 26],
[27, 28, 29, 30, 31, 32, 33, 34, 35],
[36, 37, 38, 39, 40, 41, 42, 43, 44],
[45, 46, 47, 48, 49, 50, 51, 52, 53],
[54, 55, 56, 57, 58, 59, 60, 61, 62],
[63, 64, 65, 66, 67, 68, 69, 70, 71],
[72, 73, 74, 75, 76, 77, 78, 79, 80],
[0, 9, 18, 27, 36, 45, 54, 63, 72],
[1, 10, 19, 28, 37, 46, 55, 64, 73],
[2, 11, 20, 29, 38, 47, 56, 65, 74],
[3, 12, 21, 30, 39, 48, 57, 66, 75],
[4, 13, 22, 31, 40, 49, 58, 67, 76],
[5, 14, 23, 32, 41, 50, 59, 68, 77],
[6, 15, 24, 33, 42, 51, 60, 69, 78],
[7, 16, 25, 34, 43, 52, 61, 70, 79],
[8, 17, 26, 35, 44, 53, 62, 71, 80],
[0, 1, 2, 9, 10, 11, 18, 19, 20],
[3, 4, 5, 12, 13, 14, 21, 22, 23],
[6, 7, 8, 15, 16, 17, 24, 25, 26],
[27, 28, 29, 36, 37, 38, 45, 46, 47],
[30, 31, 32, 39, 40, 41, 48, 49, 50],
[33, 34, 35, 42, 43, 44, 51, 52, 53],
[54, 55, 56, 63, 64, 65, 72, 73, 74],
[57, 58, 59, 66, 67, 68, 75, 76, 77],
[60, 61, 62, 69, 70, 71, 78, 79, 80]
]

ROWS , COLS = 9, 9

def __init__(self):
''' Initialized the list of available cells '''
self.cells = [ Cell() for i in range(self.ROWS * self.COLS)]

def process_group(self, group):
'''
For the passed in group it goes through all the cells
removing the acceptable values for it
'''
group_cells = [ self.cells[i] for i in group ]
selected_numbers = [ cell.selection for cell in group_cells if cell.selection ]
for cell in [ c for c in group_cells if c.selection is None]:
for n in selected_numbers:
if n in cell.acceptable:
cell.acceptable.remove(n)

def row_col_to_flat_index(self,row,col):
'''Converts a row - col to its corresponding flat list index '''
return (row % Sudoku.ROWS) * Sudoku.ROWS + col

def set_at(self,row,col,n):
'''Sets the value of the cell at row - col to n'''
cell = self.cells[self.row_col_to_flat_index(row,col)]
cell.selection = n

def get_at(self,row,col):
'''Gets the value of the cell at row - col'''
cell = self.cells[self.row_col_to_flat_index(row,col)]
return cell.selection

def prepare_cells(self):
'''
Goes through all the cells assigning the accepted values
the trick is that if a cell is already assigned with a value
it is assigned to no accepted values at all.
You have to understand that this method will be called in a
recourive manner until a solution is found
'''
map( lambda cell : cell.rewind(), self.cells)
map(self.process_group, Sudoku.groups)

def found_solution(self):
'''Returns true if the sudoku was solved'''
return len([ cell for cell in self.cells if cell.selection is None ]) == 0

def solve(self):
''' Will try to solve the sudoku return true or false'''
if self.found_solution():
return True

self.prepare_cells()

if len([ c for c in self.cells if not c.selection and len(c.acceptable) == 0 ] ) > 0:
return False

unassigned = [ c for c in self.cells if not c.selection]
cell_with_min_choices = sorted(unassigned,key=lambda v: len(v.acceptable))[0]

for n in cell_with_min_choices.acceptable:
cell_with_min_choices.selection = n
if self.solve():
return True

cell_with_min_choices.selection = None
return False

def print_it(self):
'''Nice printout to the console'''
for row in range(Sudoku.ROWS):
for col in range(Sudoku.COLS):
print self.get_at(row,col), ' ',
print

def __str__(self):
s = []
for row in range(Sudoku.ROWS):
for col in range(Sudoku.COLS):
s.append(str(self.get_at(row,col)))
return ''.join(s)

Be the first to comment

Leave a Reply

Your email address will not be published.


*