Let’s Tango!

Posted on by mabouali

I know it's a cheesy title for a nerdy stuff.

Anyway, I am not sure how long is LinkedIn doing it, but I started to get some messages on LinkedIn challenging me to solve some puzzles.

I have to admit, I love them.

In this post we are going to focus on one of the puzzles, called "Tango". (What else did you think I meant by "Let's Tango!"?)

What is Tango Puzzle?

Tango is a [digital] board game. You get a square board, let's say a 6 \times 6, and you have to place a "Moon" or a "Sun" in each cell.

So, what's the challenge? Of course, you cannot place a moon or sun in any arbitrary order. You need to follow certain rules as explained in next section.

How to play Tango?

There are a few simple rules that you need to follow.

  1. The board usually comes with few cells already assigned either a moon or a sun. You cannot change those of course.
  2. Each row and column must have the same number of moon and sun.
  3. At most two moon or two sun could be next to each other either horizontally or vertically.
  4. There are some signs at the border between two cells:
    • If the "=" is used, it means those two cells must have the same value assigned. For example, if you assign moon to one, you need to assign moon to the other as well.
    • If the "x" is used, it means those two cells must have the opposite value assigned to them. For example, if you assign moon to one, you must assign sun to the other.

Here is an example of the board before being solved:

How to solve it?

You need to use power of deduction to solve the puzzle. Based on the initial conditions of the puzzle, you have to find a cell that can only have one value assigned to it that satisfies all the rules. The puzzle claims that you never have to guess a value. I am assuming that they initially provide enough values for different cells that you can certainly deduce a final value for another cell that does not yet have any values. Once you do assign a new cell a value, now you should be able to deduce a value for at least one other cell.

"When you have eliminated the impossible, whatever remains, however improbable, must be the truth"

Sherlock Holmes (or should I say Conan Doyle)

How to solve it numerically?

Well, if you are familiar with my posts, you know that I want to introduce a different method of solving it. That means having computers to solve the puzzle for us! Wouldn't that be fun?

Before we can have computers to solve a Tango puzzle, we do need to specify the problem in a mathematical language. That's the first step. Even before choosing which programming language or software framework/package you want to use.

You need to first model the problem in a mathematical language.

Constraint Programming (CP)

Constraint Programming (CP) is commonly used in many real world industrial applications to find an answer or strategy for a business need. As the name suggests, you keep defining certain constraints: that is certain restriction and/or limitation on what the final answer should be.

For example:

  • Total cost must be less than $100M amount.
  • You cannot have more than 10,000 unit of a product stored in that warehouse.
  • You cannot deliver a car, unless you have put a tire on it (actually 4 tires).
  • If department A is using the lab, department B cannot use it at the same time.
  • ...

Depending on your problem, the list could go on and on and on.

Constraints are fun. I would argue that you will learn a lot about a business when you start thinking about the constraints for the problem that you are solving.

  • Some constraint could be only seasonal, like they are applicable in summer but not winter.
  • Some constraint could be temporary.
  • Some constraint could be preference, not really a constraint; but that's how you or the business leader believe that their solution should look like.
  • Some stuff that were constraint may no longer be a constraint, or the other way around.
    • ok this is a variation of temporary constraint but it counts. (Ryan Reynolds)
  • Some constraint are only applicable if certain other conditions are met. You can think of this last one, as a constraint for a constraint.

Could you think about an example for each case of the constraints mentioned above?

While you need to satisfy a bunch of constraints to find a solution, often time there are one or more objective functions that needs to be minimized (or maximized) (i.e. optimized) at the same time. In real application you will seldom face a situation that you need to just choose a solution that satisfies some constraints. You usually need to optimize something while meeting the constraints. And that's where things get fun.

Ok, what does this have to do with Tango?

There are many ways to solve a puzzle like Tango. But here, we want to specify the puzzles as a constraint problem and use a CP solver, (in our case OR-Tools) to find a solution.

Remember we said that the first step is to define your problem in mathematical language?!!! Without getting into details, these are the following steps that you need to follow, regardless of the problem that you are solving. We will first try to explain the step in a very general form, and then, we will say what we are going to do in our problem, that is solving a Tango Puzzle.

Choose Decision Variables

First you need to provide one ore more (usually more than one; a lot more than one) decision variables, let's call them x_i for i-th decision variable. Each variable must have a very well known domain, D_i, where x_i \in D_i. Let's say for a task that needs to run every day, you are trying to find out when it should start. In this case, your decision variable is the time that the task should start and the domain is 0 to 24hrs (there are 24 hours in a day, right?).

So, what would be a decision variable in the case of Tango Puzzle? For each cell we need to decide if we are putting a sun or a moon. Hence, for a square board of size 6 \times 6 we would have 36 decision variables, which for convenience, we are going to call them x_{i,j}, where 0 \le i,j \le 5 are integers showing the row and column number of each cell in the tango board

As for the Domain, we have: x_{i,j} \in \left \{ \mathtext{sun}, \mathtext{moon} \right\}. mmmmm! Only two values? We have seen that somewhere else? Yes, our decision variables are all binary values. They can only have two values: True/False, or 0 and 1.

Let's assume that if x_{i,j} = 1 that means we are assigning a sun to that cell and if x_{i,j}=0 we are assigning a moon to that cell.

Ok, we are done with this step!

Choosing an Objective function

This is the most important step. The whole point of choosing a value for each of the decision variables is to either minimize or maximize the object function. If you define a wrong objective function, you will choose a value for your decision variables that are optimizing a wrong problem (or at best your solving a problem that you were not asked to solve).

This also means that your objective function is written using the decision variables that you chose in previous step.

Remember at the end of the previous step I said we are done with that step?!

Well, I lied. You are not done. Essentially, you have to iterate these two steps as much as needed to make sure you have the right objective function and proper decision variables that reflects the objective function.

So, what is our objective function in Tango Puzzle?

None. There is no objective function that we want to minimize or maximize in this case. But in most real cases, you usually have an objective function if not more than one.

So, may be I didn't lie when I said we are done with previous step!

Define your constraints

Now comes the constraints. Usually when you start learning about optimization, they start without constraints. But real world's problems are hardly unconstraint. There are always some constraint associated with it.

So, let's define the constraints for the Tango Puzzle:

Cells with Known Value

In our problem, this one is the easiest constraint. As mentioned, some cells in the Tango puzzle are already assigned a value and you can not change them. so essentially the constraint is that a certain values are assigned to them. For example:

For example in the puzzle that was shared earlier, the very first cell, on top left is assigned 0 (moon). So your constraint is:

    \[x_{0,0} = 0\]

Like wise the last cell on the first row is assigned 1 (sun), so:

    \[x_{0,5} = 1\]

You might ask, if the value for those decision variables are already decided, they are not much of a decision variables then? and you are absolutely right. We could have decided to not assign a decision variable a variable that we already know the answer for it. But remember that most optimization solvers (at least those that are useful), before even getting to solve a problem (or optimize a problem) they run a pre-solve step, that its main goal is to reduce the size of the problem. So, if you can, by all means do reduce the size of the decision variables; but try to first making sure that you have modeled the problem right. Particularly for a problem of the size of Tango puzzle and such constraints, no need to worry about them. The pre-solve will take care of them.

Cell with Opposite/Similar values

The cell with opposite values are simple too define. For example in our little problem, the second and third cell must have a different value so we have:

    \[x_{0,1} \ne x_{0,2}\]

Likewise, for the cells with the same values, such as the 4th and 5th cell on the bottom row we have:

    \[x_{5,3} = x_{5,4}\]

No more than two moons or suns next to each other horizontally or vertically

There are multiple way to do this. One easier way to do it is to take any 3 cells adjacent to each other either horizontally (within a row) or vertically (within a column), and these are the conditions that you can happen:

Cell 1Cell 2Cell 3Acceptable
MoonMoonMoonNo
MoonMoonSunYes
MoonSunMoonYes
MoonSunSunYes
SunMoonMoonYes
SunMoonSunYes
SunSunMoonYes
SunSunSunNo

Remember that Moon = 0 and Sun == 1; So the sum of decision variables if it adds up to zero (moon,moon,moon) or if it adds up to 3 (sun,sun,sun) are not acceptable; All the other conditions are. For 3 cells that are adjacent horizontally, we can express that as:

    \[x_{i,j} + x_{i,j+1} + x_{i,j+2} \ne 0 x_{i,j} + x_{i,j+1} + x_{i,j+2} \ne 1\]

and for 3 cells adjacent vertically we have:

    \[x_{i,j} + x_{i+1,j} + x_{i+2,j} \ne 0 x_{i,j} + x_{i+1,j} + x_{i+2,j} \ne 3\]

remember that you need to do that for every 3 adjacent cells. In each row, you have 6 cells (in the above example. That means you can find 4 combination of 3 cells adjacent as follows:

  • x_{0,0}, x_{1,1}, x_{1,2}
  • x_{0,1}, x_{1,2}, x_{1,3}
  • x_{0,2}, x_{1,3}, x_{1,4}
  • x_{0,3}, x_{1,4}, x_{1,5}

There are 6 rows in total, hence, 24 combinations of 3 cells adjacent horizontally. The same goes for vertical direction. That brings the total combinations up to 48. Notice that we are essentially defining two constraints for each combination (\cdots \ne 0 and \cdots \ne 3).

That is 96 constraints in total for such a toy problem just for one of the rules. Imagine real world problems.

How I do that in OR-Tools?

Let's see what we did above and how that translates to OR-Tools. The first step is to of course installing OR-Tools. We are going to use Python here and fortunately to install OR-Tool in python all you need to do is:

pip install ortools

If you want to learn more about how to install OR-Tools refer to this link.

Now let's implement the steps we went through in former sections using OR-Tools

First Step: (no! not decision variables; even before that) Defining a model

Yes; indeed the first thing that we did, is that we started by providing a model for our problem. Fortunately, it is much easier to do that with OR-Tools (and it is always the same for all problems).

from ortools.sat.python.cp_model import CpModel

model = CpModel()

That's it. You are done!

Defining The Decision Variables

Remember in this problem our decision variables where binary type (or bool type). You can achieve this in OR-Tools by doing:

model_variables = [
    [
        model.NewBoolVar(f"c_{row_idx}_{col_idx}")
        for col_idx in range(n_columns)
    ]
    for row_idx in range(n_rows)    
]

Notice that we are putting the variables in an list of list variable called "model_variables". That helps us to reference the decision variables easier later. Don't worry about 'f"c_{row_idx}_{col_idx}"' right now. You just need a string type name for each decision variable. So, that's how we are choosing a name.

Cells with known values

We can define a method that takes care of this as follows:

model.add(
    model_variables[row][col] = value
)

Cells with opposite or the same value

# For the cells with opposite value
model.add(
    model_variables[row_cel_1][col_cel_1] != model_variables[row_cel_2][col_cel_2]
)

# For the cells with the same value
model.add(
    model_variables[row_cel_1][col_cel_1] == model_variables[row_cel_2][col_cel_2]
)

No more than 2 moon or sun adjacent

This one can be implemented using OR-Tools as:

for row_idx in range(self.n_rows):
    for col_idx in range(self.n_columns - 2):
        self.model.add(sum(self._model_variables[row_idx][col_idx:col_idx+3]) != 0)
        self.model.add(sum(self._model_variables[row_idx][col_idx:col_idx+3]) != 3)

The last Step (actually we didn’t do this above) Solve the problem

Well, we didn't really do this step in previous section. But how do we actually solve it? well, in OR-Tools is as simple as:

from ortools.sat.python.cp_model import CpSolver

solver = CpSolver()
solver.solve(model)

That's it. That's how you solve it using OR-Tools.

What is going to happen when you call solve? A lot of thing which is backed by hundreds and hundreds of years of mathematics. But we are not going over those in this post; and that's why we didnot focus on it in previous section.

Putting it all together

You saw some snippet of codes here and there showing how to use OR-Tools to implement the mathematical model for the Tango Puzzle. But we need to put them all together in a working code.

That means we need to get the input from the user, initialize the variables and objects, check the validity of the input, form the model, enforce the constraints, solve the problem, and more importantly get the solution out and represent it.

So, yes, we are done with the math part of the code, but a lot of other stuff still remains.

Here is one full example of putting it all together:

from typing import Optional
from dataclasses import dataclass

from ortools.sat.python.cp_model import CpModel, CpSolver, IntVar, OPTIMAL
from tabulate import tabulate

MOON: str = "\U0001F319"
SUN: str = "\U0001F31E"

@dataclass
class Cell:
    row_idx: int
    col_idx: int

    def is_horizontally_adjecent_to(self, cell: "Cell") -> bool:
        return (
            (self.row_idx == cell.row_idx) and 
            (abs(self.col_idx -  cell.col_idx) == 1)
        )

    def is_vertically_adjecent_to(self, cell: "Cell") -> bool:
        return (
            (self.col_idx == cell.col_idx) and 
            (abs(self.row_idx -  cell.row_idx) == 1)
        )

    def is_adjacent_to(self, cell: "Cell") -> bool:
        return self.is_horizontally_adjecent_to(cell) or self.is_vertically_adjecent_to(cell)

    @staticmethod
    def order(cell_1: "Cell", cell_2: "Cell") -> tuple["Cell", "Cell"]:
        if cell_1.is_horizontally_adjecent_to(cell_2):
            return (
                (cell_1, cell_2)
                if cell_1.col_idx < cell_2.col_idx else
                (cell_2, cell_1)
            )
        elif cell_1.is_vertically_adjecent_to(cell_2):
            return (
                (cell_1, cell_2)
                if cell_1.row_idx < cell_2.row_idx else
                (cell_2, cell_1)
            )
        else:
            raise ValueError("Cells must be adjacent, to be ordered.")

class TangoSolver:
    def __init__(
        self, 
        n_columns: int, 
        n_rows: int, 
        opposite_value_cells: list[tuple[Cell, Cell]],
        same_value_cells: list[tuple[Cell, Cell]],
        known_value_cells: list[tuple[Cell, int]],
    ):
        if n_columns % 2 != 0:
            raise ValueError(f"Number of columns ({n_columns}) must be an even number.")

        if n_rows % 2 != 0:
            raise ValueError(f"Number of rows ({n_rows}) must be an even number.")

        self._n_columns: int = n_columns
        self._n_rows: int = n_rows

        self._model_variables: list[list[IntVar]] = []

        self._model: Optional[CpModel] = None
        self._solver: Optional[CpSolver] = None

        self._opposite_value_cells: list[tuple[Cell, Cell]] = []
        self._same_value_cells: list[tuple[Cell, Cell]] = []
        self._known_value_cells: list[tuple[Cell, int]] = []
        
        self.opposite_value_cells = opposite_value_cells
        self.same_value_cells = same_value_cells
        self.known_value_cells = known_value_cells

    @property
    def n_columns(self) -> int:
        return self._n_columns

    @property
    def n_rows(self) -> int:
        return self._n_rows

    @property
    def opposite_value_cells(self) -> list[tuple[Cell, Cell]]:
        return self._opposite_value_cells

    @opposite_value_cells.setter
    def opposite_value_cells(self, values: list[tuple[Cell, Cell]]):
        self._opposite_value_cells = [
            Cell.order(
                self.is_valid_cell(cell_1),
                self.is_valid_cell(cell_2)
            )
            for cell_1, cell_2 in values
        ]

    @property
    def same_value_cells(self) -> list[tuple[Cell, Cell]]:
        return self._same_value_cells

    @same_value_cells.setter
    def same_value_cells(self, values: list[tuple[Cell, Cell]]):
        self._same_value_cells = [
            Cell.order(
                self.is_valid_cell(cell_1),
                self.is_valid_cell(cell_2)
            )
            for cell_1, cell_2 in values
        ]
        
    @property
    def known_value_cells(self) -> list[Cell]:
        return self._known_value_cells

    @known_value_cells.setter
    def known_value_cells(self, cell_value_tuple: list[tuple[Cell, int]]):
        self._known_value_cells = [
            (self.is_valid_cell(cell), self.is_valid_value(value))
            for cell, value in cell_value_tuple
        ]

    @property
    def model(self) -> CpModel:
        if self._model is None:
            self._model = CpModel()
        return self._model

    @property
    def solver(self) -> CpSolver:
        if self._solver is None:
            self._solver = CpSolver()
        return self._solver

    def is_valid_row_idx(self, row_idx: int) -> int:
        if (row_idx < 0) or (row_idx >= self.n_rows):
            raise ValueError(f"row_idx ({row_idx}) must be between 0 and {self.n_rows - 1}.")

        return row_idx

    def is_valid_col_idx(self, col_idx: int) -> int:
        if (col_idx < 0) or (col_idx >= self.n_columns):
            raise ValueError(f"col_idx ({col_idx}) must be between 0 and {self.n_columns - 1}.")

        return col_idx

    def is_valid_cell(self, cell: Cell) -> Cell:
        return Cell(
            self.is_valid_row_idx(cell.row_idx),
            self.is_valid_col_idx(cell.col_idx)
        )

    @staticmethod
    def is_valid_value(value: int) -> int:
        if value not in {0, 1}:
            raise ValueError(f"value ({value}) must be either 0 (moon) or sun(1).")

        return value

    def get_variable(self, row_idx: int, col_idx: int) -> IntVar:
        return self._model_variables[self.is_valid_row_idx(row_idx)][self.is_valid_col_idx(col_idx)]

    def get_value(self, row_idx: int, col_idx: int) -> int:
        return self.solver.value(self.get_variable(row_idx, col_idx))

    def get(self, cell: Cell):
        return self.get_variable(cell.row_idx, cell.col_idx)

    def get_cell_value(self, cell: Cell) -> int:
        return self.get_value(cell.row_idx, cell.col_idx)

    def _initialize_model(self) -> None:
        self._model = None
        self._solver = None
        self._model_variables = [
            [
                self.model.NewBoolVar(self.get_cell_name(row_idx, col_idx))
                for col_idx in range(self.n_columns)
            ]
            for row_idx in range(self.n_rows)    
        ]
        
        # no more than two consecutive Moon or Sun in a row
        for row_idx in range(self.n_rows):
            for col_idx in range(self.n_columns - 2):
                self.model.add(sum(self._model_variables[row_idx][col_idx:col_idx+3]) != 0)
                self.model.add(sum(self._model_variables[row_idx][col_idx:col_idx+3]) != 3)

        # no more than two consecutive moon or sun in a column
        for col_idx in range(self.n_columns):
            for row_idx in range(self.n_rows - 2):
                tmp_array = [
                    self.get_variable(row_idx, col_idx),
                    self.get_variable(row_idx + 1, col_idx),
                    self.get_variable(row_idx + 2, col_idx),
                ]
                self.model.add(sum(tmp_array) != 0)
                self.model.add(sum(tmp_array) != 3)

        # Same Number of Sun and Moon in each row:
        for row_idx in range(self.n_rows):
                self.model.add(sum(self._model_variables[row_idx][:]) == (self.n_columns//2))

        # Same Number of Sun and Moon in each column;
        for col_idx in range(self.n_columns):
            self.model.add(
                sum([
                    self._model_variables[row_idx][col_idx]
                    for row_idx in range(self.n_rows)
                ]) == (self.n_rows//2)
            )
                

    def add_opposite_values_constraint(self, cell_1: Cell, cell_2: Cell) -> "TangoSolver":
        if not cell_1.is_adjacent_to(cell_2):
            raise ValueError(f"The cells are not adjacents. cell_1: {cell_1} and cell_2: {cell_2}")
            
        self.model.add(self.get(cell_1) != self.get(cell_2))
        
        return self

    def add_same_values_constraints(self, cell_1: Cell, cell_2: Cell) -> "TangoSolver":
        if not cell_1.is_adjacent_to(cell_2):
            raise ValueError(f"The cells are not adjacents. cell_1: {cell_1} and cell_2: {cell_2}")
            
        self.model.add(self.get(cell_1) == self.get(cell_2))
        
        return self
    
    def add_known_values_constraint(self, cell: Cell, value: int) -> "TangoSolver":
        self.model.add(self.get(self.is_valid_cell(cell)) == self.is_valid_value(value))

        return self

    @staticmethod
    def get_cell_name(row_idx: int, col_idx: int) -> str:
        return f"c_{row_idx}_{col_idx}"

    def solve(self, print_solution: bool = False) -> bool:
        self._initialize_model()

        # enforce opposite value cells
        for cell_1, cell_2 in self.opposite_value_cells:
            self.add_opposite_values_constraint(cell_1, cell_2)

        # enforce same value cells
        for cell_1, cell_2 in self.same_value_cells:
            self.add_same_values_constraints(cell_1, cell_2)

        # enforce known value cells
        for cell, value in self.known_value_cells:
            self.add_known_values_constraint(cell, value)
            
        status = self.solver.solve(self.model)

        output = status == OPTIMAL
        if output and print_solution:
            solution = [
                [
                    SUN if self.get_value(row_idx, col_idx) == 1 else MOON
                    for col_idx in range(self.n_columns)
                ]
                for row_idx in range(self.n_rows)    
            ]

            print(tabulate(solution, tablefmt="grid"))

        return output

Does it even work?

Let's try it for the puzzle we show on top of this post:

tango_solver = TangoSolver(
    n_columns=6, 
    n_rows=6, 
    opposite_value_cells=[
        (Cell(0, 1), Cell(0, 2)),
        (Cell(0, 3), Cell(0, 4)),
        (Cell(1, 0), Cell(2, 0)),
        (Cell(3, 0), Cell(4, 0)),
        (Cell(1, 5), Cell(2, 5)),
        (Cell(5, 1), Cell(5, 2)),
    ],
    same_value_cells=[
        (Cell(5, 3), Cell(5, 4)),
        (Cell(3, 5), Cell(4, 5)),
    ],
    known_value_cells=[
        (Cell(0, 0), 0),
        (Cell(0, 5), 1),
        (Cell(1, 1), 0),
        (Cell(1, 4), 0),
        (Cell(4, 1), 0),
        (Cell(4, 5), 0),
        (Cell(5, 0), 1),
        (Cell(5, 5), 1),
    ],
)

if tango_solver.solve(print_solution=True):
    print("Found a solution.")
else:
    print("Failed to find a solution.")

And the output you get is:

+----+----+----+----+----+----+
| 🌙 | 🌞 | 🌙 | 🌙 | 🌞 | 🌞 |
+----+----+----+----+----+----+
| 🌞 | 🌙 | 🌞 | 🌞 | 🌙 | 🌙 |
+----+----+----+----+----+----+
| 🌙 | 🌞 | 🌙 | 🌙 | 🌞 | 🌞 |
+----+----+----+----+----+----+
| 🌙 | 🌞 | 🌙 | 🌞 | 🌞 | 🌙 |
+----+----+----+----+----+----+
| 🌞 | 🌙 | 🌞 | 🌞 | 🌙 | 🌙 |
+----+----+----+----+----+----+
| 🌞 | 🌙 | 🌞 | 🌙 | 🌙 | 🌞 |
+----+----+----+----+----+----+
Found a solution.

Leave a Reply

Your email address will not be published. Required fields are marked *