Sonderblade

# -*- coding: utf-8 -*-# (C) Björn Lindqvist, Public Domainimport psycopsyco.full()class Problem(object):    def __init__(self):        varlist = list("ABCDEFGHIJKLMNOPQRS")        self.cons = []        self.cons.append((all_diff_constraint, varlist))        self.cons.append((sum_38_constraint, ['A', 'B', 'D']))        self.cons.append((sum_38_constraint, ['I', 'G', 'E', 'C']))        self.cons.append((sum_38_constraint, ['N', 'L', 'J', 'H', 'F']))        self.cons.append((sum_38_constraint, ['Q', 'O', 'M', 'K']))        self.cons.append((sum_38_constraint, ['S', 'R', 'P']))        self.cons.append((sum_38_constraint, ['A', 'C', 'F']))        self.cons.append((sum_38_constraint, ['B', 'E', 'H', 'K']))        self.cons.append((sum_38_constraint, ['D', 'G', 'J', 'M', 'P']))        self.cons.append((sum_38_constraint, ['I', 'L', 'O', 'R']))        self.cons.append((sum_38_constraint, ['N', 'Q', 'S']))        self.cons.append((sum_38_constraint, ['D', 'I', 'N']))        self.cons.append((sum_38_constraint, ['B', 'G', 'L', 'Q']))        self.cons.append((sum_38_constraint, ['A', 'E', 'J', 'O', 'S']))        self.cons.append((sum_38_constraint, ['C', 'H', 'M', 'R']))        self.cons.append((sum_38_constraint, ['F', 'K', 'P']))    def getSolution(self):        vconstraints = self._getArgs()        solver = RecursiveBacktrackingSolver(vconstraints)        return solver.getSolution()    def _getArgs(self):        vconstraints = dict((var, []) for var in "ABCDEFGHIJKLMNOPQRS")        for constraint, variables in self.cons:            for variable in variables:                vconstraints[variable].append((constraint, variables))        return vconstraints# ----------------------------------------------------------------------# Solvers# ----------------------------------------------------------------------class RecursiveBacktrackingSolver(object):    def __init__(self, vconstraints):        self.domain = range(1, 20)        self.vconstraints = vconstraints                self.sorted_vconstraints = []        for variable in "ABCDEFGHIJKLMNOPQRS":            value = -len(vconstraints[variable]), 19, variable            self.sorted_vconstraints.append(value)        self.sorted_vconstraints.sort()            def getSolution(self, assignments = {}):        for item in self.sorted_vconstraints:            if item[-1] not in assignments:                # Found an unassigned variable. Let's go.                break        else:            # No unassigned variables. We've got a solution.            return assignments                    variable = item[-1]        for value in self.domain:            assignments[variable] = value            for constraint, variables in self.vconstraints[variable]:                if not constraint(variables, assignments):                    # Value is not good.                    break            else:                # Value is good. Recurse and get next variable.                solve = self.getSolution(assignments)                if solve:                    return solve        del assignments[variable]        return None# ----------------------------------------------------------------------# Constraints# ----------------------------------------------------------------------def all_diff_constraint(variables, assignments):    seen = set()    for variable in "ABCDEFGHIJKLMNOPQRS":        value = assignments.get(variable, 0)        if value:            if value in seen:                return False            seen.add(value)    return True            def sum_38_constraint(variables, assignments):    sum = 0    missing = False    for variable in variables:        if variable in assignments:            sum += assignments[variable]        else:            missing = True    if sum > 38:        return False    if missing:        return sum <= 38    return sum == 38        if __name__ == "__main__":    problem = Problem()    print problem.getSolution()