ILP Part 96 — Rook it!

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.


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