Blog | About | Hire Me

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

This website is generated by Emacs.
Privacy