ILP Part 94 — Horrendum – Random IT Utensils

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

Let’s solve Horrendum. It’s a fancy sudoku. First, we need to make sure that numbers in rows and columns are unique (as always). We also need to make sure that the diagonal going from top left to the bottom right contains unique numbers as well. Next, each 8-pieces shape must have unique numbers. Finally, 8 blue fields must be unique, same as 5 pink shapes. Generally, nothing surprising, just a slight variation of Sudoku.

First, let’s see the regular solution:

int height = 8;
int width = 8;

var groups = new int[][]{
	new int[] { 1, 2, 3, 3, 3, 3, 3, 3 },
	new int[] { 4, 2, 2, 5, 3, 1, 3, 1 },
	new int[] { 4, 1, 2, 5, 1, 6, 6, 6 },
	new int[] { 4, 2, 2, 2, 6, 6, 6, 6 },
	new int[] { 4, 5, 1, 2, 7, 5, 5, 6 },
	new int[] { 4, 5, 7, 7, 7, 7, 5, 8 },
	new int[] { 4, 4, 7, 7, 8, 8, 5, 8 },
	new int[] { 1, 4, 1, 7, 8, 8, 8, 8 }
};

var values = new int[][]{
	new int[] { 0, 0, 0, 0, 0, 0, 0, 0 },
	new int[] { 0, 0, 0, 1, 2, 0, 0, 0 },
	new int[] { 0, 0, 0, 0, 0, 0, 0, 0 },
	new int[] { 0, 0, 0, 0, 0, 0, 3, 0 },
	new int[] { 0, 4, 0, 0, 0, 0, 0, 0 },
	new int[] { 0, 0, 0, 0, 0, 0, 0, 5 },
	new int[] { 0, 0, 0, 0, 0, 6, 0, 0 },
	new int[] { 0, 7, 0, 0, 0, 0, 0, 0 }
};

Console.WriteLine("Create variables");
var fields = Enumerable.Range(0, height)
	.Select(r => Enumerable.Range(0, width)
		.Select(c => solver.CreateAnonymous(Domain.PositiveOrZeroInteger)).ToArray()
	).ToArray();
 
Console.WriteLine("Set known values");
for(int row = 0; row < height;++row){
	for(int column = 0; column < width; ++ column){
		if(values[row][column] > 0){
			solver.Set<Equal>(fields[row][column], solver.FromConstant(values[row][column]));
		}
	}
}
 
Console.WriteLine("Set ranges");
for(int row = 0; row < height;++row){
	for(int column = 0; column < width; ++ column){
		solver.Set<LessOrEqual>(fields[row][column], solver.FromConstant(8));
		solver.Set<GreaterOrEqual>(fields[row][column], solver.FromConstant(1));
	}
}
 
Console.WriteLine("Rows");
for(int row = 0; row < height;++row){
	solver.Set<AllDifferent>(fields[row][0], fields[row].Skip(1).ToArray());
}
 
Console.WriteLine("Columns");
for(int column = 0; column < width; ++ column){
	solver.Set<AllDifferent>(fields[0][column], Enumerable.Range(1, height-1).Select(row => fields[row][column]).ToArray());
}
 
Console.WriteLine("Groups");
foreach(var group in Enumerable.Range(1, groups.SelectMany(g => g).Distinct().Count())){
	var fieldsInGroup = new List<IVariable>();
	for(int row = 0; row < height;++row){
		for(int column = 0; column < width; ++ column){
			if(groups[row][column] == group){
				fieldsInGroup.Add(fields[row][column]);
			}
		}
	}
	solver.Set<AllDifferent>(fieldsInGroup[0], fieldsInGroup.Skip(1).ToArray());
}

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

solver.AddGoal("goal", solver.FromConstant(0));
solver.Solve();

for(int row = 0; row < height;++row){
	if(row % 3 == 0)Console.WriteLine("------------");
	for(int column = 0; column < width; ++ column){
		if(column % 3 == 0)Console.Write("|");
		Console.Write(Math.Round(solver.GetValue(fields[row][column])));
	}
	Console.Write("|");
	Console.WriteLine();
}
Console.WriteLine("------------");

int height = 8;

int width = 8;

var groups = new int[][]{

new int[] { 1, 2, 3, 3, 3, 3, 3, 3 },

new int[] { 4, 2, 2, 5, 3, 1, 3, 1 },

new int[] { 4, 1, 2, 5, 1, 6, 6, 6 },

new int[] { 4, 2, 2, 2, 6, 6, 6, 6 },

new int[] { 4, 5, 1, 2, 7, 5, 5, 6 },

new int[] { 4, 5, 7, 7, 7, 7, 5, 8 },

new int[] { 4, 4, 7, 7, 8, 8, 5, 8 },

new int[] { 1, 4, 1, 7, 8, 8, 8, 8 }

};

var values = new int[][]{

new int[] { 0, 0, 0, 0, 0, 0, 0, 0 },

new int[] { 0, 0, 0, 1, 2, 0, 0, 0 },

new int[] { 0, 0, 0, 0, 0, 0, 0, 0 },

new int[] { 0, 0, 0, 0, 0, 0, 3, 0 },

new int[] { 0, 4, 0, 0, 0, 0, 0, 0 },

new int[] { 0, 0, 0, 0, 0, 0, 0, 5 },

new int[] { 0, 0, 0, 0, 0, 6, 0, 0 },

new int[] { 0, 7, 0, 0, 0, 0, 0, 0 }

};

Console.WriteLine("Create variables");

var fields = Enumerable.Range(0, height)

.Select(r => Enumerable.Range(0, width)

.Select(c => solver.CreateAnonymous(Domain.PositiveOrZeroInteger)).ToArray()

).ToArray();

Console.WriteLine("Set known values");

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

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

if(values[row][column] > 0){

solver.Set<Equal>(fields[row][column], solver.FromConstant(values[row][column]));

}

Console.WriteLine("Set ranges");

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

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

solver.Set<LessOrEqual>(fields[row][column], solver.FromConstant(8));

solver.Set<GreaterOrEqual>(fields[row][column], solver.FromConstant(1));

}

Console.WriteLine("Rows");

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

solver.Set<AllDifferent>(fields[row][0], fields[row].Skip(1).ToArray());

}

Console.WriteLine("Columns");

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

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

}

Console.WriteLine("Groups");

foreach(var group in Enumerable.Range(1, groups.SelectMany(g => g).Distinct().Count())){

var fieldsInGroup = new List<IVariable>();

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

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

if(groups[row][column] == group){

fieldsInGroup.Add(fields[row][column]);

}

solver.Set<AllDifferent>(fieldsInGroup[0], fieldsInGroup.Skip(1).ToArray());

}

Console.WriteLine("Diagonal");

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

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

solver.Solve();

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

if(row % 3 == 0)Console.WriteLine("------------");

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

if(column % 3 == 0)Console.Write("|");

Console.Write(Math.Round(solver.GetValue(fields[row][column])));

}

Console.Write("|");

Console.WriteLine();

}

Console.WriteLine("------------");

Nothing new here. We first assign integers to groups, so we know which fields should be considered together. Next, we encode some known values. Finally, we create integers for each field, iterate over rows, columns, groups, and the diagonal, and add constraints. Output:

Tried aggregator 1 time.
MIP Presolve eliminated 2420 rows and 1471 columns.
MIP Presolve modified 8182 coefficients.
Reduced MIP has 3340 rows, 1393 columns, and 8908 nonzeros.
Reduced MIP has 1336 binaries, 57 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.03 sec. (7.26 ticks)
Probing changed sense of 668 constraints.
Probing time = 0.05 sec. (21.40 ticks)
Tried aggregator 2 times.
MIP Presolve eliminated 414 rows and 155 columns.
MIP Presolve modified 195 coefficients.
Aggregator did 551 substitutions.
Reduced MIP has 2375 rows, 687 columns, and 6977 nonzeros.
Reduced MIP has 630 binaries, 57 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.02 sec. (8.13 ticks)
Probing time = 0.00 sec. (5.42 ticks)
Tried aggregator 1 time.
MIP Presolve eliminated 4 rows and 1 columns.
Reduced MIP has 2371 rows, 686 columns, and 6965 nonzeros.
Reduced MIP has 629 binaries, 57 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.00 sec. (4.76 ticks)
Probing time = 0.02 sec. (5.56 ticks)
Clique table members: 944.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 8 threads.
Root relaxation solution time = 0.03 sec. (9.67 ticks)

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

      0     0        0.0000   252                      0.0000      451
      0     0        0.0000    82                   Cuts: 112      528
      0     0        0.0000   209                   Cuts: 223      757
      0     0        0.0000    73                     Cuts: 9      774
      0     0        0.0000   102                   Cuts: 126      894
      0     2        0.0000    62                      0.0000      894
Elapsed time = 0.80 sec. (298.05 ticks, tree = 0.01 MB, solutions = 0)
    605   298    infeasible                            0.0000    18603
   1607   469        0.0000    57                      0.0000    47163
   2665   537        0.0000    49                      0.0000    75184
   3684   585        0.0000    52                      0.0000   101784
   4745   712        0.0000    75                      0.0000   125086
   6189   945        0.0000    53                      0.0000   149057
   7176  1030        0.0000    93                     -0.0000   170662
   7264  1004        0.0000    32                     -0.0000   173838
   7588   652        0.0000    69                     -0.0000   185953
   9486   352        0.0000    36                     -0.0000   271140
Elapsed time = 7.39 sec. (3955.43 ticks, tree = 0.04 MB, solutions = 0)
  10324   427        0.0000    78                      0.0000   294408
  11018   344        0.0000    53                      0.0000   330685
  12799   547    infeasible                            0.0000   442833
  14658   604        0.0000    39                      0.0000   555568
  16508   560    infeasible                            0.0000   678562
  18658   636        0.0000    45                      0.0000   806084
  20798   837        0.0000    49                      0.0000   935524
  23079   829        0.0000    60                      0.0000  1071118
  25250   997    infeasible                            0.0000  1206149
  27397  1232        0.0000    68                      0.0000  1346437
Elapsed time = 23.22 sec. (14032.78 ticks, tree = 0.11 MB, solutions = 0)
  29324  1455        0.0000    55                      0.0000  1493145
  31498  1480        0.0000    53                      0.0000  1640324
  33853  1414        0.0000    82                      0.0000  1791524
  36201  1559        0.0000    58                      0.0000  1934027
  38444  1625        0.0000    85                      0.0000  2070220
  40940  1671        0.0000    66                      0.0000  2220463
  43253  1813        0.0000    55                      0.0000  2361657
  45411  1919        0.0000    57                      0.0000  2504627
  47738  2041        0.0000    35                      0.0000  2650399
  50083  2082    infeasible                            0.0000  2798446
Elapsed time = 39.50 sec. (23601.83 ticks, tree = 0.39 MB, solutions = 0)
  52418  2091        0.0000    56                      0.0000  2939597
  54845  2132        0.0000    60                      0.0000  3092966
  56995  2150        0.0000    51                      0.0000  3221568
  59483  2137        0.0000    40                      0.0000  3364112
  61911  2276    infeasible                            0.0000  3512524
  64179  2524        0.0000    51                      0.0000  3650877
  66542  2520        0.0000    62                      0.0000  3798262
  68861  2641        0.0000    30                      0.0000  3945576
  71274  2672        0.0000    61                      0.0000  4098426
  73847  2711        0.0000    49                      0.0000  4240322
Elapsed time = 56.27 sec. (33167.22 ticks, tree = 1.05 MB, solutions = 0)
  76150  2659        0.0000    48                      0.0000  4390305
  78531  2685        0.0000    46                      0.0000  4538430
  80921  2923    infeasible                            0.0000  4688928
  83464  2923        0.0000    51                      0.0000  4829205
  86152  3027        0.0000    58                      0.0000  4977460
  88645  2949        0.0000    64                      0.0000  5121174
  91101  2961        0.0000    53                      0.0000  5267561
  93656  3163        0.0000    48                      0.0000  5413870
  95989  3144        0.0000    66                      0.0000  5563430
  98390  3074        0.0000    67                      0.0000  5709198
Elapsed time = 72.81 sec. (42749.52 ticks, tree = 1.25 MB, solutions = 0)
 100929  3235        0.0000    70                      0.0000  5860910
 103139  3317    infeasible                            0.0000  5999737
 105705  3288        0.0000    51                      0.0000  6158685
 107910  3377    infeasible                            0.0000  6299778
 110419  3261        0.0000    71                      0.0000  6447582
 113118  3219        0.0000    29                      0.0000  6595578
 115696  3464        0.0000    53                      0.0000  6743074
 118200  3661        0.0000    37                      0.0000  6887671
 120608  3727        0.0000    44                      0.0000  7036236
 122871  3853        0.0000    44                      0.0000  7178943
Elapsed time = 89.52 sec. (52311.98 ticks, tree = 1.84 MB, solutions = 0)
 125608  4055        0.0000    49                      0.0000  7326316
 127913  4062        0.0000    42                      0.0000  7472344
 130288  4335        0.0000    45                      0.0000  7611920
 132763  4268        0.0000    35                      0.0000  7754190
 135166  4469        0.0000    34                      0.0000  7903305
 137689  4633        0.0000    33                      0.0000  8045331
 140126  4424        0.0000    37                      0.0000  8196028
 142628  4355    infeasible                            0.0000  8351638
 145164  4532        0.0000    38                      0.0000  8497445
 147370  4530        0.0000    76                      0.0000  8645392
Elapsed time = 106.59 sec. (61877.97 ticks, tree = 2.41 MB, solutions = 0)
 149998  4657        0.0000    58                      0.0000  8796747
 152363  4501        0.0000    41                      0.0000  8945782
 154902  4705        0.0000    42                      0.0000  9104366
 157194  4696        0.0000   141                      0.0000  9250020
 159522  4879        0.0000    35                      0.0000  9396755
 161979  4744        0.0000    71                      0.0000  9547066
 164303  4941    infeasible                            0.0000  9698100
 166617  4729        0.0000    80                      0.0000  9847250
 168979  4788        0.0000    55                      0.0000 10002678
 171379  4756        0.0000    60                      0.0000 10152083
Elapsed time = 123.67 sec. (71437.92 ticks, tree = 2.59 MB, solutions = 0)
 173859  4891        0.0000    49                      0.0000 10301029
 176207  4848        0.0000    58                      0.0000 10449345
 178381  4785        0.0000    51                      0.0000 10600577
 181029  4858        0.0000    56                      0.0000 10748204
 183601  4783        0.0000    50                      0.0000 10899393
 186141  4609        0.0000   103                      0.0000 11047812
 188532  4909        0.0000    56                      0.0000 11186222
 190961  5162        0.0000    55                      0.0000 11334017
 193366  5142        0.0000    59                      0.0000 11481704
 195796  5169        0.0000    71                      0.0000 11631422
Elapsed time = 140.50 sec. (81007.25 ticks, tree = 2.74 MB, solutions = 0)
 198177  5179        0.0000    64                      0.0000 11781556
 200634  5232        0.0000    62                      0.0000 11937526
 202970  5232        0.0000    56                      0.0000 12082805
 205403  5059    infeasible                            0.0000 12236878
 208055  4774        0.0000    82                      0.0000 12391556
 210653  4847        0.0000    54                      0.0000 12545326
 213137  4641        0.0000    90                      0.0000 12705451
 215650  4516    infeasible                            0.0000 12855847
 218188  4282        0.0000    59                      0.0000 13010354
 227881  4608        0.0000    44                      0.0000 13604879
Elapsed time = 162.05 sec. (93430.39 ticks, tree = 2.22 MB, solutions = 0)
 237648  4903        0.0000    57                      0.0000 14194336
 247066  5177        0.0000    76                      0.0000 14793979
 256960  5163        0.0000    63                      0.0000 15404814
 266712  5423        0.0000    45                      0.0000 15997810
 276998  5251        0.0000    69                      0.0000 16597573
 286534  5309    infeasible                            0.0000 17194440
 295777  5559        0.0000    42                      0.0000 17800544
 305316  6193        0.0000    42                      0.0000 18394995
 315533  6841        0.0000    60                      0.0000 18989994
 325849  6698        0.0000    58                      0.0000 19590302
Elapsed time = 232.14 sec. (131608.32 ticks, tree = 3.76 MB, solutions = 0)
 335444  7147        0.0000    37                      0.0000 20181209
 345173  7501        0.0000    63                      0.0000 20789670
 354960  7393        0.0000    44                      0.0000 21398627
 365070  6993        0.0000    51                      0.0000 22005757
 374912  6605        0.0000    51                      0.0000 22613247
 384221  6958        0.0000    48                      0.0000 23216844
 393729  7458        0.0000    73                      0.0000 23819140
 403051  7594    infeasible                            0.0000 24422769
 412808  7941        0.0000    41                      0.0000 25033095
 422390  8115        0.0000    64                      0.0000 25632410
Elapsed time = 305.73 sec. (169784.86 ticks, tree = 4.59 MB, solutions = 0)
 432056  8275    infeasible                            0.0000 26243766
 441535  8231    infeasible                            0.0000 26857450
 451319  7752        0.0000    64                      0.0000 27479823
 461105  7633        0.0000    40                      0.0000 28095724
 470381  7932        0.0000    56                      0.0000 28705371
 479574  8206        0.0000    57                      0.0000 29313501
 488897  8248    infeasible                            0.0000 29926775
 497785  8738        0.0000    65                      0.0000 30539322
 507116  8939        0.0000    43                      0.0000 31142538
 516599  8741        0.0000    39                      0.0000 31760458
Elapsed time = 378.38 sec. (207956.21 ticks, tree = 4.96 MB, solutions = 0)
 526038  8627        0.0000    58                      0.0000 32373148
 535555  8755    infeasible                            0.0000 32989521
 544279  9195        0.0000    46                      0.0000 33595468
 553818  8327        0.0000    46                      0.0000 34223494
 563130  8612        0.0000    59                      0.0000 34837407
 572261  8414        0.0000    53                      0.0000 35459280
 581671  8729        0.0000    70                      0.0000 36065564
 591304  9238        0.0000    44                      0.0000 36670480
 600753  9310        0.0000    46                      0.0000 37284145
 610595  8685    infeasible                            0.0000 37903742
Elapsed time = 451.73 sec. (246129.69 ticks, tree = 4.90 MB, solutions = 0)
 620479  8221        0.0000    71                      0.0000 38517938
 629907  9064        0.0000    37                      0.0000 39110037
 639777  9339        0.0000    38                      0.0000 39710385
 650130  9135        0.0000    64                      0.0000 40307020
 660455  8801        0.0000    45                      0.0000 40908985
*660581  8585      integral     0        0.0000        0.0000 40916509    0.00%

Root node processing (before b&c):
  Real time             =    0.80 sec. (296.99 ticks)
Parallel b&c, 8 threads:
  Real time             =  487.84 sec. (265070.30 ticks)
  Sync time (average)   =   63.56 sec.
  Wait time (average)   =    0.06 sec.
                          ------------
Total (root+branch&cut) =  488.64 sec. (265367.29 ticks)
-------------
|721|634|58|
|865|123|74|
|683|512|47|
------------
|217|485|36|
|342|857|61|
|438|761|25|
------------
|154|276|83|
|576|348|12|
------------

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

Tried aggregator 1 time.

MIP Presolve eliminated 2420 rows and 1471 columns.

MIP Presolve modified 8182 coefficients.

Reduced MIP has 3340 rows, 1393 columns, and 8908 nonzeros.

Reduced MIP has 1336 binaries, 57 generals, 0 SOSs, and 0 indicators.

Presolve time = 0.03 sec. (7.26 ticks)

Probing changed sense of 668 constraints.

Probing time = 0.05 sec. (21.40 ticks)

Tried aggregator 2 times.

MIP Presolve eliminated 414 rows and 155 columns.

MIP Presolve modified 195 coefficients.

Aggregator did 551 substitutions.

Reduced MIP has 2375 rows, 687 columns, and 6977 nonzeros.

Reduced MIP has 630 binaries, 57 generals, 0 SOSs, and 0 indicators.

Presolve time = 0.02 sec. (8.13 ticks)

Probing time = 0.00 sec. (5.42 ticks)

Tried aggregator 1 time.

MIP Presolve eliminated 4 rows and 1 columns.

Reduced MIP has 2371 rows, 686 columns, and 6965 nonzeros.

Reduced MIP has 629 binaries, 57 generals, 0 SOSs, and 0 indicators.

Presolve time = 0.00 sec. (4.76 ticks)

Probing time = 0.02 sec. (5.56 ticks)

Clique table members: 944.

MIP emphasis: balance optimality and feasibility.

MIP search method: dynamic search.

Parallel mode: deterministic, using up to 8 threads.

Root relaxation solution time = 0.03 sec. (9.67 ticks)

Nodes Cuts/

Node Left Objective IInf Best Integer Best Bound ItCnt Gap

0 0 0.0000 252 0.0000 451

0 0 0.0000 82 Cuts: 112 528

0 0 0.0000 209 Cuts: 223 757

0 0 0.0000 73 Cuts: 9 774

0 0 0.0000 102 Cuts: 126 894

0 2 0.0000 62 0.0000 894

Elapsed time = 0.80 sec. (298.05 ticks, tree = 0.01 MB, solutions = 0)

605 298 infeasible 0.0000 18603

1607 469 0.0000 57 0.0000 47163

2665 537 0.0000 49 0.0000 75184

3684 585 0.0000 52 0.0000 101784

4745 712 0.0000 75 0.0000 125086

6189 945 0.0000 53 0.0000 149057

7176 1030 0.0000 93 -0.0000 170662

7264 1004 0.0000 32 -0.0000 173838

7588 652 0.0000 69 -0.0000 185953

9486 352 0.0000 36 -0.0000 271140

Elapsed time = 7.39 sec. (3955.43 ticks, tree = 0.04 MB, solutions = 0)

10324 427 0.0000 78 0.0000 294408

11018 344 0.0000 53 0.0000 330685

12799 547 infeasible 0.0000 442833

14658 604 0.0000 39 0.0000 555568

16508 560 infeasible 0.0000 678562

18658 636 0.0000 45 0.0000 806084

20798 837 0.0000 49 0.0000 935524

23079 829 0.0000 60 0.0000 1071118

25250 997 infeasible 0.0000 1206149

27397 1232 0.0000 68 0.0000 1346437

Elapsed time = 23.22 sec. (14032.78 ticks, tree = 0.11 MB, solutions = 0)

29324 1455 0.0000 55 0.0000 1493145

31498 1480 0.0000 53 0.0000 1640324

33853 1414 0.0000 82 0.0000 1791524

36201 1559 0.0000 58 0.0000 1934027

38444 1625 0.0000 85 0.0000 2070220

40940 1671 0.0000 66 0.0000 2220463

43253 1813 0.0000 55 0.0000 2361657

45411 1919 0.0000 57 0.0000 2504627

47738 2041 0.0000 35 0.0000 2650399

50083 2082 infeasible 0.0000 2798446

Elapsed time = 39.50 sec. (23601.83 ticks, tree = 0.39 MB, solutions = 0)

52418 2091 0.0000 56 0.0000 2939597

54845 2132 0.0000 60 0.0000 3092966

56995 2150 0.0000 51 0.0000 3221568

59483 2137 0.0000 40 0.0000 3364112

61911 2276 infeasible 0.0000 3512524

64179 2524 0.0000 51 0.0000 3650877

66542 2520 0.0000 62 0.0000 3798262

68861 2641 0.0000 30 0.0000 3945576

71274 2672 0.0000 61 0.0000 4098426

73847 2711 0.0000 49 0.0000 4240322

Elapsed time = 56.27 sec. (33167.22 ticks, tree = 1.05 MB, solutions = 0)

76150 2659 0.0000 48 0.0000 4390305

78531 2685 0.0000 46 0.0000 4538430

80921 2923 infeasible 0.0000 4688928

83464 2923 0.0000 51 0.0000 4829205

86152 3027 0.0000 58 0.0000 4977460

88645 2949 0.0000 64 0.0000 5121174

91101 2961 0.0000 53 0.0000 5267561

93656 3163 0.0000 48 0.0000 5413870

95989 3144 0.0000 66 0.0000 5563430

98390 3074 0.0000 67 0.0000 5709198

Elapsed time = 72.81 sec. (42749.52 ticks, tree = 1.25 MB, solutions = 0)

100929 3235 0.0000 70 0.0000 5860910

103139 3317 infeasible 0.0000 5999737

105705 3288 0.0000 51 0.0000 6158685

107910 3377 infeasible 0.0000 6299778

110419 3261 0.0000 71 0.0000 6447582

113118 3219 0.0000 29 0.0000 6595578

115696 3464 0.0000 53 0.0000 6743074

118200 3661 0.0000 37 0.0000 6887671

120608 3727 0.0000 44 0.0000 7036236

122871 3853 0.0000 44 0.0000 7178943

Elapsed time = 89.52 sec. (52311.98 ticks, tree = 1.84 MB, solutions = 0)

125608 4055 0.0000 49 0.0000 7326316

127913 4062 0.0000 42 0.0000 7472344

130288 4335 0.0000 45 0.0000 7611920

132763 4268 0.0000 35 0.0000 7754190

135166 4469 0.0000 34 0.0000 7903305

137689 4633 0.0000 33 0.0000 8045331

140126 4424 0.0000 37 0.0000 8196028

142628 4355 infeasible 0.0000 8351638

145164 4532 0.0000 38 0.0000 8497445

147370 4530 0.0000 76 0.0000 8645392

Elapsed time = 106.59 sec. (61877.97 ticks, tree = 2.41 MB, solutions = 0)

149998 4657 0.0000 58 0.0000 8796747

152363 4501 0.0000 41 0.0000 8945782

154902 4705 0.0000 42 0.0000 9104366

157194 4696 0.0000 141 0.0000 9250020

159522 4879 0.0000 35 0.0000 9396755

161979 4744 0.0000 71 0.0000 9547066

164303 4941 infeasible 0.0000 9698100

166617 4729 0.0000 80 0.0000 9847250

168979 4788 0.0000 55 0.0000 10002678

171379 4756 0.0000 60 0.0000 10152083

Elapsed time = 123.67 sec. (71437.92 ticks, tree = 2.59 MB, solutions = 0)

173859 4891 0.0000 49 0.0000 10301029

176207 4848 0.0000 58 0.0000 10449345

178381 4785 0.0000 51 0.0000 10600577

181029 4858 0.0000 56 0.0000 10748204

183601 4783 0.0000 50 0.0000 10899393

186141 4609 0.0000 103 0.0000 11047812

188532 4909 0.0000 56 0.0000 11186222

190961 5162 0.0000 55 0.0000 11334017

193366 5142 0.0000 59 0.0000 11481704

195796 5169 0.0000 71 0.0000 11631422

Elapsed time = 140.50 sec. (81007.25 ticks, tree = 2.74 MB, solutions = 0)

198177 5179 0.0000 64 0.0000 11781556

200634 5232 0.0000 62 0.0000 11937526

202970 5232 0.0000 56 0.0000 12082805

205403 5059 infeasible 0.0000 12236878

208055 4774 0.0000 82 0.0000 12391556

210653 4847 0.0000 54 0.0000 12545326

213137 4641 0.0000 90 0.0000 12705451

215650 4516 infeasible 0.0000 12855847

218188 4282 0.0000 59 0.0000 13010354

227881 4608 0.0000 44 0.0000 13604879

Elapsed time = 162.05 sec. (93430.39 ticks, tree = 2.22 MB, solutions = 0)

237648 4903 0.0000 57 0.0000 14194336

247066 5177 0.0000 76 0.0000 14793979

256960 5163 0.0000 63 0.0000 15404814

266712 5423 0.0000 45 0.0000 15997810

276998 5251 0.0000 69 0.0000 16597573

286534 5309 infeasible 0.0000 17194440

295777 5559 0.0000 42 0.0000 17800544

305316 6193 0.0000 42 0.0000 18394995

315533 6841 0.0000 60 0.0000 18989994

325849 6698 0.0000 58 0.0000 19590302

Elapsed time = 232.14 sec. (131608.32 ticks, tree = 3.76 MB, solutions = 0)

335444 7147 0.0000 37 0.0000 20181209

345173 7501 0.0000 63 0.0000 20789670

354960 7393 0.0000 44 0.0000 21398627

365070 6993 0.0000 51 0.0000 22005757

374912 6605 0.0000 51 0.0000 22613247

384221 6958 0.0000 48 0.0000 23216844

393729 7458 0.0000 73 0.0000 23819140

403051 7594 infeasible 0.0000 24422769

412808 7941 0.0000 41 0.0000 25033095

422390 8115 0.0000 64 0.0000 25632410

Elapsed time = 305.73 sec. (169784.86 ticks, tree = 4.59 MB, solutions = 0)

432056 8275 infeasible 0.0000 26243766

441535 8231 infeasible 0.0000 26857450

451319 7752 0.0000 64 0.0000 27479823

461105 7633 0.0000 40 0.0000 28095724

470381 7932 0.0000 56 0.0000 28705371

479574 8206 0.0000 57 0.0000 29313501

488897 8248 infeasible 0.0000 29926775

497785 8738 0.0000 65 0.0000 30539322

507116 8939 0.0000 43 0.0000 31142538

516599 8741 0.0000 39 0.0000 31760458

Elapsed time = 378.38 sec. (207956.21 ticks, tree = 4.96 MB, solutions = 0)

526038 8627 0.0000 58 0.0000 32373148

535555 8755 infeasible 0.0000 32989521

544279 9195 0.0000 46 0.0000 33595468

553818 8327 0.0000 46 0.0000 34223494

563130 8612 0.0000 59 0.0000 34837407

572261 8414 0.0000 53 0.0000 35459280

581671 8729 0.0000 70 0.0000 36065564

591304 9238 0.0000 44 0.0000 36670480

600753 9310 0.0000 46 0.0000 37284145

610595 8685 infeasible 0.0000 37903742

Elapsed time = 451.73 sec. (246129.69 ticks, tree = 4.90 MB, solutions = 0)

620479 8221 0.0000 71 0.0000 38517938

629907 9064 0.0000 37 0.0000 39110037

639777 9339 0.0000 38 0.0000 39710385

650130 9135 0.0000 64 0.0000 40307020

660455 8801 0.0000 45 0.0000 40908985

*660581 8585 integral 0 0.0000 0.0000 40916509 0.00%

Root node processing (before b&c):

Real time = 0.80 sec. (296.99 ticks)

Parallel b&c, 8 threads:

Real time = 487.84 sec. (265070.30 ticks)

Sync time (average) = 63.56 sec.

Wait time (average) = 0.06 sec.

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

Total (root+branch&cut) = 488.64 sec. (265367.29 ticks)

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

|721|634|58|

|865|123|74|

|683|512|47|

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

|217|485|36|

|342|857|61|

|438|761|25|

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

|154|276|83|

|576|348|12|

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

Great, it worked. However, CPLEX needed over 8 minutes to find a solution. That’s long. Can we do better?

The trick is to encode each number as binary digits. So let’s see the code:

int height = 8;
int width = 8;
int digits = 8;

var groups = new int[][]{
	new int[] { 1, 2, 3, 3, 3, 3, 3, 3 },
	new int[] { 4, 2, 2, 5, 3, 1, 3, 1 },
	new int[] { 4, 1, 2, 5, 1, 6, 6, 6 },
	new int[] { 4, 2, 2, 2, 6, 6, 6, 6 },
	new int[] { 4, 5, 1, 2, 7, 5, 5, 6 },
	new int[] { 4, 5, 7, 7, 7, 7, 5, 8 },
	new int[] { 4, 4, 7, 7, 8, 8, 5, 8 },
	new int[] { 1, 4, 1, 7, 8, 8, 8, 8 }
};

var values = new int[][]{
	new int[] { 0, 0, 0, 0, 0, 0, 0, 0 },
	new int[] { 0, 0, 0, 1, 2, 0, 0, 0 },
	new int[] { 0, 0, 0, 0, 0, 0, 0, 0 },
	new int[] { 0, 0, 0, 0, 0, 0, 3, 0 },
	new int[] { 0, 4, 0, 0, 0, 0, 0, 0 },
	new int[] { 0, 0, 0, 0, 0, 0, 0, 5 },
	new int[] { 0, 0, 0, 0, 0, 6, 0, 0 },
	new int[] { 0, 7, 0, 0, 0, 0, 0, 0 }
};

Console.WriteLine("Create variables");
var fields = Enumerable.Range(0, height)
	.Select(r => Enumerable.Range(0, width)
		.Select(c => Enumerable.Range(0, digits)
			.Select(d => solver.CreateAnonymous(Domain.BinaryInteger)).ToArray()
		).ToArray()
	).ToArray();
 
Console.WriteLine("Set known values");
for(int row = 0; row < height;++row){
	for(int column = 0; column < width; ++ column){
		if(values[row][column] > 0){
			solver.Set<Equal>(fields[row][column][values[row][column] - 1], solver.FromConstant(1));
		}
	}
}
 
Console.WriteLine("Set exactly one digit");
for(int row = 0; row < height;++row){
	for(int column = 0; column < width; ++ column){
		solver.Operation<Addition>(Enumerable.Range(0, digits).Select(d => fields[row][column][d]).ToArray())
			.Set<Equal>(solver.FromConstant(1));
	}
}

Action<IVariable[][]> setAllDifferent = numbers => {
	foreach(var bit in Enumerable.Range(0, width)){
		solver.Operation<Addition>(numbers.Select(n => n[bit]).ToArray())
			.Set<Equal>(solver.FromConstant(1));
	}
};
 
Console.WriteLine("Rows");
for(int row = 0; row < height;++row){
	setAllDifferent(fields[row]);
}
 
Console.WriteLine("Columns");
for(int column = 0; column < width; ++column){
	setAllDifferent(Enumerable.Range(0, height).Select(row => fields[row][column]).ToArray());
}
 
Console.WriteLine("Groups");
foreach(var group in Enumerable.Range(1, groups.SelectMany(g => g).Distinct().Count())){
	var fieldsInGroup = new List<IVariable[]>();
	for(int row = 0; row < height;++row){
		for(int column = 0; column < width; ++ column){
			if(groups[row][column] == group){
				fieldsInGroup.Add(fields[row][column]);
			}
		}
	}
	setAllDifferent(fieldsInGroup.ToArray());
}

Console.WriteLine("Diagonal");
setAllDifferent(Enumerable.Range(0, width).Select(i => fields[i][i]).ToArray());

solver.AddGoal("goal", solver.FromConstant(0));
solver.Solve();

for(int row = 0; row < height;++row){
	if(row % 3 == 0)Console.WriteLine("------------");
	for(int column = 0; column < width; ++ column){
		if(column % 3 == 0)Console.Write("|");
		foreach(var digit in Enumerable.Range(0, digits).Where(digit => solver.GetValue(fields[row][column][digit]) > 0.5)){
			Console.Write(digit + 1);
		}
	}
	Console.Write("|");
	Console.WriteLine();
}
Console.WriteLine("------------");

int height = 8;

int width = 8;

int digits = 8;

var groups = new int[][]{

new int[] { 1, 2, 3, 3, 3, 3, 3, 3 },

new int[] { 4, 2, 2, 5, 3, 1, 3, 1 },

new int[] { 4, 1, 2, 5, 1, 6, 6, 6 },

new int[] { 4, 2, 2, 2, 6, 6, 6, 6 },

new int[] { 4, 5, 1, 2, 7, 5, 5, 6 },

new int[] { 4, 5, 7, 7, 7, 7, 5, 8 },

new int[] { 4, 4, 7, 7, 8, 8, 5, 8 },

new int[] { 1, 4, 1, 7, 8, 8, 8, 8 }

};

var values = new int[][]{

new int[] { 0, 0, 0, 0, 0, 0, 0, 0 },

new int[] { 0, 0, 0, 1, 2, 0, 0, 0 },

new int[] { 0, 0, 0, 0, 0, 0, 0, 0 },

new int[] { 0, 0, 0, 0, 0, 0, 3, 0 },

new int[] { 0, 4, 0, 0, 0, 0, 0, 0 },

new int[] { 0, 0, 0, 0, 0, 0, 0, 5 },

new int[] { 0, 0, 0, 0, 0, 6, 0, 0 },

new int[] { 0, 7, 0, 0, 0, 0, 0, 0 }

};

Console.WriteLine("Create variables");

var fields = Enumerable.Range(0, height)

.Select(r => Enumerable.Range(0, width)

.Select(c => Enumerable.Range(0, digits)

.Select(d => solver.CreateAnonymous(Domain.BinaryInteger)).ToArray()

).ToArray()

).ToArray();

Console.WriteLine("Set known values");

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

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

if(values[row][column] > 0){

solver.Set<Equal>(fields[row][column][values[row][column] - 1], solver.FromConstant(1));

}

Console.WriteLine("Set exactly one digit");

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

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

solver.Operation<Addition>(Enumerable.Range(0, digits).Select(d => fields[row][column][d]).ToArray())

.Set<Equal>(solver.FromConstant(1));

}

Action<IVariable[][]> setAllDifferent = numbers => {

foreach(var bit in Enumerable.Range(0, width)){

solver.Operation<Addition>(numbers.Select(n => n[bit]).ToArray())

.Set<Equal>(solver.FromConstant(1));

}

};

Console.WriteLine("Rows");

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

setAllDifferent(fields[row]);

}

Console.WriteLine("Columns");

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

setAllDifferent(Enumerable.Range(0, height).Select(row => fields[row][column]).ToArray());

}

Console.WriteLine("Groups");

foreach(var group in Enumerable.Range(1, groups.SelectMany(g => g).Distinct().Count())){

var fieldsInGroup = new List<IVariable[]>();

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

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

if(groups[row][column] == group){

fieldsInGroup.Add(fields[row][column]);

}

setAllDifferent(fieldsInGroup.ToArray());

}

Console.WriteLine("Diagonal");

setAllDifferent(Enumerable.Range(0, width).Select(i => fields[i][i]).ToArray());

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

solver.Solve();

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

if(row % 3 == 0)Console.WriteLine("------------");

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

if(column % 3 == 0)Console.Write("|");

foreach(var digit in Enumerable.Range(0, digits).Where(digit => solver.GetValue(fields[row][column][digit]) > 0.5)){

Console.Write(digit + 1);

}

Console.Write("|");

Console.WriteLine();

}

Console.WriteLine("------------");

There is a couple of changes, but they are mostly mechanical.

First, we use bits instead of integers (lines 27-33). So now we have a three-dimensional array of rows, columns, and bits for each field. That’s basically it. Now we need to make sure that our code compiles and works correctly with the new data representation, but it’s nothing challenging.

We set known values by turning up a respective bit (lines 35-42).

We then make sure that there is only one bit selected in each field (lines 44-50).

Next, we prepare a helper for setting “all different”, as we need to extract bit flags. The way we do it: we take a two-dimensional array where the former dimension represents the fields, and the latter represents the digits. We then iterate over numbers from 1 to 8, extract bit for a given number from all the fields passed as an argument, and then make sure that the sum of these bits is equal to one.

We then use this helper in other parts of the code. The output is:

Tried aggregator 2 times.
MIP Presolve eliminated 73 rows and 264 columns.
MIP Presolve modified 37 coefficients.
Aggregator did 6 substitutions.
Reduced MIP has 192 rows, 242 columns, and 955 nonzeros.
Reduced MIP has 242 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.09 sec. (0.98 ticks)
Found incumbent of value 0.000000 after 0.11 sec. (2.40 ticks)

Root node processing (before b&c):
  Real time             =    0.14 sec. (2.42 ticks)
Parallel b&c, 8 threads:
  Real time             =    0.00 sec. (0.00 ticks)
  Sync time (average)   =    0.00 sec.
  Wait time (average)   =    0.00 sec.
                          ------------
Total (root+branch&cut) =    0.14 sec. (2.42 ticks)
------------
|721|634|58|
|865|123|74|
|683|512|47|
------------
|217|485|36|
|342|857|61|
|438|761|25|
------------
|154|276|83|
|576|348|12|
------------

Tried aggregator 2 times.

MIP Presolve eliminated 73 rows and 264 columns.

MIP Presolve modified 37 coefficients.

Aggregator did 6 substitutions.

Reduced MIP has 192 rows, 242 columns, and 955 nonzeros.

Reduced MIP has 242 binaries, 0 generals, 0 SOSs, and 0 indicators.

Presolve time = 0.09 sec. (0.98 ticks)

Found incumbent of value 0.000000 after 0.11 sec. (2.40 ticks)

Root node processing (before b&c):

Real time = 0.14 sec. (2.42 ticks)

Parallel b&c, 8 threads:

Real time = 0.00 sec. (0.00 ticks)

Sync time (average) = 0.00 sec.

Wait time (average) = 0.00 sec.

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

Total (root+branch&cut) = 0.14 sec. (2.42 ticks)

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

|721|634|58|

|865|123|74|

|683|512|47|

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

|217|485|36|

|342|857|61|

|438|761|25|

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

|154|276|83|

|576|348|12|

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

CPLEX managed to find the solution in 0.14 second. That’s almost 3500 times faster!