Friday, January 13, 2006

Sudoku Solver in Python

A few months ago, my wife gave me a book with sudoku puzzles. After solving a couple by hand, I decided that it was much more fun to try and write a solver...

My first implementation was a quick hack, the code was brief and ugly with lots of index operations in a bad functional programming style, but it worked well. It used only solution-reduction algorithms, no brute force. As such not all sudoku puzzles could be solved, but the ones that could, were solved pretty fast. Satisfied with my little achievement I soon forgot about it...

Then, recently, I read this article on LinuxJournal. The program in article was unfinished (the third part has still to be published), but the code was much tidier than mine. I took some inspiration to rewrite my solver in a more pythonic way. After that I stumbled on the ASPN recipe, which gave me the idea of adding a brute force solver.

The result is a combination of analytic and brute force solvers that performs 2 or 3 orders of magnitude better than the ASPN code.

Enough talk, here it is:

#!/usr/bin/env python
# sudoku-solver version 3
# Some ideas ripped-off from:
# Pavol solver in
# Copyright 2005 Ago,
# But you are free to copy, reuse, modify and distribute the code as you see fit

from copy import deepcopy
class DeadEnd(Exception): pass

class Matrix:
    def __init__(self, input):
        self.rows = [[] for i in range(9)]
        self.cols  = [[] for i in range(9)]
        self.submatrices = [[] for i in range(9)]
        self.cells = [Cell(i,self) for i in range(81)]
        self.subdiagonals = [self.rows[i][j+i%3] for i in range(9) for j in [0,3,6]]
        input = [s not in '-*' and int(s) or 0 for s in input if s in '0123456789-*']
        for cell,val in zip(self.cells, input):
            if val: cell.setSolution(val)

    def solve(self): #Brute-force solver
        lensols=[(len(,c.index) for c in self.cells if not c.solved]
        if not lensols: return True
        unsolved = min(lensols)[1]
        solutions = list(self.cells[unsolved].solutions)
        for s in solutions:
            tmpmatrix = deepcopy(self)
                if tmpmatrix.solve():
                    return True
            except DeadEnd: pass

    def solveByReduction(self):
        while True:
            self.changed = False
            for c in self.cells: c.solve()
            for c in self.subdiagonals: c.skim()
            if not self.changed: break

    def update(self, m):
        self.rows, self.cols, self.submatrices, self.cells, self.subdiagonals=\
            m.rows, m.cols, m.submatrices, m.cells, m.subdiagonals

    def __str__(self):
        return "\n".join(str([c for c in row ])[1:-1] for row in self.rows)

class Cell:
    def __init__(self, index, matrix):
        self.solved = False
        self.matrix = matrix
        self.index = index
        self.row = matrix.rows[index/9]
        self.col = matrix.cols[index%9]
        self.submatrix = matrix.submatrices[((index/9)/3)*3+(index%9)/3]
        self.submatrix.append(self) = set(range(1,10))

    def solve(self):
        if self.solved: return
        if len( == 1:
            sol = set()
            for cells in [self.row, self.col, self.submatrix]:
                otherSolutions = self.cells2sols(cells, self)
                sol |= ( - otherSolutions)
            if len(sol) > 1: raise DeadEnd()
            if sol: self.setSolution(sol.pop())
    def skim(self):
        submatrix = set(self.submatrix)
        for r in  (set(self.row), set(self.col)):
            subset1 = submatrix - r
            subset2 = r - submatrix
            solsNotIn1 = set(range(1,10)) - self.cells2sols(subset2)
            solsNotIn2 = set(range(1,10)) - self.cells2sols(subset1)
            for c in subset1: c.delSolutions(solsNotIn1)
            for c in subset2: c.delSolutions(solsNotIn2)
    def setSolution(self, val):
        self.solved = True = set((val,))
        self.matrix.changed = True
        for other in self.row+self.col+self.submatrix:
            if other is self: continue
            if == raise DeadEnd()
    def delSolutions(self, val):
        if not self.solved and val &
   -= val
            self.matrix.changed = True
            if not raise DeadEnd()
    def __repr__(self):
        return str(self.solved and list([0] or list(

    def cells2sols(cells, exclude=None):
        return set(s for c in cells for s in if c is not exclude)

if __name__ == "__main__":
    input ='''
    matrix = Matrix(input)
    print matrix

1 comment:

Camelo said...

I'm just starting to study python, and I like Sudokus a lot... I think I'll use you program as "case study"! :)