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:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 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:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
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 |