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} \]](../../../../wp-content/ql-cache/quicklatex.com-42ccc4b2a40057ea6bac794dc5678d0f_l3.png "Rendered by QuickLaTeX.com")
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
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 |