ILP Part 98 — Horrendum 2 – Random IT Utensils

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

Today we’re going to solve Horrendum 2. We have a rectangular board. We need to fill the board with numbers from zero to four in a way that each row and column has 5 numbers and 3 empty fields. Also, each field with arrow indicates how many fields are filled in the rest of the row/column according to the direction of the arrow.

Solution:

var board = new [] {
	"   R    ",
	"D D  L  ",
	" U    U ",
	"D U R   ",
	"     D D",
	" L D  R ",
	"  R D   ",
	"        "
};

int height = board.Length;
int width = board[0].Length;

var fields = Enumerable
	.Range(0, height)
	.Select(h => Enumerable
		.Range(0, width)
		.Select(w => solver.CreateAnonymous(Domain.AnyInteger)
			.Set<GreaterOrEqual>(solver.FromConstant(-3)).Set<LessOrEqual>(solver.FromConstant(4))
		).ToArray()
	).ToArray();

// Enforce numbers in arrows
for(int i=0;i<height;++i){
	for(int j=0;j<width;++j){
		if(board[i][j] != ' '){
			fields[i][j].Set<GreaterOrEqual>(solver.FromConstant(0));
		}
	}
}

// Make rows unique
for(int i=0;i<height;++i){
	solver.Set<AllDifferent>(fields[i][0], Enumerable.Range(1, width - 1).Select(j => fields[i][j]).ToArray());
}

// Make columns unique
for(int j=0;j<width;++j){
	solver.Set<AllDifferent>(fields[0][j], Enumerable.Range(1, height - 1).Select(i => fields[i][j]).ToArray());
}

// Make arrows match numbers in rest of the line
for(int i=0;i<height;++i){
	for(int j=0;j<width;++j){
		if(board[i][j] == ' '){
			continue;
		}
			
		IVariable[] rest = null;
		
		if(board[i][j] == 'R'){
			rest = Enumerable.Range(j + 1, width - j - 1).Select(k => fields[i][k]).ToArray();
		} else if(board[i][j] == 'D'){
			rest = Enumerable.Range(i + 1, height - i - 1).Select(k => fields[k][j]).ToArray();
		} else if(board[i][j] == 'L'){
			rest = Enumerable.Range(0, j).Select(k => fields[i][k]).ToArray();
		} else {
			rest = Enumerable.Range(0, i).Select(k => fields[k][j]).ToArray();
		}
		
		solver.Operation<Addition>(rest.Select(v => v.Operation<IsGreaterOrEqual>(solver.FromConstant(0))).ToArray())
			.Set<Equal>(fields[i][j]);
	}
}

var goal = solver.FromConstant(0);
solver.Solve();

for(int i=0;i<height;++i){
	for(int j=0;j<width;++j){
		var value = Math.Round(solver.GetValue(fields[i][j]));
		if(value < 0){
			Console.Write(" ");
		}else {
			Console.Write(value);
		}
	}
	Console.WriteLine();
}
Console.WriteLine();

var board = new [] {

" R ",

"D D L ",

" U U ",

"D U R ",

" D D",

" L D R ",

" R D ",

" "

};

int height = board.Length;

int width = board[0].Length;

var fields = Enumerable

.Range(0, height)

.Select(h => Enumerable

.Range(0, width)

.Select(w => solver.CreateAnonymous(Domain.AnyInteger)

.Set<GreaterOrEqual>(solver.FromConstant(-3)).Set<LessOrEqual>(solver.FromConstant(4))

).ToArray()

).ToArray();

// Enforce numbers in arrows

for(int i=0;i<height;++i){

for(int j=0;j<width;++j){

if(board[i][j] != ' '){

fields[i][j].Set<GreaterOrEqual>(solver.FromConstant(0));

}

// Make rows unique

for(int i=0;i<height;++i){

solver.Set<AllDifferent>(fields[i][0], Enumerable.Range(1, width - 1).Select(j => fields[i][j]).ToArray());

}

// Make columns unique

for(int j=0;j<width;++j){

solver.Set<AllDifferent>(fields[0][j], Enumerable.Range(1, height - 1).Select(i => fields[i][j]).ToArray());

}

// Make arrows match numbers in rest of the line

for(int i=0;i<height;++i){

for(int j=0;j<width;++j){

if(board[i][j] == ' '){

continue;

}

IVariable[] rest = null;

if(board[i][j] == 'R'){

rest = Enumerable.Range(j + 1, width - j - 1).Select(k => fields[i][k]).ToArray();

} else if(board[i][j] == 'D'){

rest = Enumerable.Range(i + 1, height - i - 1).Select(k => fields[k][j]).ToArray();

} else if(board[i][j] == 'L'){

rest = Enumerable.Range(0, j).Select(k => fields[i][k]).ToArray();

} else {

rest = Enumerable.Range(0, i).Select(k => fields[k][j]).ToArray();

}

solver.Operation<Addition>(rest.Select(v => v.Operation<IsGreaterOrEqual>(solver.FromConstant(0))).ToArray())

.Set<Equal>(fields[i][j]);

}

var goal = solver.FromConstant(0);

solver.Solve();

for(int i=0;i<height;++i){

for(int j=0;j<width;++j){

var value = Math.Round(solver.GetValue(fields[i][j]));

if(value < 0){

Console.Write(" ");

}else {

Console.Write(value);

}

Console.WriteLine();

}

Console.WriteLine();

As usual, we start with the board (lines 1-13). Next, we represent the board as a series of integers. Each field will be filled, and we’ll represent the empty fields with negative numbers (lines 15-22).

Next, we make sure that fields with arrows are filled (lines 24-31).

Next, we enforce rows and columns (like in Sudoku) – lines 3-41.

Finally, we take all the fields indicated by arrows, and make sure that these fields are filled accordingly (lines 43-65).

Output:

Tried aggregator 2 times.
MIP Presolve eliminated 1536 rows and 919 columns.
MIP Presolve modified 4614 coefficients.
Aggregator did 91 substitutions.
Reduced MIP has 2337 rows, 999 columns, and 6490 nonzeros.
Reduced MIP has 938 binaries, 61 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.02 sec. (6.74 ticks)
Probing fixed 17 vars, tightened 7 bounds.
Probing changed sense of 440 constraints.
Probing time = 0.03 sec. (12.09 ticks)
Cover probing fixed 0 vars, tightened 25 bounds.
Tried aggregator 2 times.
MIP Presolve eliminated 223 rows and 153 columns.
MIP Presolve modified 283 coefficients.
Aggregator did 336 substitutions.
Reduced MIP has 1778 rows, 510 columns, and 5263 nonzeros.
Reduced MIP has 450 binaries, 60 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.02 sec. (6.03 ticks)
Probing fixed 2 vars, tightened 1 bounds.
Probing time = 0.01 sec. (3.78 ticks)
Cover probing fixed 0 vars, tightened 1 bounds.
Tried aggregator 2 times.
MIP Presolve eliminated 6 rows and 4 columns.
MIP Presolve modified 65 coefficients.
Aggregator did 1 substitutions.
Reduced MIP has 1771 rows, 505 columns, and 5242 nonzeros.
Reduced MIP has 445 binaries, 60 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.02 sec. (5.36 ticks)
Probing time = 0.02 sec. (3.90 ticks)
Clique table members: 1249.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 8 threads.
Root relaxation solution time = 0.00 sec. (7.39 ticks)

        Nodes                                         Cuts/
   Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap

      0     0        0.0000   104                      0.0000      309
      0     0        0.0000    91                    Cuts: 54      364
      0     0        0.0000   157                   Cuts: 116      500
      0     0        0.0000    66                    Cuts: 16      528
      0     0        0.0000   100                    Cuts: 60      613
      0     2        0.0000   100                      0.0000      613
Elapsed time = 0.63 sec. (214.60 ticks, tree = 0.01 MB, solutions = 0)
   1217   145        0.0000    45                      0.0000    24362
   2807   188        0.0000    41                      0.0000    51662
   4355   203        0.0000    46                      0.0000    80350
   6220   308        0.0000    43                      0.0000   103716
   6597   339        0.0000    81                      0.0000   108402
   6672   222        0.0000    37                      0.0000   111638
   7113    79        0.0000    44                      0.0000   126775
   7742    94        0.0000    27                      0.0000   146791
   8246    95        0.0000    50                      0.0000   169279
   9777    84        0.0000    50                      0.0000   230823
Elapsed time = 11.66 sec. (4402.69 ticks, tree = 0.17 MB, solutions = 0)
  11346   168        0.0000    63                      0.0000   287814
  14198   251        0.0000    52                      0.0000   386401
  17188   477    infeasible                            0.0000   502464
  20156   771        0.0000    68                      0.0000   618516
  23390   750        0.0000    41                      0.0000   743953
  27088   764        0.0000    37                      0.0000   870399
  30492  1020        0.0000    49                      0.0000   994022
  34095  1084        0.0000    39                      0.0000  1119451
  37785  1178        0.0000    84                      0.0000  1252184
  41440  1266        0.0000    44                      0.0000  1383705
Elapsed time = 44.86 sec. (13959.22 ticks, tree = 0.10 MB, solutions = 0)
  45089  1401        0.0000    59                      0.0000  1513966
  48587  1462        0.0000    37                      0.0000  1641233
  52107  1442    infeasible                            0.0000  1773688
  55809  1700        0.0000    37                      0.0000  1905442
  59276  1830        0.0000    84                      0.0000  2043446
  62717  1679        0.0000    43                      0.0000  2180412
  66350  1448        0.0000    48                      0.0000  2310054
  70373  1480    infeasible                            0.0000  2439498
  74281  1234        0.0000    29                      0.0000  2566073
  78479  1110        0.0000    52                      0.0000  2697817
Elapsed time = 74.02 sec. (23512.97 ticks, tree = 0.09 MB, solutions = 0)
  82527   873        0.0000    36                      0.0000  2818290
  86790   490    infeasible                            0.0000  2956576
* 87578   306      integral     0        0.0000        0.0000  2984334    0.00%

Root node processing (before b&c):
  Real time             =    0.61 sec. (213.77 ticks)
Parallel b&c, 8 threads:
  Real time             =   79.80 sec. (25497.28 ticks)
  Sync time (average)   =    7.33 sec.
  Wait time (average)   =    0.02 sec.
                          ------------
Total (root+branch&cut) =   80.41 sec. (25711.05 ticks)
1  3204
3 4  210
 0  3421
23140
 40  132
41 2 30
 2301  4
0 214  3

Tried aggregator 2 times.

MIP Presolve eliminated 1536 rows and 919 columns.

MIP Presolve modified 4614 coefficients.

Aggregator did 91 substitutions.

Reduced MIP has 2337 rows, 999 columns, and 6490 nonzeros.

Reduced MIP has 938 binaries, 61 generals, 0 SOSs, and 0 indicators.

Presolve time = 0.02 sec. (6.74 ticks)

Probing fixed 17 vars, tightened 7 bounds.

Probing changed sense of 440 constraints.

Probing time = 0.03 sec. (12.09 ticks)

Cover probing fixed 0 vars, tightened 25 bounds.

Tried aggregator 2 times.

MIP Presolve eliminated 223 rows and 153 columns.

MIP Presolve modified 283 coefficients.

Aggregator did 336 substitutions.

Reduced MIP has 1778 rows, 510 columns, and 5263 nonzeros.

Reduced MIP has 450 binaries, 60 generals, 0 SOSs, and 0 indicators.

Presolve time = 0.02 sec. (6.03 ticks)

Probing fixed 2 vars, tightened 1 bounds.

Probing time = 0.01 sec. (3.78 ticks)

Cover probing fixed 0 vars, tightened 1 bounds.

Tried aggregator 2 times.

MIP Presolve eliminated 6 rows and 4 columns.

MIP Presolve modified 65 coefficients.

Aggregator did 1 substitutions.

Reduced MIP has 1771 rows, 505 columns, and 5242 nonzeros.

Reduced MIP has 445 binaries, 60 generals, 0 SOSs, and 0 indicators.

Presolve time = 0.02 sec. (5.36 ticks)

Probing time = 0.02 sec. (3.90 ticks)

Clique table members: 1249.

MIP emphasis: balance optimality and feasibility.

MIP search method: dynamic search.

Parallel mode: deterministic, using up to 8 threads.

Root relaxation solution time = 0.00 sec. (7.39 ticks)

Nodes Cuts/

Node Left Objective IInf Best Integer Best Bound ItCnt Gap

0 0 0.0000 104 0.0000 309

0 0 0.0000 91 Cuts: 54 364

0 0 0.0000 157 Cuts: 116 500

0 0 0.0000 66 Cuts: 16 528

0 0 0.0000 100 Cuts: 60 613

0 2 0.0000 100 0.0000 613

Elapsed time = 0.63 sec. (214.60 ticks, tree = 0.01 MB, solutions = 0)

1217 145 0.0000 45 0.0000 24362

2807 188 0.0000 41 0.0000 51662

4355 203 0.0000 46 0.0000 80350

6220 308 0.0000 43 0.0000 103716

6597 339 0.0000 81 0.0000 108402

6672 222 0.0000 37 0.0000 111638

7113 79 0.0000 44 0.0000 126775

7742 94 0.0000 27 0.0000 146791

8246 95 0.0000 50 0.0000 169279

9777 84 0.0000 50 0.0000 230823

Elapsed time = 11.66 sec. (4402.69 ticks, tree = 0.17 MB, solutions = 0)

11346 168 0.0000 63 0.0000 287814

14198 251 0.0000 52 0.0000 386401

17188 477 infeasible 0.0000 502464

20156 771 0.0000 68 0.0000 618516

23390 750 0.0000 41 0.0000 743953

27088 764 0.0000 37 0.0000 870399

30492 1020 0.0000 49 0.0000 994022

34095 1084 0.0000 39 0.0000 1119451

37785 1178 0.0000 84 0.0000 1252184

41440 1266 0.0000 44 0.0000 1383705

Elapsed time = 44.86 sec. (13959.22 ticks, tree = 0.10 MB, solutions = 0)

45089 1401 0.0000 59 0.0000 1513966

48587 1462 0.0000 37 0.0000 1641233

52107 1442 infeasible 0.0000 1773688

55809 1700 0.0000 37 0.0000 1905442

59276 1830 0.0000 84 0.0000 2043446

62717 1679 0.0000 43 0.0000 2180412

66350 1448 0.0000 48 0.0000 2310054

70373 1480 infeasible 0.0000 2439498

74281 1234 0.0000 29 0.0000 2566073

78479 1110 0.0000 52 0.0000 2697817

Elapsed time = 74.02 sec. (23512.97 ticks, tree = 0.09 MB, solutions = 0)

82527 873 0.0000 36 0.0000 2818290

86790 490 infeasible 0.0000 2956576

* 87578 306 integral 0 0.0000 0.0000 2984334 0.00%

Root node processing (before b&c):

Real time = 0.61 sec. (213.77 ticks)

Parallel b&c, 8 threads:

Real time = 79.80 sec. (25497.28 ticks)

Sync time (average) = 7.33 sec.

Wait time (average) = 0.02 sec.

------------

Total (root+branch&cut) = 80.41 sec. (25711.05 ticks)

1 3204

3 4 210

0 3421

23140

40 132

41 2 30

2301 4

0 214 3