From 12ea18a615938b6df534ff434df273472de442ab Mon Sep 17 00:00:00 2001 From: Geoff Hill Date: Sun, 15 Apr 2012 12:33:17 -0500 Subject: [PATCH] start separate csp solvers to simplify sudoku --- src/sudoku/csp.py | 39 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 39 insertions(+) create mode 100644 src/sudoku/csp.py diff --git a/src/sudoku/csp.py b/src/sudoku/csp.py new file mode 100644 index 0000000..63fdb26 --- /dev/null +++ b/src/sudoku/csp.py @@ -0,0 +1,39 @@ +#!/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 -- 2.1.1