ILP Part 48 — Shapes and colors

This is the forty eighth part of the ILP series. For your convenience you can find other parts in the table of contents in Part 1 – Boolean algebra

You are given board with thirty rows and fifteen columns. For each cell you need to assign a shape with color. You are given the following shapes and collors:

$\begin{array}{ccccc} Shape & Green & Blue & Red & Yellow \\ \hline \\ Circle & 50 & 30 & 30 & 15\\ Square & 20 & 20 & 25 & 20 \\ Triangle & 40 & 30 & 30 & 5\\ Rectangle & 15 & 60 & 20 & 40 \\ \hline \end{array}$

You are given two more requirements. For two neighboring columns you can change at most ten shapes, i.e., if you have 20 squares and 10 triangles in first column, you can have 15 squares, 10 triangles, 2 circles and 3 rectangles in second one. But you cannot have 10 squares and 20 triangles.

Also, you can change color after at least three consecutive cells in column-wise order. It means that if you have green in row 0 column 0, row 1 column 0 and row 2 column 0 must have the same color. The order includes following columns so you change color in last cell of column 3, two first cells of column 4 must have the same color.

This is the solution:

public static void Start() {
    var solver = new CplexMilpSolver(10);

    int width = 15;
    int height = 30;

    Console.WriteLine("Colors of shapes");
    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" }, // Green
        {
            2, "N" }, // Blue
        {
            3, "C" }, // Red
        {
            4, "P" } // Yellow
    };

    var shapeMap = new Dictionary< int, string> {
        {
            1, "O" }, // Circle
        {
            2, "K" }, // Square
        {
            3, "T" }, // Triangle
        {
            4, "P" } // Rectangle
    };

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

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

    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 color = 1;color< = 4;++color) {
        for(int shape = 1;shape< = 4;++shape) {
            Enumerable.Range(0, width).SelectMany(x => Enumerable.Range(0, height).Select(y =>
                colorVariables[x][y].Operation(OperationType.IsEqual, solver.FromConstant(color)).Operation(OperationType.Conjunction, shapeVariables[x][y].Operation(OperationType.IsEqual, solver.FromConstant(shape)))
            )).Aggregate(solver.FromConstant(0), (previous, next) => previous.Operation(OperationType.Addition, next)).Set(ConstraintType.Equal, solver.FromConstant(figures[color-1][shape-1]));
        }
    }

    solver.AddGoal("Goal", solver.FromConstant(0));
    solver.SaveModelToFile("problem.mps");
    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();
    }
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

public static void Start() {

var solver = new CplexMilpSolver(10);

int width = 15;

int height = 30;

Console.WriteLine("Colors of shapes");

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" }, // Green

{

2, "N" }, // Blue

{

3, "C" }, // Red

{

4, "P" } // Yellow

};

var shapeMap = new Dictionary< int, string> {

{

1, "O" }, // Circle

{

2, "K" }, // Square

{

3, "T" }, // Triangle

{

4, "P" } // Rectangle

};

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));

}

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

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 color = 1;color< = 4;++color) {

for(int shape = 1;shape< = 4;++shape) {

Enumerable.Range(0, width).SelectMany(x => Enumerable.Range(0, height).Select(y =>

colorVariables[x][y].Operation(OperationType.IsEqual, solver.FromConstant(color)).Operation(OperationType.Conjunction, shapeVariables[x][y].Operation(OperationType.IsEqual, solver.FromConstant(shape)))

)).Aggregate(solver.FromConstant(0), (previous, next) => previous.Operation(OperationType.Addition, next)).Set(ConstraintType.Equal, solver.FromConstant(figures[color-1][shape-1]));

}

solver.AddGoal("Goal", solver.FromConstant(0));

solver.SaveModelToFile("problem.mps");

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

}

And solution:

PP      OC      ON      KZ      OZ      KN      PC      OC      TC      OC      KP      OZ      KN      PP      TP

PP      TZ      PN      OZ      KZ      PN      OC      TC      OC      KC      KP      PZ      PN      PP      OZ

PP      OZ      TC      OZ      OZ      KZ      KC      OC      TC      KC      PN      OZ      TN      PP      OZ

TZ      KZ      OC      OP      PZ      KZ      PC      PC      PP      KC      PN      TZ      PN      OZ      PZ

KZ      PP      KC      OP      PC      PZ      TC      TN      OP      KZ      KN      TZ      ON      OZ      TZ

KZ      KP      OC      PP      PC      KC      PP      TN      PP      OZ      KP      OZ      TZ      OZ      OZ

TC      OP      KC      OP      KC      KC      OP      PN      KC      KZ      OP      TZ      OZ      OZ      OZ

KC      PN      ON      TP      OP      OC      OP      PN      TC      PP      PP      KZ      OZ      PP      TZ

KC      ON      ON      PP      OP      OC      TC      PC      TC      PP      KP      OC      PN      TP      TN

ON      PN      PN      PN      KP      TZ      KC      TC      PN      PP      TZ      OC      TN      KP      PN

PN      PZ      TN      TN      KZ      TZ      TC      PC      PN      PN      TZ      TC      KN      PN      TN

ON      TZ      PN      PN      TZ      PZ      PN      KZ      PN      KN      TZ      PC      TN      ON      OZ

TN      PZ      PC      KZ      OZ      TZ      PN      KZ      TZ      ON      PN      TN      OP      KN      OZ

PN      TC      KC      OZ      ON      OZ      KN      OZ      TZ      OZ      KN      ON      PP      TN      OZ

OZ      TC      TC      OZ      ON      OZ      PP      PP      TZ      OZ      TN      ON      PP      ON      TZ

OZ      OC      PN      PN      PN      KP      PP      TP      TZ      TZ      KN      ON      KP      TN      PP

TZ      TZ      PN      KN      PN      PP      KP      KP      ON      TZ      ON      PN      PZ      ON      PP

KC      OZ      PN      PN      TC      OP      OZ      PC      ON      PC      PN      KC      TZ      PN      OP

PC      OZ      KZ      OZ      TC      TN      PZ      OC      KN      PC      OZ      KC      TZ      PN      KP

OC      PN      OZ      OZ      OC      PN      OZ      TC      KC      OC      KZ      TC      PN      TN      PP

KC      TN      PZ      OZ      ON      PN      KC      TC      TC      OC      OZ      ON      PN      KN      PP

TC      PN      KC      KZ      PN      ON      OC      PN      OC      TC      TZ      TN      ON      TN      OZ

PP      PP      OC      OZ      ON      TN      OC      KN      PN      TC      TN      PN      ON      TN      TZ

PP      PP      TC      TZ      PN      PP      PZ      KN      PN      PN      TN      KN      PP      ON      TZ

TP      PP      KC      PZ      TN      KP      KZ      PN      PN      PN      ON      PN      PP      TN      KP

PC      KN      TC      PZ      TZ      PP      TZ      TZ      PC      KN      KN      TC      KP      ON      OP

KC      TN      PN      KP      PZ      KP      PN      TZ      OC      TZ      OC      OC      OZ      PP      PP

KC      PN      TN      KP      OZ      PC      KN      OZ      TC      TZ      PC      PC      OZ      KP      TZ

PC      TN      ON      PP      KN      OC      PN      PC      OC      TZ      TC      PN      TZ      PP      OZ

TC      PN      KZ      KZ      TN      OC      TN      OC      KC      KP      OC      ON      PZ      OP      OZ

PP OC ON KZ OZ KN PC OC TC OC KP OZ KN PP TP

PP TZ PN OZ KZ PN OC TC OC KC KP PZ PN PP OZ

PP OZ TC OZ OZ KZ KC OC TC KC PN OZ TN PP OZ

TZ KZ OC OP PZ KZ PC PC PP KC PN TZ PN OZ PZ

KZ PP KC OP PC PZ TC TN OP KZ KN TZ ON OZ TZ

KZ KP OC PP PC KC PP TN PP OZ KP OZ TZ OZ OZ

TC OP KC OP KC KC OP PN KC KZ OP TZ OZ OZ OZ

KC PN ON TP OP OC OP PN TC PP PP KZ OZ PP TZ

KC ON ON PP OP OC TC PC TC PP KP OC PN TP TN

ON PN PN PN KP TZ KC TC PN PP TZ OC TN KP PN

PN PZ TN TN KZ TZ TC PC PN PN TZ TC KN PN TN

ON TZ PN PN TZ PZ PN KZ PN KN TZ PC TN ON OZ

TN PZ PC KZ OZ TZ PN KZ TZ ON PN TN OP KN OZ

PN TC KC OZ ON OZ KN OZ TZ OZ KN ON PP TN OZ

OZ TC TC OZ ON OZ PP PP TZ OZ TN ON PP ON TZ

OZ OC PN PN PN KP PP TP TZ TZ KN ON KP TN PP

TZ TZ PN KN PN PP KP KP ON TZ ON PN PZ ON PP

KC OZ PN PN TC OP OZ PC ON PC PN KC TZ PN OP

PC OZ KZ OZ TC TN PZ OC KN PC OZ KC TZ PN KP

OC PN OZ OZ OC PN OZ TC KC OC KZ TC PN TN PP

KC TN PZ OZ ON PN KC TC TC OC OZ ON PN KN PP

TC PN KC KZ PN ON OC PN OC TC TZ TN ON TN OZ

PP PP OC OZ ON TN OC KN PN TC TN PN ON TN TZ

PP PP TC TZ PN PP PZ KN PN PN TN KN PP ON TZ

TP PP KC PZ TN KP KZ PN PN PN ON PN PP TN KP

PC KN TC PZ TZ PP TZ TZ PC KN KN TC KP ON OP

KC TN PN KP PZ KP PN TZ OC TZ OC OC OZ PP PP

KC PN TN KP OZ PC KN OZ TC TZ PC PC OZ KP TZ

PC TN ON PP KN OC PN PC OC TZ TC PN TZ PP OZ

TC PN KZ KZ TN OC TN OC KC KP OC ON PZ OP OZ