TILE THEM ALL! Problem #2 of The 2024 LP-Contest — A Constraint Satisfaction Problem
Can we model this with a Bayesian Network? Yes, but it does require some patience (and some help. I could not have done this without my assistant, aka GPT5!). This all comes down to the Constraint Satisfaction Problem.
We will need a way to represent what we are trying to do, but in the context of a Bayesian network, so that we can think more clearly about what we are after. The first step is to create 20 nodes to represent the cells and the numbers they contain, as in the grid above.
In this context, the notion of a “tile” is only possible between any two nodes along the edges, either vertically or horizontally. There are 4 horizontal edges in each row, for a total of 16, and there are 3 vertical edges in each column, for a total of 15. This gives us 31 nodes in total. Each will be a boolean node (true/false), where “true” will mean that it is a true tile between the two numbers, while “false” will mean that the tile is eliminated. The idea is to impose constraints in such a way that, once activated, Netica will find the 10 tiles that meet the stated condition, namely that they uniquely contain each of the 10 unordered pairs from {0, 1, 2, 3} x {0, 1, 2, 3}. Let’s first display the possible horizontal tiles (in pink).
And we add the possible vertical tiles (bluish teal):
The general idea is that each of these is only a hypothetical tile since there can only be a total of exactly 10 tiles, but we have 31 tiles above. We will need to find various constraints not only to get exactly 10 tiles, but to get the right 10 tiles that correspond to one instance of each unordered pair for {0, 1, 2, 3} x {0, 1, 2, 3}.
(Note that the yellow numbered nodes are inert and only there as a graphical overlay for reference.)
The very first constraint is that each number will only have one neighbor (since only two numbers exist on a tile). Let’s use a coordinate system to represent and locate each number. For example, the corner number “1” (C_1_1) can only be on the horizontal tile (H_1_1) with “3” as its neighbor, or be on the vertical tile (V_1_1) with another “3” as its neighbor.
Here is a fragment to see more clearly
For each number, we want to say that it can only be on one tile. Each corner number could be on just one of two tiles, but interior numbers must be on just one of four possible tiles (2 horizontal and 2 vertical). Here are two example equations:
These equations are repeated for the number node.
C_2_2 (H_2_1, V_1_2, H_2_2, V_2_2) =
ExactlyOneTrue(H_2_1, V_1_2, H_2_2, V_2_2)
C_2_3 (V_1_3, V_2_3, H_2_2, H_2_3) =
plus (V_1_3, V_2_3, H_2_2, H_2_3) == 1
C_2_4 (V_2_4, H_2_3, V_1_4, H_2_4) =
plus (V_2_4, H_2_3, V_1_4, H_2_4) == 1
C_2_5 (V_2_5, H_2_4, V_1_5) =
plus (V_2_5, H_2_4, V_1_5) == 1
C_3_1 (V_3_1, H_3_1, V_2_1) =
plus (V_3_1, H_3_1, V_2_1) == 1
C_3_2 (V_3_2, H_3_1, H_3_2, V_2_2) =
plus (V_3_2, H_3_1, H_3_2, V_2_2) == 1
C_3_3 (V_3_3, H_3_2, V_2_3, H_3_3) =
plus (V_3_3, H_3_2, V_2_3, H_3_3) == 1
C_3_4 (V_3_4, H_3_3, H_3_4, V_2_4) =
plus (V_3_4, H_3_3, H_3_4, V_2_4) == 1
C_3_5 (V_2_5, H_3_4, V_3_5) =
plus (V_2_5, H_3_4, V_3_5) == 1
C_4_1 (V_3_1, H_4_1) =
plus (V_3_1, H_4_1) == 1
C_4_2 (H_4_1, H_4_2, V_3_2) =
plus (H_4_1, H_4_2, V_3_2) == 1
C_4_3 (H_4_2, H_4_3, V_3_3) =
plus (H_4_2, H_4_3, V_3_3) == 1
C_4_4 (H_4_3, V_3_4, H_4_4) =
plus (H_4_3, V_3_4, H_4_4) == 1
C_4_5 (H_4_4, V_3_5) =
plus (H_4_4, V_3_5) == 1
Once compiled, we will set each of these “cell cover” nodes to “true” to enforce that constraint. Notice that if all we wanted were any 10 tiling arrangement, we would be basically done. But not just any 10 tiles will do. The tiles have to exactly match each unordered pair from {0, 1, 2, 3} x {0, 1, 2, 3}. There are 10 such pairs. The next step is a bit more tedious. We have to find each such pair in the given grid and create a constraint node for each one.
Get Pascal Bercker’s stories in your inbox
Join Medium for free to get updates from this writer.
For example, there are 6 instances of the pair {2,3} ( the same as {3,2}), which we connect to the constraint node called “TypeUsed_T23”.
The constraint node TypeUsed_T23 is linked to each horizontal (H_1_1, etc) and vertical node (V_1_1, etc) where an instance of that pair occurs.
TypeUsed_T23 (H_2_1, V_1_2, V_1_5,
V_2_2, V_3_1, V_3_2) =
ExactlyOneTrue(H_2_1, V_1_2, V_1_5,
V_2_2, V_3_1, V_3_2)Since there are 10 unordered pairs, we theoretically have 10 such TypeUsed nodes. But we have a bit fewer than that because some are singletons, meaning the pair occurs only once, as with {2, 2} in the left-hand corner. Since that’s the only possible tile, we don’t need to worry about that one.
Only one kind of equation is needed for each TypeUsed_T constraint node (x and y are the coordinates for each horizontal (H_x_y) and Vertical (V_x_y) tile.
TypeUsed_T00 (H_3_3, V_1_3, V_2_3) = // H_x_y and V_x_y - possible tiles
ExactlyOneTrue (H_3_3, V_1_3, V_2_3)
TypeUsed_T01 (H_1_3, H_2_3, H_3_4, V_2_4, V_3_3, V_3_5) =
ExactlyOneTrue (H_1_3, H_2_3, H_3_4, V_2_4, V_3_3, V_3_5)
TypeUsed_T02 (H_2_2, H_4_4, V_3_4) =
ExactlyOneTrue (H_2_2, H_4_4, V_3_4)
TypeUsed_T03 (H_1_2, H_3_2) =
ExactlyOneTrue (H_1_2, H_3_2)
TypeUsed_T12 (H_1_4, H_4_2, H_4_3) =
ExactlyOneTrue (H_1_4, H_4_2, H_4_3)
TypeUsed_T13 (H_1_1, H_2_4, V_1_1, V_2_5) =
ExactlyOneTrue(H_1_1, H_2_4, V_1_1, V_2_5)
TypeUsed_T23 (H_2_1, V_1_2, V_1_5,
V_2_2, V_3_1, V_3_2) =
ExactlyOneTrue(H_2_1, V_1_2, V_1_5,
V_2_2, V_3_1, V_3_2)
(We have omitted {1, 1}, {2, 2}, both singletons, and {3, 3} with only two possible tiles).
It is a very handy feature of Netica that we can choose which nodes to display and which nodes and links to make invisible. This avoids a cluttered view with very busy networks.
All that remains to be done now is simply to activate the 20 cellcover nodes by setting them to “true”, and to activate the 7 TypeUsed nodes also by setting them to “true”, and the hope is that exactly 10 “tiles” get updated to “true”, meaning some combination of the H_x_y nodes and V_x_y nodes.
Let’s have a look
Let’s add the vertical tiles and the numbers:
This is a cluttered network, so let’s just show the relevant horizontal and vertical tiles and hide the rest.
I found it somewhat remarkable that essentially only one kind of equation was needed for the entire network, namely ExactlyOneTrue (or its equivalent), so as to impose the relevant constraints on various nodes. Though it works, it’s not the most elegant solution, but still instructive. There’s a certain amount of pre-processing done by the user, which ideally would be better if entirely done by the network itself. In particular, I had to locate each instance where the unordered pair occurred in the grid to tell Netica what to constrain and limit to a single instance. Ideally, one should be able to just submit a list of the unordered pairs and let the network figure out the rest.
The PICAT solution from Professor Zhou is further below (Source and reference section). I ran the PICAT version, where “tiles.dat” is just a list of the coordinates of the grid and what number is located there. The output returns the two coordinates of each of the 10 tiles.
SOURCES & REFERENCES
lp-contest/lp2024_problems.pdf at main · nfzhou/lp-contest · GitHub
Here is the PICAT solution:
lp-contest/lp2024_prob2.pi at main · nfzhou/lp-contest · GitHub
