# -*- coding: utf-8 -*-
# (C) Björn Lindqvist, Public Domain
import psyco
psyco.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()