Constraint Programming powinien to rozwiązać.
Edycja 2: poniższe rozwiązanie jest na 98% błędne, bo nie ma warunku na zgodność koloru i figury (potraktowałem je niezależnie). Jak kiedyś będę miał czas, to je dodam, niemniej samo podejście ILP spokojnie da radę z tym zadaniem.
Edycja: odpaliłem w ILP, rozwiązało się w 10 minut. Jeżeli jesteś zainteresowany rozwiązaniem (i przy okazji sprawdzeniem poprawności, bo tutaj zbyt leniwy byłem), to jest ono poniżej.
Legenda:
Para liter oznacza komórkę. Pierwsza litera to kształt (O - okrąg (koło w Twojej nomenklaturze), K - kwadrat, T - trójkąt, P - prostokąt), druga litera oznacza kolor (Z - zielony, N - niebieski, C - czerwony, P - pomarańczowy (żółty w Twojej nomenklaturze)).
KN OZ OP KP KZ PP TN TC OP ON TP KP TN OZ OP
TN OP OP KP OC PP KZ KC PP KN KP TP PN KN TZ
KN OP OC TP OC TP OZ KC TN TN KP KP PN TN KZ
PN OP OC PP OC PP TZ TC TN TZ KC OP TP TN KZ
PN OZ OC KP OZ KZ PN KP KN TZ OC KP KP OP OZ
KN KZ PC PZ OZ KZ TN KP PN OZ PC KP OP KP OZ
OP OZ OC PZ TZ KZ TN TP KZ OP PP OP KP OP TP
OP OP PC OZ KZ KZ KN KP TZ KP TP TC OC TP TP
OP OP PC TZ KZ TZ KN KN KZ TP TP TC TC KP PP
KC PP OZ KP KZ OZ OP PN TZ PP KZ TC OC KP TP
OC OC OZ PP TP OZ KP ON OC TP TZ TN TP PZ PN
OC OC OZ KP PP TN OP ON TC KP OZ ON KP KZ KN
OZ OC OC PP TP ON OZ OP KC OP KN ON KP KZ KN
OZ OC KC PP KN ON OZ KP TP TP ON PC KP KP TP
KZ TN KC OZ TN PN TZ TP KP KZ PN KC KP OP PP
OZ ON KZ OZ TN PP PC OP KP KZ KN KC OC KP TP
TZ PN KZ OZ KP OP KC OZ PP OZ TZ KC OC KZ PZ
OZ TN OZ TZ KP OP OC PZ TC OZ OZ TC PC PZ KZ
OZ KP KC KZ KP TZ KC PZ TC PZ KZ PN ON TZ KZ
OZ TP TC KZ PP KZ PP TP TC PZ TZ KN PN TC KZ
PZ OP PC OZ KC TZ TP KP OC KN TZ TN KN TC OZ
PZ KP KC OZ OC KC PP PP TZ TN TZ PZ KZ KC OC
OZ PP KC KZ KC OC PN TZ PZ TN OZ PZ KZ PC KC
OZ PN ON KZ KP OC TN TZ KZ TN KZ PZ TZ PN OC
PN PN TN TZ OP TC ON TZ OC TC TZ KC TZ ON TP
KN ON KN KC OP PC KN OC KC PC TC OC KN KN KP
ON PP PC PC PC KC TP TC OC PC OC OC PN KN KP
OZ KP TC KC TC KN OP PC PP KC PC KC TN PP KC
OZ OP OC OZ PC KN KP TC TP TP PP KN KZ OP KC
TZ KP KC OZ PC PN KP TP OP KP TP KN KZ TP PC
A jeżeli interesuje Cię kod (chociaż bardziej zostawiam go jako kopię zapasową), to jest poniżej - C# z użyciem biblioteki CplexMilpSolver (autopromocja: jestem jej autorem):
public static void Start() {
var solver = new CplexMilpSolver(10);
int width = 15;
int height = 30;
var figures = new [] {
new [] { 50, 20, 40, 15 },
new [] { 30, 20, 30, 60 },
new [] { 30, 25, 30, 20 },
new [] { 15, 20, 5, 40 }
};
var colorVariables = Enumerable.Range(0, width).Select(x => Enumerable.Range(0, height).Select(y => solver.Create(string.Format("color_{0}_{1}", x, y), Domain.PositiveOrZeroInteger)).ToArray()).ToArray();
var shapeVariables = Enumerable.Range(0, width).Select(x => Enumerable.Range(0, height).Select(y => solver.Create(string.Format("color_{0}_{1}", x, y), Domain.PositiveOrZeroInteger)).ToArray()).ToArray();
for(int x = 0;x<width;++x) {
for(int y = 0;y<height;++y) {
colorVariables[x][y].Set(ConstraintType.GreaterOrEqual, solver.FromConstant(1)).Set(ConstraintType.LessOrEqual, solver.FromConstant(4));
shapeVariables[x][y].Set(ConstraintType.GreaterOrEqual, solver.FromConstant(1)).Set(ConstraintType.LessOrEqual, solver.FromConstant(4));
}
}
var colorMap = new Dictionary<int, string> {
{
1, "Z" },
{
2, "N" },
{
3, "C" },
{
4, "P" }
};
var shapeMap = new Dictionary<int, string> {
{
1, "O" },
{
2, "K" },
{
3, "T" },
{
4, "P" }
};
var shapesSums = Enumerable.Range(1, 4).Select(shape => Enumerable.Range(0, width).Select(x => {
return Enumerable.Range(0, height).Select(y => shapeVariables[x][y].Operation(OperationType.IsEqual, solver.FromConstant(shape)))
.Aggregate(solver.FromConstant(0), (previous, next) => previous.Operation(OperationType.Addition, next));
}).ToArray()).ToArray();
var colorSums = Enumerable.Range(1, 4).Select(color => {
return Enumerable.Range(0, width)
.SelectMany(x => Enumerable.Range(0, height)
.Select(y => colorVariables[x][y].Operation(OperationType.IsEqual, solver.FromConstant(color)))
).Aggregate(solver.FromConstant(0), (previous, next) => previous.Operation(OperationType.Addition, next));
}).ToArray();
for(int i = 0;i<4;++i) {
colorSums[i].Set(ConstraintType.Equal, solver.FromConstant(Enumerable.Range(0, 4).Select(y => figures[y][i]).Sum()));
}
colorVariables[0][0].Set(ConstraintType.Equal, colorVariables[0][1]);
colorVariables[0][1].Set(ConstraintType.Equal, colorVariables[0][2]);
for(int x = 0;x<width;++x) {
for(int y = 0;y<height;++y) {
if(x == width-1 && y > height -4) {
break;
}
List<IVariable> variables = new List<IVariable>();
int copyY = y;
int copyX = x;
while(variables.Count < 4) {
variables.Add(colorVariables[copyX][copyY]);
copyY ++;
if(copyY >= height) {
copyY = 0;
copyX ++;
}
}
var isFirstThreeEqual = variables[0].Operation(OperationType.IsEqual, variables[1])
.Operation(OperationType.Conjunction, variables[0].Operation(OperationType.IsEqual, variables[2]));
var isLastThreeEqual = variables[1].Operation(OperationType.IsEqual, variables[2])
.Operation(OperationType.Conjunction, variables[1].Operation(OperationType.IsEqual, variables[3]));
var areParis = variables[0].Operation(OperationType.IsEqual, variables[1])
.Operation(OperationType.Conjunction, variables[2].Operation(OperationType.IsEqual, variables[3]));
isFirstThreeEqual
.Operation(OperationType.Disjunction, isLastThreeEqual)
.Operation(OperationType.Disjunction, areParis)
.Set(ConstraintType.Equal, solver.FromConstant(1));
}
}
for(int x = 1;x<width;++x) {
var difference = Enumerable.Range(1, 4)
.Select(shape => shapesSums[shape-1][x].Operation(OperationType.Subtraction, shapesSums[shape-1][x-1]).Operation(OperationType.AbsoluteValue))
.Aggregate(solver.FromConstant(0), (previous, next) => previous.Operation(OperationType.Addition, next))
.Set(ConstraintType.LessOrEqual, solver.FromConstant(10));
}
for(int i = 0;i<4;++i) {
shapesSums[i].Aggregate(solver.FromConstant(0), (previous, next) => previous.Operation(OperationType.Addition, next))
.Set(ConstraintType.Equal, solver.FromConstant(figures[i].Sum()));
}
solver.AddGoal("Goal", solver.FromConstant(0));
solver.Solve();
for(int y = 0;y<height;++y) {
for(int x = 0;x<width;++x) {
int shape = (int)solver.GetValue(shapeVariables[x][y]);
int color = (int)solver.GetValue(colorVariables[x][y]);
Console.Write(string.Format("{0}{1}\t", shapeMap[shape], colorMap[color]));
}
Console.WriteLine();
}
for(int i = 0;i<4;++i) {
for(int x = 0;x<width;++x) {
Console.Write(solver.GetValue(shapesSums[i][x]));
Console.Write("\t");
}
Console.WriteLine();
}
for(int i = 0;i<4;++i) {
Console.Write(solver.GetValue(colorSums[i]));
Console.Write("\t");
}
}