// (C) Bjrn Lindqvist, Public Domain

using System;
using System.Collections.Generic;

class AssignmentsMap : Dictionary<string, int>
{ 
}

class VariableConstraintsMap : Dictionary<string, List<Constraint>>
{
}

class OrderedVariablePair : IComparable
{
    public int order;
    public string variable;

    public OrderedVariablePair(int order, string variable)
    {
        this.order = order;
        this.variable = variable;
    }

    public int CompareTo(object obj)
    {
        OrderedVariablePair other = (OrderedVariablePair)obj;
        if (this.order > other.order)
            return 1;
        else if (this.order < other.order)
            return -1;
        return 0;
    }
}

abstract class Constraint
{
    protected string[] variables;
    public abstract bool Check(AssignmentsMap assignments);
    public string[] GetVariables()
    {
        return variables;
    }
}

class SumEqualsConstraint : Constraint
{
    int sum;
    
    public SumEqualsConstraint(string[] variables, int sum)
    {
        this.variables = variables;
        this.sum = sum;
    }

    public override bool Check(AssignmentsMap assignments)
    {
        int sum = 0;
        bool missing = false;
        foreach (string var in this.variables)
        {
            if (assignments.ContainsKey(var))
                sum += assignments[var];
            else
                missing = true;
        }
        if (sum > this.sum)
            return false;
        if (missing)
            return sum <= this.sum;
        return sum == this.sum;
    }
}

class AllDifferentConstraint : Constraint
{
    public AllDifferentConstraint(string[] variables)
    {
        this.variables = variables;
    }

    public override bool Check(AssignmentsMap assignments)
    {
        Dictionary<int, bool> seenValues = new Dictionary<int, bool>();
        foreach (string var in this.variables)
        {
            if (assignments.ContainsKey(var))
            {
                int value = assignments[var];
                if (seenValues.ContainsKey(value))
                    // The value is assigned to two or more variables.
                    return false;
                seenValues[value] = true;
            }
        }
        return true;
    }
}

class ProblemDefinition
{
    protected int[] valueDomain;
    protected string[] allVariables;
    protected Constraint[] constraints;
    protected VariableConstraintsMap variableConstraints;

    public VariableConstraintsMap GetVariableConstraints()
    {
        VariableConstraintsMap map = new VariableConstraintsMap();
        foreach (string var in this.allVariables)
            map[var] = new List<Constraint>();
        
        foreach (Constraint c in this.constraints)
            foreach (string var in c.GetVariables())
                map[var].Add(c);
        
        return map;
    }

    public AssignmentsMap Solve()
    {
        VariableConstraintsMap vconstraints = this.GetVariableConstraints();
        AssignmentsMap assignments = new AssignmentsMap();

        // Sort the vconstraints
        List<OrderedVariablePair> sortedVConstraints =
            new List<OrderedVariablePair>();

        foreach (string var in this.allVariables)
        {
            int value = -vconstraints[var].Count;
            sortedVConstraints.Add(new OrderedVariablePair(value, var));
        }

        sortedVConstraints.Sort();
        

        return this.SolveRecursive(assignments,
                                   vconstraints,
                                   sortedVConstraints);
    }

    string FindFirstUnassignedVariable(
        AssignmentsMap assignments,
        List<OrderedVariablePair> sortedVConstraints)
    {
        foreach (OrderedVariablePair pair in sortedVConstraints)
            if (!assignments.ContainsKey(pair.variable))
            {
                //Console.WriteLine(pair.order);
                return pair.variable;
            }
        // No unassigned variable found
        return null;
    }

    protected bool CheckConstraints(List<Constraint> vconstraints,
                                    AssignmentsMap assignments)
    {
        foreach (Constraint c in vconstraints)
            if (!c.Check(assignments))
                return false;
        return true;
    }

    public AssignmentsMap SolveRecursive(
        
        AssignmentsMap assignments,
        VariableConstraintsMap vconstraints,
        List<OrderedVariablePair> sortedVConstraints)
        
    {
        string var = this.FindFirstUnassignedVariable(
            assignments, sortedVConstraints);

        if (var == null)
        {
            Console.WriteLine("Solution is complete");
            // No unassigned variable means the solution is complete.
            return assignments;
        }

        foreach (int value in this.valueDomain)
        {
            assignments[var] = value;
            if (this.CheckConstraints(vconstraints[var], assignments))
            {
                // Value fits, recurse and get next variable.
                AssignmentsMap solve = this.SolveRecursive(
                    assignments, vconstraints, sortedVConstraints);
                if (solve != null)
                    return solve;
            }
        }
        assignments.Remove(var);
        return null;
    }
}

class HiveProblem : ProblemDefinition
{
    public HiveProblem()
    {
        this.valueDomain = new int[]{
            1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
            11, 12, 13, 14, 15, 16, 17, 18, 19};
        this.allVariables = new string[]{
            "A", "B", "C", "D", "E", "F", "G", "H", "I", "J",
            "K", "L", "M", "N", "O", "P", "Q", "R", "S"};
        this.constraints = new Constraint[]{
            new AllDifferentConstraint(this.allVariables),
            
            new SumEqualsConstraint(new string[]{"A", "B", "D"}, 38),
            new SumEqualsConstraint(new string[]{"I", "G", "E", "C"}, 38),
            new SumEqualsConstraint(new string[]{"N", "L", "J", "H", "F"}, 38),
            new SumEqualsConstraint(new string[]{"Q", "O", "M", "K"}, 38),
            new SumEqualsConstraint(new string[]{"S", "R", "P"}, 38),

            new SumEqualsConstraint(new string[]{"A", "C", "F"}, 38),
            new SumEqualsConstraint(new string[]{"B", "E", "H", "K"}, 38),
            new SumEqualsConstraint(new string[]{"D", "G", "J", "M", "P"}, 38),
            new SumEqualsConstraint(new string[]{"I", "L", "O", "R"}, 38),
            new SumEqualsConstraint(new string[]{"N", "Q", "S"}, 38),

            new SumEqualsConstraint(new string[]{"D", "I", "N"}, 38),
            new SumEqualsConstraint(new string[]{"B", "G", "L", "Q"}, 38),
             new SumEqualsConstraint(new string[]{"A", "E", "J", "O", "S"}, 38),
//             new SumEqualsConstraint(new string[]{"C", "H", "M", "R"}, 38),
//             new SumEqualsConstraint(new string[]{"F", "K", "P"}, 38)
        };
    }
}

class HiveSolver
{
    static string desc =
@"Let the value of each hex in the hive be represented by a variable A..S,
then the following equations hold:

    A + B + D = 38
    I + G + E + C = 38
    N + L + J + H + F = 38
    Q + O + M + K = 38
    S + R + P = 38

    A + C + F = 38
    B + E + H + K = 38
    D + G + J + M + P = 38
    I + L + O + R = 38
    N + Q + S = 38

    D + I + N = 38
    B + G + L + Q = 38
    A + E + J + O + S = 38
    C + H + M + R = 38
    F + K + P = 38

And because each variable must be unique:

    A != B != C != D .. != S

And all variables are in the range 1..19. This can be represented
using 16 constraints and limiting all variables to that range.
";

    static void WriteExplanation()
    {
        Console.WriteLine("Solving the hive problem!");
        Console.WriteLine();
        Console.WriteLine(HiveSolver.desc);
    }

    static void Main()
    {
        HiveSolver.WriteExplanation();

        HiveProblem problem = new HiveProblem();
        AssignmentsMap solution = problem.Solve();

        if (solution != null)
        {
            foreach (KeyValuePair<string, int> pair in solution)
                Console.WriteLine(pair.Key + " = " + pair.Value);
        }
    }
}