ILP Part 66 – Knight on dominoes

This is the sixtieth 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 a mix of chess and dominoes riddle. We have a board built using dominoes with at least one empty half. We want to find a chess knight route first going through empty pieces and then through ones with numbers.


Let’s go through this step by step.

We start with board in lines 1-5. Spaces represent missing fields, zeroes represent fields we don’t know anything about. You can put other numbers there if you wish to test prefilled boards.

In line 9 we specify how many pieces we have. There are 7 of them, one of which has both halves empty.

Next, we create fields in lines 23-42. Each field has 4 variables: whether given field is empty half of the domino piece, its piece identifier, and two variables for creating the knight route (route end indicating whether route ends here and step number). We also set some ranges in lines 35-44.

Next, couple obvious requirements. First, each domino piece must have exactly two parts (lines 46-59). Next, each domino piece must have one empty half (with exception of totally empty domino) in lines 61-74. Finally, halves must be together on the board (lines 76-111).

Next, we define the path. We start with specifying that it must start end end somewhere (lines 114-115).

Next, we number fields on the path (lines 117-119).

Finally, we define knight moves. We get knight neighbours (lines 127-137), and then specify the numbering. If this is an inner field on the path, then it must have exactly one neighbour with lower number and one neighbour with higher number (lines 147-148). If it’s starting/ending field then it must have exactly one neighbour with matching number (line 145). Last part is in lines 152-160 where we specify that knight moves over empty pieces first.

At the end we print couple representations of the board (which is tricky as well!). Output:

First board shows the piece ids with halves. Second board shows piece ids together (so you can make sure pieces are continuous). Third board shows knight’s path. Finally, last board shows the answer to the riddle. There are many answers here so you can come up with your own.