// (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);
}
}
}