ILP Part 66 – Knight on dominoes

This is the sixtieth sixth 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 are going to solve a mix of chess and dominoes riddle. We have a board built using dominoes with at least one empty half. We want to find a chess knight route first going through empty pieces and then through ones with numbers.

Code:

var board = new string[]{
	" 0000",
	"00000",
	"00000"
};

var width = board[0].Length;
var height = board.Length;
int pieceCount = 7;

var solver = new CplexMilpSolver(new CplexMilpSolverSettings
{
	IntegerWidth = 15,
	Epsilon = 0.1,
	StoreDebugExpressions = false,
	CacheConstants = false,
	StoreDebugConstraints = false
});

Console.WriteLine("Create variables");
var fields = Enumerable.Range(0, height).Select(r => Enumerable.Range(0, width).Select(c => board[r][c] != ' ' ? new System.Dynamic.ExpandoObject() : null).ToArray()).ToArray();

Console.WriteLine("Assign pieces");	
for(int row = 0; row < height;++row){
	for(int column = 0; column < width; ++ column){
		dynamic self = fields[row][column];
		if(self == null)continue;
		
		self.Empty = solver.CreateAnonymous(Domain.BinaryInteger);
		self.PieceId = solver.CreateAnonymous(Domain.PositiveOrZeroInteger);
		self.RouteEnd = solver.CreateAnonymous(Domain.BinaryInteger);
		self.Step = solver.CreateAnonymous(Domain.PositiveOrZeroInteger);
		
		
		solver.Set<LessOrEqual>(self.PieceId, solver.FromConstant(pieceCount));
		solver.Set<GreaterOrEqual>(self.PieceId, solver.FromConstant(1));
		if(board[row][column] != ' ' && board[row][column] != '0'){
			solver.Set<Equal>(self.PieceId, solver.FromConstant(board[row][column] - '0'));
			solver.Set<Equal>(self.Empty, solver.FromConstant(0));
		}
		
		solver.Set<LessOrEqual>(self.Step, solver.FromConstant(board.SelectMany(s => s).Where(c => c != ' ').Count() - 1));
	}
}

Console.WriteLine("Exactly two parts for each piece");
for(int piece = 1; piece <= pieceCount; ++piece){
	var sum = solver.FromConstant(0);
	for(int row = 0; row < height;++row){
		for(int column = 0; column < width; ++ column){
			dynamic self = fields[row][column];
			if(self == null) continue;
			
			sum = solver.Operation<Addition>(sum, solver.Operation<IsEqual>(self.PieceId, solver.FromConstant(piece)));
		}
	}
	
	solver.Set<Equal>(sum, solver.FromConstant(2));
}

Console.WriteLine("Exactly one non-empty for each piece above 1, otherwise 2");
for(int piece = 1; piece <= pieceCount; ++piece){
	var sum = solver.FromConstant(0);
	for(int row = 0; row < height;++row){
		for(int column = 0; column < width; ++ column){
			dynamic self = fields[row][column];
			if(self == null) continue;
			
			sum = solver.Operation<Addition>(sum, solver.Operation<Conjunction>(solver.Operation<IsEqual>(self.PieceId, solver.FromConstant(piece)), self.Empty));
		}
	}
	
	solver.Set<Equal>(sum, solver.FromConstant(piece > 1 ? 1 : 2));
}

Console.WriteLine("Continous pieces");
for(int row = 0; row < height;++row){
	for(int column = 0; column < width; ++ column){
		dynamic self = fields[row][column];
		if(self == null)continue;
		
		IVariable matches = solver.FromConstant(0);
		
		if(row > 0){
			dynamic target = fields[row-1][column];
			if(target != null){
				matches = solver.Operation<Addition>(matches, solver.Operation<IsEqual>(self.PieceId, target.PieceId));
			}
		}
		if(row < height - 1){
			dynamic target = fields[row+1][column];
			if(target != null){
				matches = solver.Operation<Addition>(matches, solver.Operation<IsEqual>(self.PieceId, target.PieceId));
			}
		}
		if(column > 0){
			dynamic target = fields[row][column-1];
			if(target != null){
				matches = solver.Operation<Addition>(matches, solver.Operation<IsEqual>(self.PieceId, target.PieceId));
			}
		}
		if(column < width - 1){
			dynamic target = fields[row][column + 1];
			if(target != null){
				matches = solver.Operation<Addition>(matches, solver.Operation<IsEqual>(self.PieceId, target.PieceId));
			}
		}
		
		solver.Set<Equal>(matches, solver.FromConstant(1));
	}
}


Console.WriteLine("Two ends of the path");
solver.Set<Equal>(solver.FromConstant(2), solver.Operation<Addition>(Enumerable.Range(0, height).SelectMany(r => Enumerable.Range(0, width).Where(c => fields[r][c] != null).Select(c => (IVariable)((dynamic)fields[r][c]).RouteEnd)).ToArray()));

Console.WriteLine("Steps are different");
var steps = Enumerable.Range(0, height).SelectMany(r => Enumerable.Range(0, width).Where(c => fields[r][c] != null).Select(c => (IVariable)((dynamic)fields[r][c]).Step)).ToArray();
solver.Set<AllDifferent>(steps[0], steps.Skip(1).ToArray());

Console.WriteLine("Knight moves");
for(int row = 0; row < height;++row){
	for(int column = 0; column < width; ++ column){
		dynamic self = fields[row][column];
		if(self == null)continue;
		
		List<IVariable> neighbours = new List<IVariable>();
		
		for(int i=-2;i<=2;++i){
			for(int j=-2;j<=2;++j){
				if(Math.Abs(i%3) + Math.Abs(j%3) == 3){
					if(row + i >= 0 && row + i < height && column + j >= 0 && column + j < width && fields[row+i][column+j] != null){
						neighbours.Add((IVariable)((dynamic)fields[row+i][column+j]).Step);
					}
				}
			}
		}
		
		var less = solver.Operation<Addition>(self.Step, solver.FromConstant(-1));
		var lessByOne = solver.Operation<Addition>((IVariable[])neighbours.Select(n => (IVariable)solver.Operation<IsEqual>(less, n)).ToArray());
		
		var greater = solver.Operation<Addition>(self.Step, solver.FromConstant(1));
		var greaterByOne = solver.Operation<Addition>((IVariable[])neighbours.Select(n => (IVariable)solver.Operation<IsEqual>(greater, n)).ToArray());
		
		solver.Set<Equal>(solver.FromConstant(1), solver.Operation<MaterialImplication>(self.RouteEnd, solver.Operation<IsEqual>(solver.FromConstant(1), solver.Operation<Addition>(lessByOne, greaterByOne))));
		
		solver.Set<Equal>(solver.FromConstant(1), solver.Operation<MaterialImplication>(solver.Operation<BinaryNegation>(self.RouteEnd), solver.Operation<IsEqual>(solver.FromConstant(1), lessByOne)));
		solver.Set<Equal>(solver.FromConstant(1), solver.Operation<MaterialImplication>(solver.Operation<BinaryNegation>(self.RouteEnd), solver.Operation<IsEqual>(solver.FromConstant(1), greaterByOne)));
	}
}

Console.WriteLine("First jump over empty fields");	
for(int row = 0; row < height;++row){
	for(int column = 0; column < width; ++ column){
		dynamic self = fields[row][column];
		if(self == null)continue;
		
		solver.Set<Equal>(solver.FromConstant(1), solver.Operation<MaterialImplication>(self.Empty, solver.Operation<IsLessOrEqual>(self.Step, solver.FromConstant(pieceCount))));
	}
}

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

for(int row = 0; row < height;++row){
	if(row == 0){
		for(int column = 0; column < width; ++ column){
			dynamic self = fields[row][column];
			Console.Write(self == null ? "  " : " -");
		}
		Console.WriteLine();
	}
	
	for(int column = 0; column < width; ++ column){
		dynamic self = fields[row][column];
		if(column == 0){
			Console.Write(self == null ? " " : "|");
		}
		
		Console.Write(self == null ? " " : (solver.GetValue(self.Empty) > 0.5 ? " " : Math.Round(solver.GetValue(self.PieceId))));
	
		if((self != null && column == width - 1) || (self != null && fields[row][column + 1] == null) || (self != null && Math.Round(solver.GetValue(self.PieceId)) != Math.Round(solver.GetValue(((dynamic)fields[row][column+1]).PieceId))) || (self == null && column < width - 1 && fields[row][column + 1] != null)){
			Console.Write("|");
		}else{
			Console.Write(" ");
		}
	}
	Console.WriteLine();
	
	for(int column = 0; column < width; ++ column){
		dynamic self = fields[row][column];
		
		if((self != null && row == height - 1) || (self != null && fields[row + 1][column] == null) || (self != null && Math.Round(solver.GetValue(self.PieceId)) != Math.Round(solver.GetValue(((dynamic)fields[row + 1][column]).PieceId))) || (self == null && row < height - 1 && fields[row + 1][column] != null)){
			Console.Write(" -");
		}else{
			Console.Write("  ");
		}
	}
	
	Console.WriteLine();
}


for(int row = 0; row < height;++row){
	if(row == 0){
		for(int column = 0; column < width; ++ column){
			dynamic self = fields[row][column];
			Console.Write(self == null ? "  " : " -");
		}
		Console.WriteLine();
	}
	
	for(int column = 0; column < width; ++ column){
		dynamic self = fields[row][column];
		if(column == 0){
			Console.Write(self == null ? " " : "|");
		}
		
		Console.Write(self == null ? " " : Math.Round(solver.GetValue(self.PieceId)));
	
		if((self != null && column == width - 1) || (self != null && fields[row][column + 1] == null) || (self != null && Math.Round(solver.GetValue(self.PieceId)) != Math.Round(solver.GetValue(((dynamic)fields[row][column+1]).PieceId))) || (self == null && column < width - 1 && fields[row][column + 1] != null)){
			Console.Write("|");
		}else{
			Console.Write(" ");
		}
	}
	Console.WriteLine();
	
	for(int column = 0; column < width; ++ column){
		dynamic self = fields[row][column];
		
		if((self != null && row == height - 1) || (self != null && fields[row + 1][column] == null) || (self != null && Math.Round(solver.GetValue(self.PieceId)) != Math.Round(solver.GetValue(((dynamic)fields[row + 1][column]).PieceId))) || (self == null && row < height - 1 && fields[row + 1][column] != null)){
			Console.Write(" -");
		}else{
			Console.Write("  ");
		}
	}
	
	Console.WriteLine();
}


for(int row = 0; row < height;++row){
	if(row == 0){
		for(int column = 0; column < width; ++ column){
			dynamic self = fields[row][column];
			Console.Write(self == null ? "   " : " --");
		}
		Console.WriteLine();
	}
	
	for(int column = 0; column < width; ++ column){
		dynamic self = fields[row][column];
		if(column == 0){
			Console.Write(self == null ? " " : "|");
		}
		
		Console.Write(self == null ? "  " : ((int)Math.Round(solver.GetValue(self.Step))).ToString("D2"));
	
		if((self != null && column == width - 1) || (self != null && fields[row][column + 1] == null) || (self != null && Math.Round(solver.GetValue(self.PieceId)) != Math.Round(solver.GetValue(((dynamic)fields[row][column+1]).PieceId))) || (self == null && column < width - 1 && fields[row][column + 1] != null)){
			Console.Write("|");
		}else{
			Console.Write(" ");
		}
	}
	Console.WriteLine();
	
	for(int column = 0; column < width; ++ column){
		dynamic self = fields[row][column];
		
		if((self != null && row == height - 1) || (self != null && fields[row + 1][column] == null) || (self != null && Math.Round(solver.GetValue(self.PieceId)) != Math.Round(solver.GetValue(((dynamic)fields[row + 1][column]).PieceId))) || (self == null && row < height - 1 && fields[row + 1][column] != null)){
			Console.Write(" --");
		}else{
			Console.Write("   ");
		}
	}
	
	Console.WriteLine();
}


for(int row = 0; row < height;++row){
	if(row == 0){
		for(int column = 0; column < width; ++ column){
			dynamic self = fields[row][column];
			Console.Write(self == null ? "   " : " --");
		}
		Console.WriteLine();
	}
	
	for(int column = 0; column < width; ++ column){
		dynamic self = fields[row][column];
		if(column == 0){
			Console.Write(self == null ? " " : "|");
		}
		
		var step = self == null ? 0 : (int)Math.Round(solver.GetValue(self.Step));
		Console.Write(self == null || step <= pieceCount ? "  " : (step - pieceCount).ToString("D2"));
	
		if((self != null && column == width - 1) || (self != null && fields[row][column + 1] == null) || (self != null && Math.Round(solver.GetValue(self.PieceId)) != Math.Round(solver.GetValue(((dynamic)fields[row][column+1]).PieceId))) || (self == null && column < width - 1 && fields[row][column + 1] != null)){
			Console.Write("|");
		}else{
			Console.Write(" ");
		}
	}
	Console.WriteLine();
	
	for(int column = 0; column < width; ++ column){
		dynamic self = fields[row][column];
		
		if((self != null && row == height - 1) || (self != null && fields[row + 1][column] == null) || (self != null && Math.Round(solver.GetValue(self.PieceId)) != Math.Round(solver.GetValue(((dynamic)fields[row + 1][column]).PieceId))) || (self == null && row < height - 1 && fields[row + 1][column] != null)){
			Console.Write(" --");
		}else{
			Console.Write("   ");
		}
	}
	
	Console.WriteLine();
}

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

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301

302

303

304

305

306

307

308

309

310

311

312

313

314

315

316

317

318

319

var board = new string[]{

" 0000",

"00000",

"00000"

};

var width = board[0].Length;

var height = board.Length;

int pieceCount = 7;

var solver = new CplexMilpSolver(new CplexMilpSolverSettings

{

IntegerWidth = 15,

Epsilon = 0.1,

StoreDebugExpressions = false,

CacheConstants = false,

StoreDebugConstraints = false

});

Console.WriteLine("Create variables");

var fields = Enumerable.Range(0, height).Select(r => Enumerable.Range(0, width).Select(c => board[r][c] != ' ' ? new System.Dynamic.ExpandoObject() : null).ToArray()).ToArray();

Console.WriteLine("Assign pieces");

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

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

dynamic self = fields[row][column];

if(self == null)continue;

self.Empty = solver.CreateAnonymous(Domain.BinaryInteger);

self.PieceId = solver.CreateAnonymous(Domain.PositiveOrZeroInteger);

self.RouteEnd = solver.CreateAnonymous(Domain.BinaryInteger);

self.Step = solver.CreateAnonymous(Domain.PositiveOrZeroInteger);

solver.Set<LessOrEqual>(self.PieceId, solver.FromConstant(pieceCount));

solver.Set<GreaterOrEqual>(self.PieceId, solver.FromConstant(1));

if(board[row][column] != ' ' && board[row][column] != '0'){

solver.Set<Equal>(self.PieceId, solver.FromConstant(board[row][column] - '0'));

solver.Set<Equal>(self.Empty, solver.FromConstant(0));

}

solver.Set<LessOrEqual>(self.Step, solver.FromConstant(board.SelectMany(s => s).Where(c => c != ' ').Count() - 1));

}

Console.WriteLine("Exactly two parts for each piece");

for(int piece = 1; piece <= pieceCount; ++piece){

var sum = solver.FromConstant(0);

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

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

dynamic self = fields[row][column];

if(self == null) continue;

sum = solver.Operation<Addition>(sum, solver.Operation<IsEqual>(self.PieceId, solver.FromConstant(piece)));

}

solver.Set<Equal>(sum, solver.FromConstant(2));

}

Console.WriteLine("Exactly one non-empty for each piece above 1, otherwise 2");

for(int piece = 1; piece <= pieceCount; ++piece){

var sum = solver.FromConstant(0);

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

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

dynamic self = fields[row][column];

if(self == null) continue;

sum = solver.Operation<Addition>(sum, solver.Operation<Conjunction>(solver.Operation<IsEqual>(self.PieceId, solver.FromConstant(piece)), self.Empty));

}

solver.Set<Equal>(sum, solver.FromConstant(piece > 1 ? 1 : 2));

}

Console.WriteLine("Continous pieces");

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

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

dynamic self = fields[row][column];

if(self == null)continue;

IVariable matches = solver.FromConstant(0);

if(row > 0){

dynamic target = fields[row-1][column];

if(target != null){

matches = solver.Operation<Addition>(matches, solver.Operation<IsEqual>(self.PieceId, target.PieceId));

}

if(row < height - 1){

dynamic target = fields[row+1][column];

if(target != null){

matches = solver.Operation<Addition>(matches, solver.Operation<IsEqual>(self.PieceId, target.PieceId));

}

if(column > 0){

dynamic target = fields[row][column-1];

if(target != null){

matches = solver.Operation<Addition>(matches, solver.Operation<IsEqual>(self.PieceId, target.PieceId));

}

if(column < width - 1){

dynamic target = fields[row][column + 1];

if(target != null){

matches = solver.Operation<Addition>(matches, solver.Operation<IsEqual>(self.PieceId, target.PieceId));

}

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

}

Console.WriteLine("Two ends of the path");

solver.Set<Equal>(solver.FromConstant(2), solver.Operation<Addition>(Enumerable.Range(0, height).SelectMany(r => Enumerable.Range(0, width).Where(c => fields[r][c] != null).Select(c => (IVariable)((dynamic)fields[r][c]).RouteEnd)).ToArray()));

Console.WriteLine("Steps are different");

var steps = Enumerable.Range(0, height).SelectMany(r => Enumerable.Range(0, width).Where(c => fields[r][c] != null).Select(c => (IVariable)((dynamic)fields[r][c]).Step)).ToArray();

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

Console.WriteLine("Knight moves");

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

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

dynamic self = fields[row][column];

if(self == null)continue;

List<IVariable> neighbours = new List<IVariable>();

for(int i=-2;i<=2;++i){

for(int j=-2;j<=2;++j){

if(Math.Abs(i%3) + Math.Abs(j%3) == 3){

if(row + i >= 0 && row + i < height && column + j >= 0 && column + j < width && fields[row+i][column+j] != null){

neighbours.Add((IVariable)((dynamic)fields[row+i][column+j]).Step);

}

var less = solver.Operation<Addition>(self.Step, solver.FromConstant(-1));

var lessByOne = solver.Operation<Addition>((IVariable[])neighbours.Select(n => (IVariable)solver.Operation<IsEqual>(less, n)).ToArray());

var greater = solver.Operation<Addition>(self.Step, solver.FromConstant(1));

var greaterByOne = solver.Operation<Addition>((IVariable[])neighbours.Select(n => (IVariable)solver.Operation<IsEqual>(greater, n)).ToArray());

solver.Set<Equal>(solver.FromConstant(1), solver.Operation<MaterialImplication>(self.RouteEnd, solver.Operation<IsEqual>(solver.FromConstant(1), solver.Operation<Addition>(lessByOne, greaterByOne))));

solver.Set<Equal>(solver.FromConstant(1), solver.Operation<MaterialImplication>(solver.Operation<BinaryNegation>(self.RouteEnd), solver.Operation<IsEqual>(solver.FromConstant(1), lessByOne)));

solver.Set<Equal>(solver.FromConstant(1), solver.Operation<MaterialImplication>(solver.Operation<BinaryNegation>(self.RouteEnd), solver.Operation<IsEqual>(solver.FromConstant(1), greaterByOne)));

}

Console.WriteLine("First jump over empty fields");

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

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

dynamic self = fields[row][column];

if(self == null)continue;

solver.Set<Equal>(solver.FromConstant(1), solver.Operation<MaterialImplication>(self.Empty, solver.Operation<IsLessOrEqual>(self.Step, solver.FromConstant(pieceCount))));

}

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

solver.Solve();

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

if(row == 0){

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

dynamic self = fields[row][column];

Console.Write(self == null ? " " : " -");

}

Console.WriteLine();

}

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

dynamic self = fields[row][column];

if(column == 0){

Console.Write(self == null ? " " : "|");

}

Console.Write(self == null ? " " : (solver.GetValue(self.Empty) > 0.5 ? " " : Math.Round(solver.GetValue(self.PieceId))));

if((self != null && column == width - 1) || (self != null && fields[row][column + 1] == null) || (self != null && Math.Round(solver.GetValue(self.PieceId)) != Math.Round(solver.GetValue(((dynamic)fields[row][column+1]).PieceId))) || (self == null && column < width - 1 && fields[row][column + 1] != null)){

Console.Write("|");

}else{

Console.Write(" ");

}

Console.WriteLine();

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

dynamic self = fields[row][column];

if((self != null && row == height - 1) || (self != null && fields[row + 1][column] == null) || (self != null && Math.Round(solver.GetValue(self.PieceId)) != Math.Round(solver.GetValue(((dynamic)fields[row + 1][column]).PieceId))) || (self == null && row < height - 1 && fields[row + 1][column] != null)){

Console.Write(" -");

}else{

Console.Write(" ");

}

Console.WriteLine();

}

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

if(row == 0){

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

dynamic self = fields[row][column];

Console.Write(self == null ? " " : " -");

}

Console.WriteLine();

}

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

dynamic self = fields[row][column];

if(column == 0){

Console.Write(self == null ? " " : "|");

}

Console.Write(self == null ? " " : Math.Round(solver.GetValue(self.PieceId)));

Console.Write("|");

}else{

Console.Write(" ");

}

Console.WriteLine();

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

dynamic self = fields[row][column];

Console.Write(" -");

}else{

Console.Write(" ");

}

Console.WriteLine();

}

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

if(row == 0){

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

dynamic self = fields[row][column];

Console.Write(self == null ? " " : " --");

}

Console.WriteLine();

}

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

dynamic self = fields[row][column];

if(column == 0){

Console.Write(self == null ? " " : "|");

}

Console.Write(self == null ? " " : ((int)Math.Round(solver.GetValue(self.Step))).ToString("D2"));

Console.Write("|");

}else{

Console.Write(" ");

}

Console.WriteLine();

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

dynamic self = fields[row][column];

Console.Write(" --");

}else{

Console.Write(" ");

}

Console.WriteLine();

}

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

if(row == 0){

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

dynamic self = fields[row][column];

Console.Write(self == null ? " " : " --");

}

Console.WriteLine();

}

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

dynamic self = fields[row][column];

if(column == 0){

Console.Write(self == null ? " " : "|");

}

var step = self == null ? 0 : (int)Math.Round(solver.GetValue(self.Step));

Console.Write(self == null || step <= pieceCount ? " " : (step - pieceCount).ToString("D2"));

Console.Write("|");

}else{

Console.Write(" ");

}

Console.WriteLine();

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

dynamic self = fields[row][column];

Console.Write(" --");

}else{

Console.Write(" ");

}

Console.WriteLine();

}

Let’s go through this step by step.

We start with board in lines 1-5. Spaces represent missing fields, zeroes represent fields we don’t know anything about. You can put other numbers there if you wish to test prefilled boards.

In line 9 we specify how many pieces we have. There are 7 of them, one of which has both halves empty.

Next, we create fields in lines 23-42. Each field has 4 variables: whether given field is empty half of the domino piece, its piece identifier, and two variables for creating the knight route (route end indicating whether route ends here and step number). We also set some ranges in lines 35-44.

Next, couple obvious requirements. First, each domino piece must have exactly two parts (lines 46-59). Next, each domino piece must have one empty half (with exception of totally empty domino) in lines 61-74. Finally, halves must be together on the board (lines 76-111).

Next, we define the path. We start with specifying that it must start end end somewhere (lines 114-115).

Next, we number fields on the path (lines 117-119).

Finally, we define knight moves. We get knight neighbours (lines 127-137), and then specify the numbering. If this is an inner field on the path, then it must have exactly one neighbour with lower number and one neighbour with higher number (lines 147-148). If it’s starting/ending field then it must have exactly one neighbour with matching number (line 145). Last part is in lines 152-160 where we specify that knight moves over empty pieces first.

At the end we print couple representations of the board (which is tricky as well!). Output:

Tried aggregator 2 times.
MIP Presolve eliminated 596 rows and 294 columns.
MIP Presolve modified 3785 coefficients.
Aggregator did 957 substitutions.
Reduced MIP has 2635 rows, 1283 columns, and 7466 nonzeros.
Reduced MIP has 1255 binaries, 28 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.00 sec. (7.84 ticks)
Probing fixed 30 vars, tightened 0 bounds.
Probing changed sense of 91 constraints.
Probing time = 0.02 sec. (11.32 ticks)
Tried aggregator 2 times.
MIP Presolve eliminated 634 rows and 330 columns.
MIP Presolve modified 56 coefficients.
Aggregator did 91 substitutions.
Reduced MIP has 1910 rows, 862 columns, and 5800 nonzeros.
Reduced MIP has 834 binaries, 28 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.00 sec. (7.77 ticks)
Probing time = 0.02 sec. (4.61 ticks)
Tried aggregator 1 time.
MIP Presolve eliminated 74 rows and 37 columns.
Reduced MIP has 1836 rows, 825 columns, and 5578 nonzeros.
Reduced MIP has 797 binaries, 28 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.01 sec. (4.35 ticks)
Probing time = 0.02 sec. (4.86 ticks)
Clique table members: 3614.
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. (16.14 ticks)

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

      0     0        0.0000   375                      0.0000      685
      0     0        0.0000   253                   Cuts: 357      996
      0     0        0.0000   339                   Cuts: 483     1373
      0     0        0.0000   216                   Cuts: 137     1548
      0     0        0.0000   213                   Cuts: 238     1765
      0     2        0.0000   170                      0.0000     1765
Elapsed time = 1.00 sec. (476.37 ticks, tree = 0.01 MB, solutions = 0)
    157    96    infeasible                            0.0000    17542
    527   166        0.0000   135                      0.0000    44188
    858   217        0.0000   335                      0.0000    71434
   1043   252        0.0000   407                      0.0000    93256
   1170   239        0.0000   339                      0.0000   113124
   1382   281        0.0000   320                      0.0000   141997
   1534   283    infeasible                            0.0000   164947
   1857   305        0.0000   178                      0.0000   194642
*  1945   252      integral     0        0.0000        0.0000   206876    0.00%

GUB cover cuts applied:  18
Clique cuts applied:  153
Cover cuts applied:  230
Implied bound cuts applied:  883
Mixed integer rounding cuts applied:  38
Zero-half cuts applied:  68
Lift and project cuts applied:  1
Gomory fractional cuts applied:  5

Root node processing (before b&c):
  Real time             =    1.02 sec. (475.27 ticks)
Parallel b&c, 8 threads:
  Real time             =    3.58 sec. (2246.65 ticks)
  Sync time (average)   =    0.43 sec.
  Wait time (average)   =    0.00 sec.
                          ------------
Total (root+branch&cut) =    4.59 sec. (2721.92 ticks)
   - - - -
  |  2|   |
 - - - - -
|6  | |7|4|
 - -
|  3|5| | |
 - - - - -

   - - - -
  |2 2|1 1|
 - - - - -
|6 6|5|7|4|
 - -
|3 3|5|7|4|
 - - - - -

    -- -- -- --
   |07 10|01 04|
 -- -- -- -- --
|11 02|05|08|13|
 -- --
|06 09|12|03|00|
 -- -- -- -- --

    -- -- -- --
   |   03|     |
 -- -- -- -- --
|04   |  |01|06|
 -- --
|   02|05|  |  |
 -- -- -- -- --

Tried aggregator 2 times.

MIP Presolve eliminated 596 rows and 294 columns.

MIP Presolve modified 3785 coefficients.

Aggregator did 957 substitutions.

Reduced MIP has 2635 rows, 1283 columns, and 7466 nonzeros.

Reduced MIP has 1255 binaries, 28 generals, 0 SOSs, and 0 indicators.

Presolve time = 0.00 sec. (7.84 ticks)

Probing fixed 30 vars, tightened 0 bounds.

Probing changed sense of 91 constraints.

Probing time = 0.02 sec. (11.32 ticks)

Tried aggregator 2 times.

MIP Presolve eliminated 634 rows and 330 columns.

MIP Presolve modified 56 coefficients.

Aggregator did 91 substitutions.

Reduced MIP has 1910 rows, 862 columns, and 5800 nonzeros.

Reduced MIP has 834 binaries, 28 generals, 0 SOSs, and 0 indicators.

Presolve time = 0.00 sec. (7.77 ticks)

Probing time = 0.02 sec. (4.61 ticks)

Tried aggregator 1 time.

MIP Presolve eliminated 74 rows and 37 columns.

Reduced MIP has 1836 rows, 825 columns, and 5578 nonzeros.

Reduced MIP has 797 binaries, 28 generals, 0 SOSs, and 0 indicators.

Presolve time = 0.01 sec. (4.35 ticks)

Probing time = 0.02 sec. (4.86 ticks)

Clique table members: 3614.

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. (16.14 ticks)

Nodes Cuts/

Node Left Objective IInf Best Integer Best Bound ItCnt Gap

0 0 0.0000 375 0.0000 685

0 0 0.0000 253 Cuts: 357 996

0 0 0.0000 339 Cuts: 483 1373

0 0 0.0000 216 Cuts: 137 1548

0 0 0.0000 213 Cuts: 238 1765

0 2 0.0000 170 0.0000 1765

Elapsed time = 1.00 sec. (476.37 ticks, tree = 0.01 MB, solutions = 0)

157 96 infeasible 0.0000 17542

527 166 0.0000 135 0.0000 44188

858 217 0.0000 335 0.0000 71434

1043 252 0.0000 407 0.0000 93256

1170 239 0.0000 339 0.0000 113124

1382 281 0.0000 320 0.0000 141997

1534 283 infeasible 0.0000 164947

1857 305 0.0000 178 0.0000 194642

* 1945 252 integral 0 0.0000 0.0000 206876 0.00%

GUB cover cuts applied: 18

Clique cuts applied: 153

Cover cuts applied: 230

Implied bound cuts applied: 883

Mixed integer rounding cuts applied: 38

Zero-half cuts applied: 68

Lift and project cuts applied: 1

Gomory fractional cuts applied: 5

Root node processing (before b&c):

Real time = 1.02 sec. (475.27 ticks)

Parallel b&c, 8 threads:

Real time = 3.58 sec. (2246.65 ticks)

Sync time (average) = 0.43 sec.

Wait time (average) = 0.00 sec.

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

Total (root+branch&cut) = 4.59 sec. (2721.92 ticks)

- - - -

| 2| |

- - - - -

|6 | |7|4|

- -

| 3|5| | |

- - - - -

- - - -

|2 2|1 1|

- - - - -

|6 6|5|7|4|

- -

|3 3|5|7|4|

- - - - -

-- -- -- --

|07 10|01 04|

-- -- -- -- --

|11 02|05|08|13|

-- --

|06 09|12|03|00|

-- -- -- -- --

-- -- -- --

| 03| |

-- -- -- -- --

|04 | |01|06|

-- --

| 02|05| | |

-- -- -- -- --

First board shows the piece ids with halves. Second board shows piece ids together (so you can make sure pieces are continuous). Third board shows knight’s path. Finally, last board shows the answer to the riddle. There are many answers here so you can come up with your own.