Source

python-ai / src / sudoku / csp.py

#!/usr/bin/env python

class SolutionNotFound(Exception):
    def __str__(self):
        return "Solution not found."

class MaxSolutionDepthExceeded(Exception):
    def __init__(self, depth):
        self.depth = depth
    def __str__(self):
        return "Max solution depth exceeded %d." % (self.depth,)

class NotZeroConstraint(object):
    def __init__(self, variable):
        self.variable = variable
    def satisfied(self, m):
        return m[self.variable] != 0

class AllDiffConstraint(object):
    def __init__(self, variables):
        self.variables = variables
    def satisfied(self, m):
        vs = set()
        for v in self.variables:
            vs.add(m[v])
        return len(vs) == len(self.variables)

class CSPSolver(object):
    MAX_CHECKS = 1e7

    def __init__(self, numVariables, domains, constraints):
        self.numVariables = numVariables
        self.domains = domains
        self.constraints = constraints

    def solved(self, m):
        for c in self.constraints:
            if not c.satisfied(m): return False
        return True