Solving LinkedIn Tango by Linear Optimization

Problem Modeling¶

In order to model our LOP, it will be necessary to define the following elements:

• Ranges

• Sets

• Decision variables

• Parameters

• Objective function

• Constraints

Ranges¶

$I = \{1, \cdots, n\}$

The row range, where $n$ is the total number of rows in the grid.

$J = \{1, \cdots, m\}$

The column range, where $n$ is the total number of columns in the grid.

Sets¶

In addition to the row and column ranges, it will be necessary to consider the sets of pairs of squares with = and × signs, plus the set of squares already filled with a sun or moon symbol. Therefore, there will be:

$H = I \times J = \{(i, j) \mid \forall i \in I, \forall j \in J\}$

Set of all board squares $(i, j)$, which is simply the Cartesian product of the ranges $I$ and $J$.

$M = \{(v, w) \mid v, w \in H, v \ne w\}$

Set of pairs of squares separated by =.

$O = \{(v, w) \mid v, w \in H, v \ne w\}$

Set of pairs of squares separated by ×.

$K \subset H$

Set of squares with an already filled symbol.

Decision Variables¶

The decision variables will be binary, since Tango only uses two symbols. Therefore, the LOP is actually a BLOP:

$x_{ij} \in \B, \forall (i,j) \in H$

$x_{ij} = 1$, if the square in row $i$ and column $j$ will be filled with a 🌙;

$x_{ij} = 0$, if the same square will be filled with a ☀️.

Parameters¶

In Tango, there may be some cells that already come with a predefined symbol: sun or moon. As the set of parameters in our model, there will be:

$k_{ij} \in \B, \forall (i,j) \in K$

$k_{ij} = 1$, if the square in row $i$ and column $j$ is already filled with a 🌙;

$k_{ij} = 0$, if the same square is already filled with a ☀️.

Objective Function¶

Again, our objective is not to optimize a function, but rather to find a solution that fulfills all the rules of the game. Therefore, the Tango BLOP is not an optimization problem, but a feasibility problem. Thus, the objective function will be to minimize (or maximize, it doesn’t matter) an arbitrary constant $C$.

Constraints¶

With the previous elements well defined, we can translate the rules of the game to our BLOP as follows:

Binarity Constraints

First, we must define that all decision variables in our problem are binary variables, that is, they only accept 0 and 1 as the only possible values.

$$x_{ij} \in \B, \forall (i,j) \in H$$

(2)

Equal-Moons-Suns-Per-Row Constraints

Since the number of suns and moons for each row must be equal, the sum of $x_{ij}$ belonging to a row $i$ must equal the half of total columns, therefore 3. Since there are 6 rows, the model will have 6 of these constraints.

$$\sum_{j=1}^{m}{x_{ij}}=\frac{m}{2}, \forall i \in I$$

(3)

Equal-Moons-Suns-Per-Column Constraints

The same logic applies to the columns. Therefore, there are 6 more constraints.

$$\sum_{i=1}^{n}{x_{ij}}=\frac{n}{2}, \forall j \in J$$

(4)

No-Three-Consecutive-Moons-Per-Row Constraints

Since the 3 moons in a row cannot be next to each other, it means that the sum of three consecutive $x_{ij}$ in a row must be less than or equal to 2.

$$x_{ij} + x_{i,j+1} + x_{i,j+2} \le 2, \forall i \in I, \forall j \in \{1, \cdots, m-2\}$$

(5)

No-Three-Consecutive-Moons-Per-Column Constraints

And the same logic applies to the columns.

$$x_{ij} + x_{i+1,j} + x_{i+2,j} \le 2, \forall i \in \{1, \cdots, n-2\}, \forall j \in J$$

(6)

No-Three-Consecutive-Suns-Per-Row Constraints

Similarly, since there cannot be 3 consecutive suns in a row, the sum of 3 subsequent $x_{ij}$ in a row i must be greater than or equal to 1.

$$x_{ij} + x_{i,j+1} + x_{i,j+2} \ge 1, \forall i \in I, \forall j \in \{1, \cdots,m-2\}$$

(7)

No-Three-Consecutive-Suns-Per-Column Constraints

And the same logic applies to the columns.

$$x_{ij} + x_{i+1,j} + x_{i+2,j} \ge 1, \forall i \in \{1, \cdots, n-2\}, \forall j \in J$$

(8)

Already-Filled-squares Constraints

For each square that already has a pre-established figure, it is necessary to impose that $x_{ij}$ is equal to 1 or 0, depending on whether the figure is a moon or a sun, respectively.

$$x_{ij} = k_{ij}, \forall k_{ij} \in K$$

(9)

Matching-Pairs Constraints

For each pair of adjacent cells that contains the = sign between them, it is necessary to impose the constraint that the values $x_{ij}$ of that pair are equal, which is the same as saying that the difference between the values $x_{ij}$ of that pair must be equal to 0.

$$x_v - x_w = 0, \forall \{v,w\} \in M$$

(10)

Opposite-Pairs Constraints

Finally, for each pair of adjacent cells that contains the sign × between them, it is necessary to impose the constraint that the values $x_{ij}$ of this pair are different, which is the same as saying that the sum of the values $x_{ij}$ of this pair must be equal to 1.

$$x_v + x_w = 1, \forall \{v,w\} \in O$$

(11)

Abstract Model¶

Up to this point, the formulas created have been based on the premise that every Tango minigame will have 6 rows and 6 columns, which is indeed the case. However, in order to create a more generalized abstract model, we can admit that this will not always be a certainty, and therefore there is a possibility that the number of rows and columns will vary from game to game. Due to the restriction that the number of moons and suns for each row and column must be equal, it must be assumed that the total number of rows and columns are even numbers, that is, $n \mod 2 \equiv 0$ and $m \mod 2 \equiv 0$.

Thus, having raised these points, the abstract model of the Tango minigame is formulated as follows:

Concrete Model¶

The concrete model was built based on the Tango minigame No. 151

S.t.:

Equal-Moons-Suns-Per-Row Constraints

$x_{11} + x_{12} + x_{13} + x_{14} + x_{15} + x_{16} = 3$ _{(Row 1)}

$x_{21} + x_{22} + x_{23} + x_{24} + x_{25} + x_{26} = 3$ _{(Row 2)}

$x_{31} + x_{32} + x_{33} + x_{34} + x_{35} + x_{36} = 3$ _{(Row 3)}

$x_{41} + x_{42} + x_{43} + x_{44} + x_{45} + x_{46} = 3$ _{(Row 4)}

$x_{51} + x_{52} + x_{53} + x_{54} + x_{55} + x_{56} = 3$ _{(Row 5)}

$x_{61} + x_{62} + x_{63} + x_{64} + x_{65} + x_{66} = 3$ _{(Row 6)}

Equal-Moons-Suns-Per-Column Constraints

$x_{11} + x_{21} + x_{31} + x_{41} + x_{51} + x_{61} = 3$ _{(Column 1)}

$x_{12} + x_{22} + x_{32} + x_{42} + x_{52} + x_{62} = 3$ _{(Column 2)}

$x_{13} + x_{23} + x_{33} + x_{43} + x_{53} + x_{63} = 3$ _{(Column 3)}

$x_{14} + x_{24} + x_{34} + x_{44} + x_{54} + x_{64} = 3$ _{(Column 4)}

$x_{15} + x_{25} + x_{35} + x_{45} + x_{55} + x_{65} = 3$ _{(Column 5)}

$x_{16} + x_{26} + x_{36} + x_{46} + x_{56} + x_{66} = 3$ _{(Column 6)}

No-Three-Consecutive-Moons-Per-Row Constraints

$x_{11} + x_{21} + x_{31} \le 2$ _{(Row 1)}

$x_{12} + x_{13} + x_{14} \le 2$ _{(Row 1)}

$x_{13} + x_{14} + x_{15} \le 2$ _{(Row 1)}

$x_{14} + x_{15} + x_{16} \le 2$ _{(Row 1)}

$x_{21} + x_{22} + x_{23} \le 2$ _{(Row 2)}

$x_{22} + x_{23} + x_{24} \le 2$ _{(Row 2)}

$x_{23} + x_{24} + x_{25} \le 2$ _{(Row 2)}

$x_{24} + x_{25} + x_{26} \le 2$ _{(Row 2)}

$x_{31} + x_{32} + x_{33} \le 2$ _{(Row 3)}

$x_{32} + x_{33} + x_{34} \le 2$ _{(Row 3)}

$x_{33} + x_{34} + x_{35} \le 2$ _{(Row 3)}

$x_{34} + x_{35} + x_{36} \le 2$ _{(Row 3)}

$x_{41} + x_{42} + x_{43} \le 2$ _{(Row 4)}

$x_{42} + x_{43} + x_{44} \le 2$ _{(Row 4)}

$x_{43} + x_{44} + x_{45} \le 2$ _{(Row 4)}

$x_{44} + x_{45} + x_{46} \le 2$ _{(Row 4)}

$x_{51} + x_{52} + x_{53} \le 2$ _{(Row 5)}

$x_{52} + x_{53} + x_{54} \le 2$ _{(Row 5)}

$x_{53} + x_{54} + x_{55} \le 2$ _{(Row 5)}

$x_{54} + x_{55} + x_{56} \le 2$ _{(Row 5)}

$x_{61} + x_{62} + x_{63} \le 2$ _{(Row 6)}

$x_{62} + x_{63} + x_{64} \le 2$ _{(Row 6)}

$x_{63} + x_{64} + x_{65} \le 2$ _{(Row 6)}

$x_{64} + x_{65} + x_{66} \le 2$ _{(Row 6)}

No-Three-Consecutive-Moons-Per-Column Constraints

$x_{11} + x_{21} + x_{31} \le 2$ _{(Column 1)}

$x_{21} + x_{31} + x_{41} \le 2$ _{(Column 1)}

$x_{31} + x_{41} + x_{51} \le 2$ _{(Column 1)}

$x_{41} + x_{51} + x_{61} \le 2$ _{(Column 1)}

$x_{12} + x_{22} + x_{32} \le 2$ _{(Column 2)}

$x_{22} + x_{32} + x_{42} \le 2$ _{(Column 2)}

$x_{32} + x_{42} + x_{52} \le 2$ _{(Column 2)}

$x_{42} + x_{52} + x_{62} \le 2$ _{(Column 2)}

$x_{13} + x_{23} + x_{33} \le 2$ _{(Column 3)}

$x_{23} + x_{33} + x_{43} \le 2$ _{(Column 3)}

$x_{33} + x_{43} + x_{53} \le 2$ _{(Column 3)}

$x_{43} + x_{53} + x_{63} \le 2$ _{(Column 3)}

$x_{14} + x_{24} + x_{34} \le 2$ _{(Column 4)}

$x_{24} + x_{34} + x_{44} \le 2$ _{(Column 4)}

$x_{34} + x_{44} + x_{54} \le 2$ _{(Column 4)}

$x_{44} + x_{54} + x_{64} \le 2$ _{(Column 4)}

$x_{15} + x_{25} + x_{35} \le 2$ _{(Column 5)}

$x_{25} + x_{35} + x_{45} \le 2$ _{(Column 5)}

$x_{35} + x_{45} + x_{55} \le 2$ _{(Column 5)}

$x_{45} + x_{55} + x_{65} \le 2$ _{(Column 5)}

$x_{16} + x_{26} + x_{36} \le 2$ _{(Column 6)}

$x_{26} + x_{36} + x_{46} \le 2$ _{(Column 6)}

$x_{36} + x_{46} + x_{56} \le 2$ _{(Column 6)}

$x_{46} + x_{56} + x_{66} \le 2$ _{(Column 6)}

No-Three-Consecutive-Suns-Per-Row Constraints

$x_{11} + x_{21} + x_{31} \ge 1$ _{(Row 1)}

$x_{12} + x_{13} + x_{14} \ge 1$ _{(Row 1)}

$x_{13} + x_{14} + x_{15} \ge 1$ _{(Row 1)}

$x_{14} + x_{15} + x_{16} \ge 1$ _{(Row 1)}

$x_{21} + x_{22} + x_{23} \ge 1$ _{(Row 2)}

$x_{22} + x_{23} + x_{24} \ge 1$ _{(Row 2)}

$x_{23} + x_{24} + x_{25} \ge 1$ _{(Row 2)}

$x_{24} + x_{25} + x_{26} \ge 1$ _{(Row 2)}

$x_{31} + x_{32} + x_{33} \ge 1$ _{(Row 3)}

$x_{32} + x_{33} + x_{34} \ge 1$ _{(Row 3)}

$x_{33} + x_{34} + x_{35} \ge 1$ _{(Row 3)}

$x_{34} + x_{35} + x_{36} \ge 1$ _{(Row 3)}

$x_{41} + x_{42} + x_{43} \ge 1$ _{(Row 4)}

$x_{42} + x_{43} + x_{44} \ge 1$ _{(Row 4)}

$x_{43} + x_{44} + x_{45} \ge 1$ _{(Row 4)}

$x_{44} + x_{45} + x_{46} \ge 1$ _{(Row 4)}

$x_{51} + x_{52} + x_{53} \ge 1$ _{(Row 5)}

$x_{52} + x_{53} + x_{54} \ge 1$ _{(Row 5)}

$x_{53} + x_{54} + x_{55} \ge 1$ _{(Row 5)}

$x_{54} + x_{55} + x_{56} \ge 1$ _{(Row 5)}

$x_{61} + x_{62} + x_{63} \ge 1$ _{(Row 6)}

$x_{62} + x_{63} + x_{64} \ge 1$ _{(Row 6)}

$x_{63} + x_{64} + x_{65} \ge 1$ _{(Row 6)}

$x_{64} + x_{65} + x_{66} \ge 1$ _{(Row 6)}

No-Three-Consecutive-Suns-Per-Column Constraints

$x_{11} + x_{21} + x_{31} \ge 1$ _{(Column 1)}

$x_{21} + x_{31} + x_{41} \ge 1$ _{(Column 1)}

$x_{31} + x_{41} + x_{51} \ge 1$ _{(Column 1)}

$x_{41} + x_{51} + x_{61} \ge 1$ _{(Column 1)}

$x_{12} + x_{22} + x_{32} \ge 1$ _{(Column 2)}

$x_{22} + x_{32} + x_{42} \ge 1$ _{(Column 2)}

$x_{32} + x_{42} + x_{52} \ge 1$ _{(Column 2)}

$x_{42} + x_{52} + x_{62} \ge 1$ _{(Column 2)}

$x_{13} + x_{23} + x_{33} \ge 1$ _{(Column 3)}

$x_{23} + x_{33} + x_{43} \ge 1$ _{(Column 3)}

$x_{33} + x_{43} + x_{53} \ge 1$ _{(Column 3)}

$x_{43} + x_{53} + x_{63} \ge 1$ _{(Column 3)}

$x_{14} + x_{24} + x_{34} \ge 1$ _{(Column 4)}

$x_{24} + x_{34} + x_{44} \ge 1$ _{(Column 4)}

$x_{34} + x_{44} + x_{54} \ge 1$ _{(Column 4)}

$x_{44} + x_{54} + x_{64} \ge 1$ _{(Column 4)}

$x_{15} + x_{25} + x_{35} \ge 1$ _{(Column 5)}

$x_{25} + x_{35} + x_{45} \ge 1$ _{(Column 5)}

$x_{35} + x_{45} + x_{55} \ge 1$ _{(Column 5)}

$x_{45} + x_{55} + x_{65} \ge 1$ _{(Column 5)}

$x_{16} + x_{26} + x_{36} \ge 1$ _{(Column 6)}

$x_{26} + x_{36} + x_{46} \ge 1$ _{(Column 6)}

$x_{36} + x_{46} + x_{56} \ge 1$ _{(Column 6)}

$x_{46} + x_{56} + x_{66} \ge 1$ _{(Column 6)}

Matching-Pairs Constraints

$x_{23} - x_{24} = 0$

$x_{21} - x_{31} = 0$

$x_{23} - x_{33} = 0$

$x_{26} - x_{36} = 0$

$x_{41} - x_{42} = 0$

$x_{63} - x_{64} = 0$

Opposite-Pairs Constraints

$x_{24} + x_{34} = 1$

$x_{33} + x_{34} = 1$

$x_{36} + x_{46} = 1$

$x_{45} + x_{46} = 1$

Already-Filled-squares Constraints

$x_{12} = 1$

$x_{15} = 1$

$x_{51} = 0$

$x_{55} = 1$

Binarity Constraints

$x_{12} \in \B$

$x_{13} \in \B$

$x_{14} \in \B$

$x_{15} \in \B$

$x_{16} \in \B$

$x_{21} \in \B$

$x_{22} \in \B$

$x_{23} \in \B$

$x_{24} \in \B$

$x_{25} \in \B$

$x_{26} \in \B$

$x_{31} \in \B$

$x_{32} \in \B$

$x_{33} \in \B$

$x_{34} \in \B$

$x_{35} \in \B$

$x_{36} \in \B$

$x_{41} \in \B$

$x_{42} \in \B$

$x_{43} \in \B$

$x_{44} \in \B$

$x_{45} \in \B$

$x_{46} \in \B$

$x_{51} \in \B$

$x_{52} \in \B$

$x_{53} \in \B$

$x_{54} \in \B$

$x_{55} \in \B$

$x_{56} \in \B$

$x_{61} \in \B$

$x_{62} \in \B$

$x_{63} \in \B$

$x_{64} \in \B$

$x_{65} \in \B$

$x_{66} \in \B$

Solving Tango¶

In order to solve the presented game, the linkedin-games library counts on Tango class, that implements the Tango game and its constraints, as well as methods to solve it and visualize the solution.

To instantiate the game, it is necessary to provide three sets of inputs regarding the game in question:

filled_squares

A dictionary of (row, column): 0 | 1 representing the pre-filled squares.

matching_pairs

A tuple of pairs of squares separated by the = symbol.

opposite_pairs

A tuple of pairs of squares separated by the × symbol.

The Tango class features the model attribute, which implements the TangoModel object to structure the Linear Optimization logic behind the Tango’s game.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
import pyomo.environ as pyo


class TangoModel(pyo.ConcreteModel):
    """The Linear Optimization Model for Tango game."""

    def __init__(self,
            grid_dims: tuple[int, int],
            filled_squares: dict[tuple[int, int], int],
            matching_pairs: list[tuple[tuple[int, int], tuple[int, int]]] | None = None,
            opposite_pairs: list[tuple[tuple[int, int], tuple[int, int]]] | None = None
        ) -> None:
        """
        Args:
            grid_dims: Grid dimensions as a `(row, column)` tuple.
            filled_squares: Starting filled squares as a dictionary of `(row, column): 0 | 1` items.
            matching_pairs: Pairs of matching squares (separated by a `=` sign)
                as a set of `((row1, column1), (row2, column2))` edges.
            opposite_pairs: Pairs of opposite squares (separated by a `×` sign)
                as a set of `((row1, column1), (row2, column2))` edges.
        """
        super().__init__()

        # BOARD DIMENSIONS
        m, n = grid_dims
        self.m = pyo.Param(initialize=m, domain=pyo.PositiveIntegers)
        self.n = pyo.Param(initialize=n, domain=pyo.PositiveIntegers)

        # RANGE SETS
        I = self.I = pyo.RangeSet(n) # Rows
        J = self.J = pyo.RangeSet(m) # Columns

        # COMPOSITE SETS
        S = self.S = pyo.Set(initialize=lambda model: [(i,j) for i in I for j in J]) # Grid Squares
        K = self.K = pyo.Set(initialize=filled_squares.keys(), dimen=2)
        M = self.M = pyo.Set(initialize=matching_pairs)
        O = self.O = pyo.Set(initialize=opposite_pairs)

        # DECISION VARIABLES
        x = self.x = pyo.Var(S, domain=pyo.Binary, initialize=0)

        # PARAMETERS
        m = self.m # Total number of rows
        n = self.n # Total number of columns
        k = self.k = pyo.Param(K, initialize=filled_squares, domain=pyo.Binary) # Filled values

        # OBJECTIVE FUNCTION
        self.obj = pyo.Objective(expr=0) # feasibility problem

        # CONSTRAINTS
        self.equal_moons_suns_per_row_constraints = pyo.Constraint(
            I, rule=lambda model, i: pyo.quicksum(x[i,j] for j in J) == n / 2
        )
        self.equal_moons_suns_per_column_constraints = pyo.Constraint(
            J, rule=lambda model, j: pyo.quicksum(x[i,j] for i in I) == m / 2
        )
        self.no_three_consecutive_moons_per_row_constraints = pyo.Constraint(
            I, pyo.RangeSet(n-2),
            rule=lambda model, i, j: x[i,j] + x[i, j+1] + x[i, j+2] <= 2
        )
        self.no_three_consecutive_suns_per_row_constraints = pyo.Constraint(
            I, pyo.RangeSet(n-2),
            rule=lambda model, i, j: x[i,j] + x[i, j+1] + x[i, j+2] >= 1
        )
        self.no_three_consecutive_moons_per_column_constraints = pyo.Constraint(
            pyo.RangeSet(m-2), J,
            rule=lambda model, i, j: x[i,j] + x[i+1, j] + x[i+2, j] <= 2
        )
        self.no_three_consecutive_suns_per_column_constraints = pyo.Constraint(
            pyo.RangeSet(m-2), J,
            rule=lambda model, i, j: x[i,j] + x[i+1, j] + x[i+2, j] >= 1
        )
        self.already_filled_squares_constraints = pyo.Constraint(
            K, rule=lambda model, i, j: x[i,j] == k[i,j]
        )
        self.matching_pairs_constraints = pyo.Constraint(
            M, rule=lambda model, i, j, r, s: x[i,j] - x[r, s] == 0
        )
        self.opposite_pairs_constraints = pyo.Constraint(
            O, rule=lambda model, i, j, r, s: x[i,j] + x[r, s] == 1
        )

After the model is built, the public method solve() calls the restricted method _set_solution() to save the solution to _board property, which is a NetworkX Graph representing the game’s board.

1
2
3
4
5
6
7
8
9
10
11
12

        
        invalid_items = [
            square for pair in values for square in pair for coord in square
            if not isinstance(coord, int) or coord < 1
        ]
        if invalid_items:
            msg = f"Coordinates must be positive integers. Invalid squares: {invalid_items!r}."
            raise ValueError(msg)

        invalid_items = [pair for pair in values if self._taxicab_distance(*pair) != 1]
        if invalid_items:

With the solution obtained, the method show() can be called to plot the Tango’s board.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

            msg = f"Squares in a pair must be consecutive ones. Invalid pairs: {invalid_items!r}."
            raise ValueError(msg)
        
        self.__opposite_pairs = list(set(values))


    def _set_solution(self, verbose:bool=False) -> None:
        S= self.model.S
        x = self.model.x
        nx.set_node_attributes(
            self._grid,
            name="value",
            values={(i-1, j-1): round(pyo.value(x[i,j])) for i, j in S}
        )
        if verbose:
            print("Tango solution:")
            pprint(self.grid_squares)


    def show(self) -> None:
        """Show Tango's grid."""

        O = self.model.O
        M = self.model.M

        plt.figure(figsize=(3, 3))
        pos = {(i, j): (j, -i) for i, j in self.grid.nodes()}
        nx.draw(
            self.grid,
            pos= pos,
            arrows=False,
            with_labels= True,
            labels= nx.get_node_attributes(self.grid, "value"),
            node_size= 1100,
            node_color= [
                "#EEEAE7" if (i+1,j+1) in self.filled_squares else "white"
                for (i, j) in self.grid.nodes()
            ],
            node_shape="s",
            edgecolors="#EEEAE7",
            linewidths=1,
            width=0,
            edgelist=
                [((i-1, j-1), (r-1, s-1)) for i,j,r,s in O] +
                [((i-1, j-1), (r-1, s-1)) for i,j,r,s in M]
        )
        nx.draw_networkx_edge_labels(
            self._grid,
            pos= pos,
            edge_labels=
                {((i-1, j-1), (r-1, s-1)): "×" for i,j,r,s in O} |
                {((i-1, j-1), (r-1, s-1)): "=" for i,j,r,s in M},
            font_color="#887658"
        )
        plt.show()

So to solve the game and display its results, just call the public methods solve() and show(), at this order.

As expected, the image result matches the solution of Tango No. 151