ILP Part 97 — Rook it advanced

This is the ninetieth seventh 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 the advanced version of Uwież (Rook it). We use the solution from the last part. This time we have walls with letters, so we don’t know what numbers they represent. Also, one of the fields of the board is not attacked.

The code:

var board = new [] {
	"  A X   X ",
	"X      X  ",
	" BX  B X C",
	"    X     ",
	"  D   X  A",
	"A  D   X  ",
	"     X    ",
	"B X E  XX ",
	"  X      B",
	" X   X A  "
};

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.BinaryInteger))
		.ToArray()
	).ToArray();

var isCovered = Enumerable
	.Range(0, height)
	.Select(h => Enumerable
		.Range(0, width)
		.Select(w => solver.CreateAnonymous(Domain.BinaryInteger))
		.ToArray()
	).ToArray();

var seesOtherRook = Enumerable
	.Range(0, height)
	.Select(h => Enumerable
		.Range(0, width)
		.Select(w => solver.CreateAnonymous(Domain.BinaryInteger))
		.ToArray()
	).ToArray();

// Ban blockers
for(int i=0;i<height;++i){
	for(int j=0;j<width;++j){
		if(board[i][j] != ' '){
			fields[i][j].Set<Equal>(solver.FromConstant(0));
		}
	}
}

// Make letters and make sure they are unique
Dictionary<string, IVariable> letters = new Dictionary<string, IVariable>();
letters["A"] = solver.CreateAnonymous(Domain.PositiveOrZeroInteger).Set<LessOrEqual>(solver.FromConstant(4));
letters["B"] = solver.CreateAnonymous(Domain.PositiveOrZeroInteger).Set<LessOrEqual>(solver.FromConstant(4));
letters["C"] = solver.CreateAnonymous(Domain.PositiveOrZeroInteger).Set<LessOrEqual>(solver.FromConstant(4));
letters["D"] = solver.CreateAnonymous(Domain.PositiveOrZeroInteger).Set<LessOrEqual>(solver.FromConstant(4));
letters["E"] = solver.CreateAnonymous(Domain.PositiveOrZeroInteger).Set<LessOrEqual>(solver.FromConstant(4));
solver.Set<AllDifferent>(letters.Values.First(), letters.Values.Skip(1).ToArray());

// Count neighbors
for(int i=0;i<height;++i){
	for(int j=0;j<width;++j){
		if(board[i][j] != 'X' && board[i][j] != ' '){
			IVariable count = letters[board[i][j].ToString()];
			
			var sum = solver.FromConstant(0);
			if(j > 0) sum = sum.Operation<Addition>(fields[i][j-1]);
			if(j < width - 1) sum = sum.Operation<Addition>(fields[i][j+1]);
			if(i > 0) sum = sum.Operation<Addition>(fields[i-1][j]);
			if(i < height - 1) sum = sum.Operation<Addition>(fields[i+1][j]);
			
			sum.Set<Equal>(count);
		}
	}
}

// Find other rooks
for(int i=0;i<height;++i){
	for(int j=0;j<width;++j){
		var hasRook = solver.FromConstant(0);
		var stillLooking = solver.FromConstant(1);
		
		stillLooking = solver.FromConstant(1);
		for(int k=i+1;k<height;++k){
			var isThisOneRook = fields[k][j].Operation<IsEqual>(solver.FromConstant(1));
			hasRook = hasRook.Operation<Disjunction>(
				stillLooking.Operation<Conjunction>(isThisOneRook)
			);
			
			stillLooking = stillLooking.Operation<Conjunction>(
				solver.FromConstant(board[k][j] == ' ' ? 1 : 0)
			);
		}
		
		stillLooking = solver.FromConstant(1);
		for(int k=i-1;k>=0;--k){
			var isThisOneRook = fields[k][j].Operation<IsEqual>(solver.FromConstant(1));
			hasRook = hasRook.Operation<Disjunction>(
				stillLooking.Operation<Conjunction>(isThisOneRook)
			);
			
			stillLooking = stillLooking.Operation<Conjunction>(
				solver.FromConstant(board[k][j] == ' ' ? 1 : 0)
			);
		}
		
		stillLooking = solver.FromConstant(1);
		for(int k=j+1;k<width;++k){
			var isThisOneRook = fields[i][k].Operation<IsEqual>(solver.FromConstant(1));
			hasRook = hasRook.Operation<Disjunction>(
				stillLooking.Operation<Conjunction>(isThisOneRook)
			);
			
			stillLooking = stillLooking.Operation<Conjunction>(
				solver.FromConstant(board[i][k] == ' ' ? 1 : 0)
			);
		}
		
		stillLooking = solver.FromConstant(1);
		for(int k=j-1;k>=0;--k){
			var isThisOneRook = fields[i][k].Operation<IsEqual>(solver.FromConstant(1));
			hasRook = hasRook.Operation<Disjunction>(
				stillLooking.Operation<Conjunction>(isThisOneRook)
			);
			
			stillLooking = stillLooking.Operation<Conjunction>(
				solver.FromConstant(board[i][k] == ' ' ? 1 : 0)
			);
		}
		
		var isRook = fields[i][j].Operation<IsEqual>(solver.FromConstant(1));
		var isSpecial = solver.FromConstant(board[i][j] != ' ' ? 1 : 0);
		
		isCovered[i][j].Set<Equal>(
			solver.Operation<Disjunction>(
				isSpecial,
				isRook,
				hasRook
			)
		);
		
		seesOtherRook[i][j].Set<Equal>(
			solver.Operation<Conjunction>(
				isRook,
				hasRook
			)
		);
	}
}

// Make sure all but one fields ale covered
solver.Operation<Addition>(isCovered.SelectMany(c => c).ToArray()).Set<GreaterOrEqual>(solver.FromConstant(width * height - 1));

// Make sure rooks do not attack each other
for(int i=0;i<height;++i){
	for(int j=0;j<width;++j){
		seesOtherRook[i][j].Set<Equal>(solver.FromConstant(0));
	}
}

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

for(int i=0;i<height;++i){
	for(int j=0;j<width;++j){
		if(board[i][j] == 'X'){
			Console.Write(board[i][j]);
		}else if(board[i][j] != ' '){
			Console.Write(Math.Round(solver.GetValue(letters[board[i][j].ToString()])));
		}else {
			Console.Write(solver.GetValue(fields[i][j]) > 0.5 ? "R" : " ");
		}
	}
	Console.WriteLine();
}
Console.WriteLine();

for(int i=0;i<height;++i){
	for(int j=0;j<width;++j){
		Console.Write(solver.GetValue(isCovered[i][j]) > 0.5 ? "1" : "0");
	}
	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

var board = new [] {

" A X X ",

"X X ",

" BX B X C",

" X ",

" D X A",

"A D X ",

" X ",

"B X E XX ",

" X B",

" X X A "

};

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.BinaryInteger))

.ToArray()

).ToArray();

var isCovered = Enumerable

.Range(0, height)

.Select(h => Enumerable

.Range(0, width)

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

.ToArray()

).ToArray();

var seesOtherRook = Enumerable

.Range(0, height)

.Select(h => Enumerable

.Range(0, width)

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

.ToArray()

).ToArray();

// Ban blockers

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

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

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

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

}

// Make letters and make sure they are unique

Dictionary<string, IVariable> letters = new Dictionary<string, IVariable>();

letters["A"] = solver.CreateAnonymous(Domain.PositiveOrZeroInteger).Set<LessOrEqual>(solver.FromConstant(4));

letters["B"] = solver.CreateAnonymous(Domain.PositiveOrZeroInteger).Set<LessOrEqual>(solver.FromConstant(4));

letters["C"] = solver.CreateAnonymous(Domain.PositiveOrZeroInteger).Set<LessOrEqual>(solver.FromConstant(4));

letters["D"] = solver.CreateAnonymous(Domain.PositiveOrZeroInteger).Set<LessOrEqual>(solver.FromConstant(4));

letters["E"] = solver.CreateAnonymous(Domain.PositiveOrZeroInteger).Set<LessOrEqual>(solver.FromConstant(4));

solver.Set<AllDifferent>(letters.Values.First(), letters.Values.Skip(1).ToArray());

// Count neighbors

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

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

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

IVariable count = letters[board[i][j].ToString()];

var sum = solver.FromConstant(0);

if(j > 0) sum = sum.Operation<Addition>(fields[i][j-1]);

if(j < width - 1) sum = sum.Operation<Addition>(fields[i][j+1]);

if(i > 0) sum = sum.Operation<Addition>(fields[i-1][j]);

if(i < height - 1) sum = sum.Operation<Addition>(fields[i+1][j]);

sum.Set<Equal>(count);

}

// Find other rooks

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

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

var hasRook = solver.FromConstant(0);

var stillLooking = solver.FromConstant(1);

stillLooking = solver.FromConstant(1);

for(int k=i+1;k<height;++k){

var isThisOneRook = fields[k][j].Operation<IsEqual>(solver.FromConstant(1));

hasRook = hasRook.Operation<Disjunction>(

stillLooking.Operation<Conjunction>(isThisOneRook)

);

stillLooking = stillLooking.Operation<Conjunction>(

solver.FromConstant(board[k][j] == ' ' ? 1 : 0)

);

}

stillLooking = solver.FromConstant(1);

for(int k=i-1;k>=0;--k){

var isThisOneRook = fields[k][j].Operation<IsEqual>(solver.FromConstant(1));

hasRook = hasRook.Operation<Disjunction>(

stillLooking.Operation<Conjunction>(isThisOneRook)

);

stillLooking = stillLooking.Operation<Conjunction>(

solver.FromConstant(board[k][j] == ' ' ? 1 : 0)

);

}

stillLooking = solver.FromConstant(1);

for(int k=j+1;k<width;++k){

var isThisOneRook = fields[i][k].Operation<IsEqual>(solver.FromConstant(1));

hasRook = hasRook.Operation<Disjunction>(

stillLooking.Operation<Conjunction>(isThisOneRook)

);

stillLooking = stillLooking.Operation<Conjunction>(

solver.FromConstant(board[i][k] == ' ' ? 1 : 0)

);

}

stillLooking = solver.FromConstant(1);

for(int k=j-1;k>=0;--k){

var isThisOneRook = fields[i][k].Operation<IsEqual>(solver.FromConstant(1));

hasRook = hasRook.Operation<Disjunction>(

stillLooking.Operation<Conjunction>(isThisOneRook)

);

stillLooking = stillLooking.Operation<Conjunction>(

solver.FromConstant(board[i][k] == ' ' ? 1 : 0)

);

}

var isRook = fields[i][j].Operation<IsEqual>(solver.FromConstant(1));

var isSpecial = solver.FromConstant(board[i][j] != ' ' ? 1 : 0);

isCovered[i][j].Set<Equal>(

solver.Operation<Disjunction>(

isSpecial,

isRook,

hasRook

)

);

seesOtherRook[i][j].Set<Equal>(

solver.Operation<Conjunction>(

isRook,

hasRook

)

);

}

// Make sure all but one fields ale covered

solver.Operation<Addition>(isCovered.SelectMany(c => c).ToArray()).Set<GreaterOrEqual>(solver.FromConstant(width * height - 1));

// Make sure rooks do not attack each other

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

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

seesOtherRook[i][j].Set<Equal>(solver.FromConstant(0));

}

var goal = solver.FromConstant(0);

solver.Solve();

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

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

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

Console.Write(board[i][j]);

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

Console.Write(Math.Round(solver.GetValue(letters[board[i][j].ToString()])));

}else {

Console.Write(solver.GetValue(fields[i][j]) > 0.5 ? "R" : " ");

}

Console.WriteLine();

}

Console.WriteLine();

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

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

Console.Write(solver.GetValue(isCovered[i][j]) > 0.5 ? "1" : "0");

}

Console.WriteLine();

}

Most of the code should be familiar. The changes are in two places.

Lines 51-57 – we need to create variables for letters. We then use them in counting neighbours in lines 60-74.
Line 151 – we make sure that all fields but one are covered.
We also print the result differently, so we can see which field is not attacked.

The output:

Reduced MIP has 1018 rows, 576 columns, and 3227 nonzeros.
Reduced MIP has 571 binaries, 5 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.06 sec. (31.09 ticks)
Found incumbent of value 0.000000 after 0.08 sec. (39.56 ticks)

Root node processing (before b&c):
  Real time             =    0.08 sec. (40.10 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.08 sec. (40.10 ticks)
 R1 X R X
X   R  X R
 0X  0 XR3
    X    R
R 2R  XR 1
1 R2  RX
    RX   R
0 XR4R XX
 RX R    0
RXR  X 1R

1111111111
1111111111
1111111111
1101111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111

Reduced MIP has 1018 rows, 576 columns, and 3227 nonzeros.

Reduced MIP has 571 binaries, 5 generals, 0 SOSs, and 0 indicators.

Presolve time = 0.06 sec. (31.09 ticks)

Found incumbent of value 0.000000 after 0.08 sec. (39.56 ticks)

Root node processing (before b&c):

Real time = 0.08 sec. (40.10 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.08 sec. (40.10 ticks)

R1 X R X

X R X R

0X 0 XR3

X R

R 2R XR 1

1 R2 RX

RX R

0 XR4R XX

RX R 0

RXR X 1R

1111111111

1101111111

1111111111