# Solving Domino Fit Using Constraint Programming

by Philippe Olivier

Created 2024-03-27

Updated 2024-04-03

Domino Fit is a domino tiling game, where you have to place dominoes on a board in such a way that the sum of the dots must match row and column numbers. There are two dominoes: a one-dot vertical domino and a two-dot horizontal domino. Dominoes may not be rotated. There are also a few black squares on which dominoes may not be placed. The board in its initial and solved states looks like this:

Initial board | Solved board |

Domino Fit was discussed on Hacker News here, and can be played here. Let's write a constraint programming model to automatically solve the game.

The data given to us is the board size, the location of the black squares, and the row and column numbers. We use `(w, h)`

with `w`

the width and `h`

the height to refer to a particular square. The top-left square is at position `(0, 0)`

; the width increases when going right and the height increases when going down (I know…).

# The (0, 0) position is at the top-left of the board width = 7 height = 7 # Black squares (w, h) blacks = [(0, 6), (1, 0), (3, 5), (4, 1), (6, 0)] # Top numbers top_numbers = [3, 2, 4, 10, 4, 3, 9] # Side numbers side_numbers = [5, 5, 6, 5, 4, 4, 6]

We import CP-SAT and create an empty model:

from ortools.sat.python import cp_model model = cp_model.CpModel()

We can describe the state of a board (i.e., which types of dominoes are placed where) using two matrices of binary variables representing the positions of the one- and two-dot dominoes. For example, if cell `(4, 2)`

of the `ones`

matrix is set to 1, this means that the "dot half" of a one-dot vertical domino is placed at position `(4, 2)`

. That cell of the `ones`

matrix would be set to 0 in the alternate case.

# `ones[w][h]` indicates if the dot number of a one-dot vertical domino is at position (w, h) ones = [[model.NewBoolVar(f"ones_{w}_{h}") for h in range(height)] for w in range(width)] # `twos[w][h]` indicates if the dot number of a two-dot vertical domino is at position (w, h) twos = [[model.NewBoolVar(f"twos_{w}_{h}") for h in range(height)] for w in range(width)]

We can now use these two matrices to sum the dots of the rows and the columns, and ensure that they match with the numbers of each row and column:

# The top numbers must match for w in range(width): model.Add(cp_model.LinearExpr.WeightedSum([ones[w][h] for h in range(height)], [1 for _ in range(height)]) + cp_model.LinearExpr.WeightedSum([twos[w][h] for h in range(height)], [2 for _ in range(height)]) == top_numbers[w]) # The side numbers must match for h in range(height): model.Add(cp_model.LinearExpr.WeightedSum([ones[w][h] for w in range(width)], [1 for _ in range(width)]) + cp_model.LinearExpr.WeightedSum([twos[w][h] for w in range(width)], [2 for _ in range(width)]) == side_numbers[h])

Finally, all that is left to do is to ensure that the dominoes don't overlap other dominoes or black squares. This is actually pretty easy to model, but a bit tiresome as we have to consider many special cases: each of the four corners, each of the four sides, and the center of the board. These cases have to be considered individually because, depending on the location, half of one or another domino could end up off-grid. We use simple inequalities to ensure that no conflicting dominoes are placed on the board. For instance, if we place a one-dot vertical domino at position `(w, h)`

, the constraint `ones[w][h] + ones[w][h+1] <= 1`

ensures that the "dot half" of another one-dot vertical domino does not end up in the adjacent square below, as it would overlap the "blank half" of the domino above.

# The dominoes must fit for h in range(height): for w in range(width): # Top-left corner if (w, h) == (0, 0): if (w, h) in blacks: model.Add(ones[w][h] + twos[w][h] + twos[w+1][h] == 0) else: model.Add(twos[w][h] == 0) model.Add(ones[w][h] + ones[w][h+1] <= 1) model.Add(ones[w][h] + twos[w+1][h] <= 1) model.Add(ones[w][h] + twos[w+1][h+1] <= 1) # Top-right corner elif (w, h) == (width-1, 0): if (w, h) in blacks: model.Add(ones[w][h] + twos[w][h] == 0) else: model.Add(ones[w][h] + ones[w][h+1] <= 1) model.Add(ones[w][h] + twos[w][h] <= 1) model.Add(ones[w][h] + twos[w][h+1] <= 1) model.Add(twos[w][h] + twos[w-1][h] <= 1) model.Add(twos[w][h] + ones[w-1][h] <= 1) # Bottom-left corner elif (w, h) == (0, height-1): if (w, h) in blacks: model.Add(ones[w][h] + ones[w][h-1] + twos[w][h] + twos[w+1][h] == 0) else: model.Add(ones[w][h] + twos[w][h] == 0) # Bottom-right corner elif (w, h) == (width-1, height-1): if (w, h) in blacks: model.Add(ones[w][h] + ones[w][h-1] + twos[w][h] == 0) else: model.Add(ones[w][h] == 0) model.Add(twos[w][h] + ones[w][h-1] <= 1) model.Add(twos[w][h] + twos[w-1][h] <= 1) model.Add(twos[w][h] + ones[w-1][h-1] <= 1) # Top border elif h == 0: if (w, h) in blacks: model.Add(ones[w][h] + twos[w][h] + twos[w+1][h] == 0) else: model.Add(ones[w][h] + twos[w][h] <= 1) model.Add(ones[w][h] + twos[w+1][h] <= 1) model.Add(twos[w][h] + twos[w+1][h] <= 1) # Left border elif w == 0: if (w, h) in blacks: model.Add(ones[w][h] + ones[w][h-1] + twos[w][h] + twos[w+1][h] == 0) else: model.Add(twos[w][h] == 0) model.Add(ones[w][h] + ones[w][h+1] <= 1) model.Add(ones[w][h] + ones[w][h-1] <= 1) model.Add(ones[w][h] + twos[w+1][h] <= 1) model.Add(ones[w][h] + twos[w+1][h+1] <= 1) # Right border elif w == width-1: if (w, h) in blacks: model.Add(ones[w][h] + ones[w][h-1] + twos[w][h] == 0) else: model.Add(ones[w][h] + ones[w][h+1] <= 1) model.Add(ones[w][h] + ones[w][h-1] <= 1) model.Add(ones[w][h] + twos[w][h] <= 1) model.Add(ones[w][h] + twos[w][h+1] <= 1) model.Add(twos[w][h] + ones[w-1][h] <= 1) # Bottom border elif h == height-1: if (w, h) in blacks: model.Add(ones[w][h] + ones[w][h-1] + twos[w][h] + twos[w+1][h] == 0) else: model.Add(ones[w][h] == 0) model.Add(twos[w][h] + twos[w+1][h] <= 1) model.Add(twos[w][h] + twos[w-1][h] <= 1) model.Add(twos[w][h] + ones[w][h-1] <= 1) model.Add(twos[w][h] + ones[w-1][h-1] <= 1) # Everywhere else else: if (w, h) in blacks: model.Add(ones[w][h] + ones[w][h-1] + twos[w][h] + twos[w+1][h] == 0) else: model.Add(ones[w][h] + ones[w][h-1] <= 1) model.Add(ones[w][h] + ones[w][h+1] <= 1) model.Add(ones[w][h] + twos[w][h] <= 1) model.Add(ones[w][h] + twos[w][h+1] <= 1) model.Add(ones[w][h] + twos[w+1][h] <= 1) model.Add(ones[w][h] + twos[w+1][h+1] <= 1) model.Add(twos[w][h] + twos[w+1][h] <= 1) model.Add(twos[w][h] + ones[w-1][h] <= 1) model.Add(twos[w][h] + ones[w][h-1] <= 1) model.Add(twos[w][h] + ones[w-1][h-1] <= 1)

Now that the problem is modeled, let's solve it:

solver = cp_model.CpSolver() status = solver.Solve(model) # Print the solution for h in range(height): for w in range(width): if solver.Value(ones[w][h]) == 1: print(1, end="") elif solver.Value(twos[w][h]) == 1: print(2, end="") elif (w, h) in blacks: print("X", end="") elif w < width-1 and solver.Value(twos[w+1][h]) == 1: print("-", end="") else: print("|", end="") print()

This gives us the following solution:

1X-2-2X |1-2X-2 1|-21-2 |1-2|11 1|-21|| |-2X|-2 X-2-2-2

We can see that this solution matches the one shown at the beginning of this article. The complete source code of the model can be found here.

Update (2024-04-03): A more elegant approach than mine can be found here, using Z3 instead of CP-SAT (thanks rjeli).