# python-ai / src / sudoku / csp.py

 ``` 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 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105``` ```#!/usr/bin/env python from itertools import count class SolutionNotFound(Exception): def __str__(self): return "Solution not found." class MaxDepthExceeded(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): v = self.variable return v in m and m[v] != 0 class AllDiffConstraint(object): def __init__(self, variables): self.variables = variables def satisfied(self, m): vs = set() for v in self.variables: if not v in m: return False vs.add(m[v]) return len(vs) == len(self.variables) class CSPSolver(object): MAX_CHECKS = 1e7 def __init__(self, variables, domains, constraints): self.variables = variables self.domains = domains self.constraints = constraints def solved(self, m): for v in self.variables: if not v in m: return False for c in self.constraints: if not c.satisfied(m): return False return True def constraintsUnsatisfied(self, m): num = 0 for c in self.constraints: if not c.satisfied(m): num += 1 return num def solve(self): """Solves the CSP problem, returning the solution as a dict with variables as keys and domain members as values. Raises SolutionNotFound if no solution found or MaxDepthExceeded if solution not found after MAX_DEPTH expansions.""" (mapping, num) = self.solveWithCount() return mapping def solveWithCount(self): """Solves the CSP problem, returning the 2-tuple (mapping, exps). `mapping` is the solution as a dict with variables as keys and domain members as values. `exps` is the number of expansions required to find a solution. Raises SolutionNotFound if no solution found or MaxDepthExceeded if solution not found after MAX_DEPTH expansions.""" if len(self.constraints) == 0 and self.solved(dict()): return dict(), 0 for v in self.variables: if v not in self.domains or len(self.domains[v]) == 0: raise SolutionNotFound return self.searchSolution() def searchSolution(self): raise SolutionNotFound class BacktrackingSolver(CSPSolver): def __init__(self, *args, **kwargs): super(BacktrackingSolver, self).__init__(*args, **kwargs) def searchSolution(self): last_var = self.variables[-1] var = self.variables[0] mapping = {var: self.domains[var][0]} for exps in count(): if self.solved(mapping): return mapping, exps elif var == last_var: while mapping[var] == self.domains[var][-1]: del mapping[var] idx = self.variables.index(var) if idx == 0: raise SolutionNotFound var = self.variables[idx-1] last_val = mapping[var] val = self.domains[var][self.domains[var].index(last_val)+1] mapping[var] = val else: var = self.variables[self.variables.index(var)+1] if len(self.domains[var]) == 0: raise SolutionNotFound mapping[var] = self.domains[var][0] def getNextVar(self, remaining): for r in remaining: return r def getNextVal(self, remaining): for r in remaining: return r ```