ILP Part 78 — Tic-Tac-Toe

This is the seventieth eighth 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 Tic-Tac-Toe riddle.

We have a board with some circles and crosses. We need to fill it with more of these so that no 2 by 2 square has four same characters, and we can separate circles from crosses (each of them create a closed shape).

First part is simple. For separation we need to build a simple path of edges going from top to bottom.

First, the regular model:

As always, we have edges for directions, and an identifier which we’re going to propagate through the network.

Now the solution:

First, we define the input. 0 indicates empty field, 1 indicates circle, 2 indicates cross.

We define binary variables for each field indicating what we choose for given field. We then translate existing board in lines 18-25.

Next, we block squares to have the same characters. This is done in lines 27-37 where we make sure that sum is at least one and at most three. If there were four the same characters we’d end up with sum equal to zero or four.

Next, we start building the path. We create variables in lines 39-47, then we make sure neighbours see the same assignments (49-55), and then we ban forks (lines 57-64). Notice that we create crossing points only in the middle of the board, not on the edges. Then we want to make sure that path starts at the top and enters the bottom only once (lines 66-68) and doesn’t touch side edges (70-72).

Next, we want to separate characters. If two fields are separated by a path then they must have different characters (77-80), otherwise they must be the same (82-85).

Finally, we start building the BFS graph to make sure there is only one path. So we propagate identifiers (lines 89-116), and then calculate lower neighbours (lines 118-142) as always.

Finally, we need to make sure that fields in the middle have exactly one lower neighbour, and in the top row there is exactly one point with no lower neighbours. The point would have one edge going to the top (and touching top side of the board) and one other outgoing edge. Since there is no point above the point then the up edge will be ignored, effectively ending with one neighbour only.