ILP Part 96 — Rook it! – Random IT Utensils

This is the ninetieth 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 the basic version of Uwież (Rook it).

We are given a chessboard with some fields highlighted. These fields act as invisible walls, so that rooks can’t move past them. Some of these walls have numbers which indicate how many rooks there are in vertical and horizontal neighbours (so up, down, left, and right neighbours). Our goal is to put rooks on the chessboard in a way that all fields are attacked by rooks, and no two rooks attack each other. Also, walls are considered “attacked” by definition, so they don’t need to be explicitly attacked by some other rooks.

Solution:

var board = new [] {
	"X  X   ",
	"  X  0 ",
	"   2  1",
	" 4   X ",
	"3  X   ",
	" X  X  ",
	"   1  1"
};

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));
		}
	}
}

// Count neighbors
for(int i=0;i<height;++i){
	for(int j=0;j<width;++j){
		if(board[i][j] != 'X' && board[i][j] != ' '){
			int count = int.Parse(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>(solver.FromConstant(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 fields ale covered
for(int i=0;i<height;++i){
	for(int j=0;j<width;++j){
		isCovered[i][j].Set<Equal>(solver.FromConstant(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] != ' '){
			Console.Write(board[i][j]);
		}else {
			Console.Write(solver.GetValue(fields[i][j]) > 0.5 ? "R" : " ");
		}
	}
	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

var board = new [] {

"X X ",

" X 0 ",

" 2 1",

" 4 X ",

"3 X ",

" X X ",

" 1 1"

};

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));

}

// Count neighbors

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

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

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

int count = int.Parse(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>(solver.FromConstant(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 fields ale covered

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

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

isCovered[i][j].Set<Equal>(solver.FromConstant(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] != ' '){

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

}else {

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

}

Console.WriteLine();

}

We start with defining the board. Letters X indicate walls with no numbers on it. Numbers indicate walls with numbers. Spaces are empty fields.

First, we start by defining the grid of bitflags indicating where rooks are (lines 14-20). We also define additional bitflags: to indicate if given field is covered (attacked) by a rook (lines 22-28), and to indicate if given field is a rook and sees some other rook (lines 30-36).

First, we disallow placing rooks in walls. This is in lines 39-45.

Next, we make sure that walls with numbers have corrrect number of neighbours – liens 48-62.

Now comes the hard part. We iterate over all the fields. For each of them we want to find a rook attacking it. This is in lines 65-136. We do it by iterating over all directions, and checking if there is a rook that sees us. Let’s go line by line.

First, we define a variable indicating if we found a rook – line 67. We also define another variable (line 68) which says if we’re still looking for a rook in a given direction.

Next, we go in four directions. We reinitialize the variable indicating if we’re still looking for a rook (line 82). Next, we go over remaining fields in the given direction. We check if current field is a rook (line 84). Next, we update the value indicating if we found a rook. We set it to true when either it already was a true or we’re still looking and the current field is a rook (lines 85-87). Next, we update the flag indicating if we’re still looking for a rook – we stop if we hit a wall (lines 89-91).

We repeat that for three other directions. Finally, we set the field as covered (attacked) if it was a rook, was special (= a wall), or had some rook attacking it (lines 121-127). We also update the flag if the current field is a rook and sees some other rook (lines 129-133).

Now we can add remaining constraints. We make sure that all fields are covered (lines 139-143). We also make sure that there is no rook seeing other rook (lines 146-150).

Output:

Tried aggregator 1 time.
MIP Presolve eliminated 7861 rows and 4606 columns.
MIP Presolve modified 5685 coefficients.
All rows and columns eliminated.
Presolve time = 0.02 sec. (4.25 ticks)

Root node processing (before b&c):
  Real time             =    0.02 sec. (5.06 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.02 sec. (5.06 ticks)
X RX  R
  XR 0
 R 2R 1
R4R  XR
3R X
RX RX
 R 1 R1

Tried aggregator 1 time.

MIP Presolve eliminated 7861 rows and 4606 columns.

MIP Presolve modified 5685 coefficients.

All rows and columns eliminated.

Presolve time = 0.02 sec. (4.25 ticks)

Root node processing (before b&c):

Real time = 0.02 sec. (5.06 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.02 sec. (5.06 ticks)

X RX R

XR 0

R 2R 1

R4R XR

3R X

RX RX

R 1 R1