Sudoku solver (Python recipe) by Artur de Sousa Rocha

ActiveState Code (http://code.activestate.com/recipes/473844/)

#!/usr/bin/env python

"""Sudoku solver

usage: python sudoku.py <file> [<depth>]

The input file should contain exactly 81 digits, with emtpy fields marked
with 0. Optionally, dots (.) may be used for empty fields if better
readability is required. All other characters are discarded.

The default guessing depth is 2.

"""


import pprint
from itertools import chain


def parseString(text):
    s = text.replace('.', '0')
    s = [int(x) for x in s if x.isdigit()]
    s = [s[i:i+9] for i in range(0, 81, 9)]
    return s


def parse(name):
    f = open(name)
    s = f.read()
    f.close()
    return parseString(s)


class NotSolvable(Exception):

    """Not solvable"""

    pass


class IncorrectSolution(Exception):
    
    """Incorrect solution"""

    pass


class Done(Exception):

    """Done!"""

    pass


# These constants are speed optimizations for use in loops
MASK9 = set(range(1, 10))
NINE = tuple(range(9))
THREE = tuple(range(3))


def try_cross_and_region(matrix, depth=0):
    """Fill cells unambiguously determined by their lines and regions.
    
    For every empty cell, find the values of known digits in its row, column,
    and region. If there is exactly one digit left, it is the value of the
    cell. If there are more and if search depth is non-zero, try solving the
    puzzle for each of the values.
    
    """
    result = False
    for col in NINE:
        yexist = set(m[col] for m in matrix)
        rcol = col // 3
        rcol3 = 3 * rcol
        rcol3p3 = rcol3 + 3
        for row in NINE:
            if not matrix[row][col]:
                xexist = set(matrix[row])
                rrow = row // 3
                rrow3 = 3 * rrow
                region = [matrix[rrow3+i][rcol3:rcol3p3] for i in THREE]
                rexist = set(chain(*region))
                missing = MASK9 - xexist - yexist - rexist
                size = len(missing)
                if size == 1:
                    elem = list(missing)[0]
                    matrix[row][col] = elem
                    yexist.add(elem)  # Speed optimization, see outer loop
                    result = True
                elif size == 0:
                    raise NotSolvable()
                elif size < 4 and depth > 0:
                    # The size limit was established by experimentation.
                    hypothesize(matrix, row, col, missing, depth-1)
    return result


def try_adjacent_lines(matrix):
    """Fill cells unambiguously determined by same-region lines.
    
    For every empty cell, find the values of known digits in the lines passing
    through the same region. For the cell's line, the other two values in the
    region should be known. For the remaining two lines, all digits in the
    other two regions should be known. There should be exactly one value
    happening twice on the other lines and not at all on the current line.
    It is the value of the current cell.

    If the above failed in one direction, try the other.

    If both horizontal and vertical searches failed for a given cell but all
    24 other-region values are known, there should be exactly one value
    happening 4 times (each for one of the other regions checked). It is the
    value of the current cell.
    
    """
    result = False
    for col in NINE:
        rcol = col // 3
        rcol3 = 3 * rcol
        rcol3p3 = rcol3 + 3
        othercolidxs = (rcol3 + (col+1)%3, rcol3 + (col+2)%3)
        for row in NINE:
            if not matrix[row][col]:
                rrow = row // 3
                rrow3 = 3 * rrow
                otherrows = (rrow3 + (row+1)%3, rrow3 + (row+2)%3)
                otherrows = [matrix[orow] for orow in otherrows]
                othercols = [[m[ocol] for m in matrix]
                             for ocol in othercolidxs]
                othercross = []  # Container for other-region known values
                if _check_other_lines2(matrix, rcol, row, col, matrix[row],
                                       otherrows, othercross):
                    result = True
                elif _check_other_lines2(matrix, rcol, row, col,
                                         [m[col] for m in matrix],
                                         othercols, othercross):
                    result = True
                elif len(othercross) == 24:
                    fours = [i for i in MASK9 if othercross.count(i) == 4]
                    if fours:
                        matrix[row][col] = fours[0]
                        result = True
    return result


def _check_other_lines2(matrix, ridx, row, col, line, otherlines, othercross):
    """Helper function for try_adjacent_lines().

    Check the values in one direction. As an artifact, known digit values
    from the lines are collected into othercross.
    
    """
    ridx3 = 3 * ridx
    ridx3p3 = ridx3 + 3
    line = line[ridx3:ridx3p3]
    if line.count(0) != 1:
        return False
    allfields = []
    for other in otherlines:
        other = list(other)
        del other[ridx3:ridx3p3]
        allfields += other
    if allfields.count(0):
        return False
    othercross += allfields
    twos = set(i for i in MASK9 if allfields.count(i) == 2)
    twos -= set(line)
    if len(twos) == 1:
        elem = list(twos)[0]
        if elem not in line:
            matrix[row][col] = elem
            return True
    return False


# Speed optimization in for loop
RLOCATIONS = set((row, col) for row in THREE for col in THREE)


def try_masking(matrix):
    """Fill cells that remain alone after "masking" by other cells.

    For each digit value, "stamp out" the puzzle to see which regions have
    empty cells that could potentially still be filled with that value. For
    regions with single cells left, fill those cells with the value.
    
    Known problems:
    This function causes a 'Bad call' exception in the profile module
    (see http://www.python.org/sf/1117670) in some Python installations.
    
    """
    result = False
    for digit in MASK9:
        locations = set(RLOCATIONS)
        matrix2 = [list(m) for m in matrix]
        for row in NINE:
            try:
                idx = matrix2[row].index(digit)
            except ValueError:
                idx = -1
            else:
                matrix2[row] = [-1 for col in NINE]
                for row2 in NINE:
                    matrix2[row2][idx] = -1
                locations.discard((row//3, idx//3))
        for rrow, rcol in locations:
            rcol3 = 3 * rcol
            rcol3p3 = rcol3 + 3
            rrow3 = 3 * rrow
            region2 = (matrix2[rrow3+i][rcol3:rcol3p3] for i in THREE)
            region2 = [x for x in chain(*region2)]
            if region2.count(0) == 1:
                idx = region2.index(0)
                row = rrow3 + idx // 3
                col = rcol3 + idx % 3
                matrix[row][col] = digit
                result = True
    return result


def hypothesize(matrix, row, col, values, depth):
    """Try further search with the specified cell equal to each of values."""
    for x in values:
        matrix2 = [list(m) for m in matrix]
        matrix2[row][col] = x
        try:
            solve(matrix2, depth)
        except (NotSolvable, IncorrectSolution):
            pass


def check_done(matrix):
    if 0 in chain(*matrix):
        return False
    for row in matrix:
        if len(set(row)) < 9:
            raise IncorrectSolution()
    for col in range(9):
        col = set(m[col] for m in matrix)
        if len(col) < 9:
            raise IncorrectSolution()
    for rrow in range(3):
        for rcol in range(3):
            region = [matrix[3*rrow+i][3*rcol:3*(rcol+1)] for i in range(3)]
            if len(set(chain(*region))) < 9:
                raise IncorrectSolution()
    return True


def solve(matrix, depth=2):
    while try_cross_and_region(matrix):
        pass
    if check_done(matrix):
        pprint.pprint(matrix)
        raise Done()
    
    while try_adjacent_lines(matrix):
        pass
    if check_done(matrix):
        pprint.pprint(matrix)
        raise Done()
    
    while try_masking(matrix):
        pass
    if check_done(matrix):
        pprint.pprint(matrix)
        raise Done()
    
    while try_cross_and_region(matrix, depth=depth):
        pass
    if check_done(matrix):
        pprint.pprint(matrix)
        raise Done()


if __name__ == "__main__":
    import sys
    matrix = parse(sys.argv[1])
    depth = 2
    if len(sys.argv) > 2:
        depth = int(sys.argv[2])
    try:
        solve(matrix, depth)
        print "Failed, this is all I could fill in:"
        pprint.pprint(matrix)
    except Done:
        print "Done!"
    except NotSolvable:
        print "Not solvalbe, this is how I filled it in:"
        pprint.pprint(matrix)
    import os
    utime, stime, cutime, cstime, elapsed = os.times()
    print "cputime=%s" % (utime + stime)

# vim:et:ai:sw=4