ILP Part 85 — Lying riddle – Random IT Utensils

This is the eightieth fifth 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 Lying riddle (Kłamigłówka).

We have a board split into parts. Each part has some numbers in it. A number indicates how many neighbouring fields (up, down, left, or right) are selected. One number in each part lies.

We need to select fields according to numbers. However, two selected fields cannot be neighbours and if they touch corners then they can’t split the board into multiple parts.

Solution:

using System;
using System.Collections.Generic;
using System.Linq;
using MilpManager.Abstraction;
using MilpManager.Utilities;
using CplexMilpManager.Implementation;

namespace LyingRiddle
{
    public class Program
    {
        public static void Start(IMilpSolver solver)
        {
			var parts = new int[,]{
			{1, 1, 2, 2, 2, 2, 2, 3, 3, 3},
			{1, 1, 4, 5, 5, 5, 5, 3, 3, 3},
			{1, 1, 4, 5, 5, 5, 5, 3, 3, 3},
			{1, 1, 4, 6, 6, 6, 7, 7, 7, 7},
			{8, 8, 8, 6, 6, 6, 7, 7, 7, 7},
			{8, 8, 8, 6, 6, 6, 7, 7, 7, 7},
			{8, 8, 8, 6, 6, 6, 9, 9, 10, 10},
			{11, 11, 11, 11, 12, 12, 9, 9, 10, 10},
			{13, 13, 13, 13, 12, 12, 9, 9, 10, 10},
			{13, 13, 13, 13, 12, 12, 9, 9, 10, 10}
		};

			var numbers = new int[,] {
			{-1, 1, -1, 2, -1, 2, -1, 2, -1, 2},
			{2, -1, 1, -1, -1, -1, 2, -1, 2, -1},
			{-1, 3, -1, 3, -1, 3, -1, 3, -1, -1},
			{2, -1, 1, -1, -1, -1, -1, 1, 2, -1},
			{-1, 3, -1, 3, 2, -1, -1, -1, 3, -1},
			{-1, -1, 3, -1, 3, -1, 2, -1, -1, -1},
			{-1, -1, -1, -1, -1, -1, -1, -1, -1, 1},
			{2, -1, -1, 1, -1, 2, 3, -1, 2, -1},
			{-1, 3, -1, -1, -1, -1, -1, -1, -1, -1},
			{-1, -1, 2, -1, -1, 2, -1, 2, -1, 2}
		};

			int height = 10;
			int width = 10;

			var board = Enumerable.Range(0, height).Select(h => Enumerable.Range(0, width).Select(w => new Field
			{
				Part = parts[h, w],
				Number = numbers[h, w],
				Selected = solver.CreateAnonymous(Domain.BinaryInteger),
				IsLying = solver.CreateAnonymous(Domain.BinaryInteger),
				Id = solver.CreateAnonymous(Domain.PositiveOrZeroInteger),
				LowerCount = solver.FromConstant(-1),
				Neighbours = new List<Field>()
			}).ToArray()).ToArray();

			// Calculate neighbours
			for (int h = 0; h < height; ++h)
			{
				for (int w = 0; w < width; ++w)
				{
					if (h > 0) board[h][w].Neighbours.Add(board[h - 1][w]);
					if (h < height - 1) board[h][w].Neighbours.Add(board[h + 1][w]);
					if (w > 0) board[h][w].Neighbours.Add(board[h][w - 1]);
					if (w < width - 1) board[h][w].Neighbours.Add(board[h][w + 1]);
				}
			}





			// Exactly one lier in each part
			foreach (var part in Enumerable.Range(0, board.SelectMany(f => f).Max(f => f.Part)))
			{
				var partFields = board
							.SelectMany(f => f)
							.Where(f => f.Number != -1)
							.Where(f => f.Part == part + 1)
							.Select(f => f.IsLying).ToArray();
				solver.Set<Equal>(
					solver.FromConstant(1),
					solver.Operation<Addition>(partFields)
				);
			}

			// Field with number cannot be selected
			foreach (var field in board.SelectMany(f => f).Where(f => f.Number != -1))
			{
				field.Selected.Set<Equal>(solver.FromConstant(0));
			}

			// Selected fields cannot touch edges
			for (int h = 0; h < height; ++h)
			{
				for (int w = 0; w < width; ++w)
				{
					foreach (var neighbour in board[h][w].Neighbours)
					{
						neighbour.Selected.Operation<Conjunction>(board[h][w].Selected).Set<Equal>(solver.FromConstant(0));
					}
				}
			}

			// Fields with number must have correct neighbours count
			for (int h = 0; h < height; ++h)
			{
				for (int w = 0; w < width; ++w)
				{
					if (board[h][w].Number != -1)
					{
						solver.Set<Equal>(
							solver.Operation<Addition>(board[h][w].Neighbours.Select(x => x.Selected).ToArray())
								.Operation<IsEqual>(solver.FromConstant(board[h][w].Number)),
							solver.Operation<BinaryNegation>(board[h][w].IsLying)
						);
					}
				}
			}





			// Make sure field is not isolated
			for (int h = 0; h < height; ++h)
			{
				for (int w = 0; w < width; ++w)
				{
					solver.Set<LessOrEqual>(
						solver.Operation<Addition>(board[h][w].Neighbours.Select(n => n.Selected).ToArray()),
						solver.FromConstant(board[h][w].Neighbours.Count - 1)
					);
				}
			}

			// Make sure that we do not split the board
			board[height - 1][0].Id.Set<Equal>(solver.FromConstant(1));
			board[height - 1][0].Selected.Set<Equal>(solver.FromConstant(0));
			for (int h = 0; h < height; ++h)
			{
				for (int w = 0; w < width; ++w)
				{

					// Calculate lower count
					board[h][w].LowerCount = solver.Operation<Addition>(
						board[h][w].Neighbours
							.Select(n => n.Id.Operation<IsLessThan>(board[h][w].Id))
							.ToArray()
					);

					// Id is limited
					var highestId = 30;
					board[h][w].Id.Set<LessOrEqual>(solver.FromConstant(highestId));

					// Selected fields have super big id
					solver.Set<Equal>(
						solver.FromConstant(1),
						board[h][w].Selected.Operation<MaterialImplication>(solver.Operation<IsEqual>(board[h][w].Id, solver.FromConstant(highestId)))
					);

					// Fields next to each other should differ by one unless any of them is selected
					foreach (var neighbour in board[h][w].Neighbours)
					{
						solver.Operation<Disjunction>(board[h][w].Selected, neighbour.Selected).Operation<BinaryNegation>().Operation<MaterialImplication>(
							solver.Operation<AbsoluteValue>(solver.Operation<Subtraction>(board[h][w].Id, neighbour.Id)).Operation<IsEqual>(solver.FromConstant(1))
						).Set<Equal>(solver.FromConstant(1));
					}

					// Only one field can have no lower neighbours, all others must have a path
					if (h == height - 1 && w == 0)
					{
						board[h][w].LowerCount.Set<Equal>(solver.FromConstant(0));
					}
					else
					{
						board[h][w].LowerCount.Set<GreaterOrEqual>(solver.FromConstant(1));
					}
				}
			}


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

			for (int h = 0; h < height; ++h)
			{
				for (int w = 0; w < width; ++w)
				{
					if (numbers[h, w] != -1)
					{
						Console.Write(numbers[h, w]);
					}
					else
					{
						Console.Write((int)solver.GetValue(board[h][w].Selected) == 1 ? "X" : " ");
					}
				}
				Console.WriteLine();
			}
			Console.WriteLine();
		}


		static void Main()
		{
			var solver = new CplexMilpSolver(new CplexMilpSolverSettings
			{
				IntegerWidth = 5,
				Epsilon = 0.00001,
				StoreDebugExpressions = false,
				CacheConstants = false,
				StoreDebugConstraints = false
			});
			Start(solver);
		}
	}

	public class Field
	{
		public int Part { get; set; }
		public int Number { get; set; }
		public IVariable Selected { get; set; }
		public IVariable IsLying { get; set; }
		public IVariable Id { get; set; }
		public IVariable LowerCount { get; set; }
		public List<Field> Neighbours { get; set; }
	}

}

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

using System;

using System.Collections.Generic;

using System.Linq;

using MilpManager.Abstraction;

using MilpManager.Utilities;

using CplexMilpManager.Implementation;

namespace LyingRiddle

{

public class Program

{

public static void Start(IMilpSolver solver)

{

var parts = new int[,]{

{1, 1, 2, 2, 2, 2, 2, 3, 3, 3},

{1, 1, 4, 5, 5, 5, 5, 3, 3, 3},

{1, 1, 4, 6, 6, 6, 7, 7, 7, 7},

{8, 8, 8, 6, 6, 6, 7, 7, 7, 7},

{8, 8, 8, 6, 6, 6, 9, 9, 10, 10},

{11, 11, 11, 11, 12, 12, 9, 9, 10, 10},

{13, 13, 13, 13, 12, 12, 9, 9, 10, 10},

{13, 13, 13, 13, 12, 12, 9, 9, 10, 10}

};

var numbers = new int[,] {

{-1, 1, -1, 2, -1, 2, -1, 2, -1, 2},

{2, -1, 1, -1, -1, -1, 2, -1, 2, -1},

{-1, 3, -1, 3, -1, 3, -1, 3, -1, -1},

{2, -1, 1, -1, -1, -1, -1, 1, 2, -1},

{-1, 3, -1, 3, 2, -1, -1, -1, 3, -1},

{-1, -1, 3, -1, 3, -1, 2, -1, -1, -1},

{-1, -1, -1, -1, -1, -1, -1, -1, -1, 1},

{2, -1, -1, 1, -1, 2, 3, -1, 2, -1},

{-1, 3, -1, -1, -1, -1, -1, -1, -1, -1},

{-1, -1, 2, -1, -1, 2, -1, 2, -1, 2}

};

int height = 10;

int width = 10;

var board = Enumerable.Range(0, height).Select(h => Enumerable.Range(0, width).Select(w => new Field

{

Part = parts[h, w],

Number = numbers[h, w],

Selected = solver.CreateAnonymous(Domain.BinaryInteger),

IsLying = solver.CreateAnonymous(Domain.BinaryInteger),

Id = solver.CreateAnonymous(Domain.PositiveOrZeroInteger),

LowerCount = solver.FromConstant(-1),

Neighbours = new List<Field>()

}).ToArray()).ToArray();

// Calculate neighbours

for (int h = 0; h < height; ++h)

{

for (int w = 0; w < width; ++w)

{

if (h > 0) board[h][w].Neighbours.Add(board[h - 1][w]);

if (h < height - 1) board[h][w].Neighbours.Add(board[h + 1][w]);

if (w > 0) board[h][w].Neighbours.Add(board[h][w - 1]);

if (w < width - 1) board[h][w].Neighbours.Add(board[h][w + 1]);

}

// Exactly one lier in each part

foreach (var part in Enumerable.Range(0, board.SelectMany(f => f).Max(f => f.Part)))

{

var partFields = board

.SelectMany(f => f)

.Where(f => f.Number != -1)

.Where(f => f.Part == part + 1)

.Select(f => f.IsLying).ToArray();

solver.Set<Equal>(

solver.FromConstant(1),

solver.Operation<Addition>(partFields)

);

}

// Field with number cannot be selected

foreach (var field in board.SelectMany(f => f).Where(f => f.Number != -1))

{

field.Selected.Set<Equal>(solver.FromConstant(0));

}

// Selected fields cannot touch edges

for (int h = 0; h < height; ++h)

{

for (int w = 0; w < width; ++w)

{

foreach (var neighbour in board[h][w].Neighbours)

{

neighbour.Selected.Operation<Conjunction>(board[h][w].Selected).Set<Equal>(solver.FromConstant(0));

}

// Fields with number must have correct neighbours count

for (int h = 0; h < height; ++h)

{

for (int w = 0; w < width; ++w)

{

if (board[h][w].Number != -1)

{

solver.Set<Equal>(

solver.Operation<Addition>(board[h][w].Neighbours.Select(x => x.Selected).ToArray())

.Operation<IsEqual>(solver.FromConstant(board[h][w].Number)),

solver.Operation<BinaryNegation>(board[h][w].IsLying)

);

}

// Make sure field is not isolated

for (int h = 0; h < height; ++h)

{

for (int w = 0; w < width; ++w)

{

solver.Set<LessOrEqual>(

solver.Operation<Addition>(board[h][w].Neighbours.Select(n => n.Selected).ToArray()),

solver.FromConstant(board[h][w].Neighbours.Count - 1)

);

}

// Make sure that we do not split the board

board[height - 1][0].Id.Set<Equal>(solver.FromConstant(1));

board[height - 1][0].Selected.Set<Equal>(solver.FromConstant(0));

for (int h = 0; h < height; ++h)

{

for (int w = 0; w < width; ++w)

{

// Calculate lower count

board[h][w].LowerCount = solver.Operation<Addition>(

board[h][w].Neighbours

.Select(n => n.Id.Operation<IsLessThan>(board[h][w].Id))

.ToArray()

);

// Id is limited

var highestId = 30;

board[h][w].Id.Set<LessOrEqual>(solver.FromConstant(highestId));

// Selected fields have super big id

solver.Set<Equal>(

solver.FromConstant(1),

board[h][w].Selected.Operation<MaterialImplication>(solver.Operation<IsEqual>(board[h][w].Id, solver.FromConstant(highestId)))

);

// Fields next to each other should differ by one unless any of them is selected

foreach (var neighbour in board[h][w].Neighbours)

{

solver.Operation<Disjunction>(board[h][w].Selected, neighbour.Selected).Operation<BinaryNegation>().Operation<MaterialImplication>(

solver.Operation<AbsoluteValue>(solver.Operation<Subtraction>(board[h][w].Id, neighbour.Id)).Operation<IsEqual>(solver.FromConstant(1))

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

}

// Only one field can have no lower neighbours, all others must have a path

if (h == height - 1 && w == 0)

{

board[h][w].LowerCount.Set<Equal>(solver.FromConstant(0));

}

else

{

board[h][w].LowerCount.Set<GreaterOrEqual>(solver.FromConstant(1));

}

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

solver.Solve();

for (int h = 0; h < height; ++h)

{

for (int w = 0; w < width; ++w)

{

if (numbers[h, w] != -1)

{

Console.Write(numbers[h, w]);

}

else

{

Console.Write((int)solver.GetValue(board[h][w].Selected) == 1 ? "X" : " ");

}

Console.WriteLine();

}

Console.WriteLine();

}

static void Main()

{

var solver = new CplexMilpSolver(new CplexMilpSolverSettings

{

IntegerWidth = 5,

Epsilon = 0.00001,

StoreDebugExpressions = false,

CacheConstants = false,

StoreDebugConstraints = false

});

Start(solver);

}

public class Field

{

public int Part { get; set; }

public int Number { get; set; }

public IVariable Selected { get; set; }

public IVariable IsLying { get; set; }

public IVariable Id { get; set; }

public IVariable LowerCount { get; set; }

public List<Field> Neighbours { get; set; }

}

First, in lines 14-38 we define the input. For numbers we use -1 to indicate there is no number in given field.

Next, we calculate neighbours in lines 55-64, just to know which fields are next to each other.

We start with straightforward constraints: one lier in each part (71-82), fields with number can’t be selected (85-88), selected fields can’t be next to each other (91-100), fields with numbers must have correct selected neighbours unless they lie (103-116).

Now, we take care of the requirement that we can’t split the board. First, we make sure a particular field is not isolated (123-132).

Next, we need to build a road from the starting position (bottom left corner) to each field. So we make sure that field is not selected and that we start counting from one (135-136).

Next, we calculate lower neighbours (142-147), we make sure that selected fields have very high id (150-157). Next, fields next to each other must differ by one unless any of them is selected (160-165). Finally, only one field (bottom left corner) can have no lower neighbours (168-174). That’s all.

Output:

Parallel mode: none, using 1 thread.
Root relaxation solution time = 0.01 sec. (9.18 ticks)

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

      0     0        0.0000   363                      0.0000      356
      0     0        0.0000    69                    Cuts: 10      571
      0     0        0.0000   132                    Cuts: 67      653
*     0+    0                            0.0000        0.0000      653    0.00%
      0     0        cutoff              0.0000        0.0000      653    0.00%
Elapsed time = 0.86 sec. (436.87 ticks, tree = 0.00 MB, solutions = 1)

Clique cuts applied:  2
Cover cuts applied:  23
Implied bound cuts applied:  6
Flow cuts applied:  1
Mixed integer rounding cuts applied:  3
Zero-half cuts applied:  3
Gomory fractional cuts applied:  16

Root node processing (before b&c):
  Real time             =    0.86 sec. (437.18 ticks)
Sequential b&c:
  Real time             =    0.00 sec. (0.00 ticks)
                          ------------
Total (root+branch&cut) =    0.86 sec. (437.18 ticks)
X1 2X2X2 2
2 1   2X2
X3X3X3X3X
2 1X X 12
X3X32  X3X
  3X3X2 X
X X X X  1
2  1 23X2X
X3X  X
  2X 2X2X2

Parallel mode: none, using 1 thread.

Root relaxation solution time = 0.01 sec. (9.18 ticks)

Nodes Cuts/

Node Left Objective IInf Best Integer Best Bound ItCnt Gap

0 0 0.0000 363 0.0000 356

0 0 0.0000 69 Cuts: 10 571

0 0 0.0000 132 Cuts: 67 653

* 0+ 0 0.0000 0.0000 653 0.00%

0 0 cutoff 0.0000 0.0000 653 0.00%

Elapsed time = 0.86 sec. (436.87 ticks, tree = 0.00 MB, solutions = 1)

Clique cuts applied: 2

Cover cuts applied: 23

Implied bound cuts applied: 6

Flow cuts applied: 1

Mixed integer rounding cuts applied: 3

Zero-half cuts applied: 3

Gomory fractional cuts applied: 16

Root node processing (before b&c):

Real time = 0.86 sec. (437.18 ticks)

Sequential b&c:

Real time = 0.00 sec. (0.00 ticks)

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

Total (root+branch&cut) = 0.86 sec. (437.18 ticks)

X1 2X2X2 2

2 1 2X2

X3X3X3X3X

2 1X X 12

X3X32 X3X

3X3X2 X

X X X X 1

2 1 23X2X

X3X X

2X 2X2X2