Solving LinkedIn Queens by Linear Optimization

Problem Modeling¶

Before solving Queens, it is necessary to translate the game elements into the following components of the LOP:

• Ranges

• Sets

• Decision Variables

• Objective Function

• Constraints

Ranges¶

Defining the ranges is a fundamental step for the proper definition of the other components of the LOP. For the case of Queens, three ranges will be considered:

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

Range of rows, where $n$ is the total number of rows on the board (in this case, $n$ = 7)

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

Range of columns, where $n$ is the total number of columns on the board (also $n$ = 7 for this case)

$K = \{1, \cdots, p\}$

Range of colored regions in game, where $p$ is the total number of regions on the board ($p$ = 7)

Sets¶

By defining the ranges $I$ and $J$, let’s define three sets for solving the Queens game:

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

Set of all squares $(i, j)$ on the board, which is nothing more than the Cartesian product of the ranges $I$ and $J$

$R = \{((i,j),k) \mid (i,j) \in H, k \in K\}$

Set of colored regions and says to which region $k$ a square $(i,j)$ belongs.

$D = \begin{array}{cr} \{((i,j), (i+1,j+1)) \mid (i,j), (i+1,j+1) \in H\} & \cup \\ \{((i,j), (i+1,j-1)) \mid (i,j), (i+1,j-1) \in H\} & \end{array}$

Set of all pairs of diagonally adjacent squares. This set will be useful so to make defining the constraints easier later on.

Decision variables¶

The decision variables will be binary variables $x_{ij}$, which will assume only two values:

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

$x_{ij} = 1$, if the crown is located in row $i$ and column $j$;

$x_{ij} = 0$, otherwise.

Objective function¶

The interesting thing about the Queens game is that, since we don"t have an objective function to maximize or minimize, we are not actually dealing with an optimization problem, but rather a feasibility problem, that is, our objective is only to find a feasible solution that meets all the game’s constraints. Because of this, we can define the objective function as minimizing (or maximizing, it doesn"t matter) an arbitrary constant. Thus, the objective function will not depend on the decision variables, so that the model doesn"t seek to optimize it and only worries about meeting the constraints.

Constraints¶

With the previous elements well defined, we can finally translate Queens’ rules into constraints for our BLOP model. Let’s go step by step:

Binarity Constraints

The first constraint we need to define right away is that all decision variables in our problem are binary variables, meaning they only accept 0 and 1 as valid values.

$$x_{ij} \in \B, \forall i \in I, \forall j \in J$$

(2)

Single-Crown-Per-Row Constraints

Since each row on the board must have only one crown, the sum of all $x_{ij}$ belonging to a row $i$ must equal 1. As there are 7 rows in total, there will be 7 such constraints, one for each row.

$$\sum_{j \in J}{x_{ij}} = 1, \forall i \in I$$

(3)

Single-Crown-Per-Column Constraints

The same logic applies to the columns. Since there are 7 columns on the board, there will be 7 more constraints, one for each column.

$$\sum_{i \in I}{x_{ij}} = 1, \forall j \in J$$

(4)

Single-Crown-Per-Region Constraints

The same logic also applies to the colored regions. For each region of the board, the sum of the $x_{ij}$ belonging to a region $k$ must be equal to 1. Since there are 7 regions, there will be 7 more constraints.

$$\sum_{(i,j) \in R_k}{x_{ij}} = 1, \forall k \in K$$

(5)

Diagonally-Adjacent-squares Constraints

Finally, we must not forget the rule that there cannot be adjacent crowns, not even along the diagonals. The cases of vertical and horizontal proximity do not need to be addressed, since the row and column constraints already cover this. Therefore, we only need to worry about imposing constraints for the two diagonal directions in each pair of shared-vertex squares. With the set $D$ well defined, this constraint is easily defined as it follows.

$$x_{ij} + x_{rs} \le 1, \forall ((i,j), (r,s)) \in D$$

(6)

Abstract Model¶

With all components defined, it is possible to model the game of Queens using the following abstract model.

Concrete Model¶

In this article, let’s apply LO techniques to solve the Queens No. 307, which will be an instance of the abstract model presented earlier, that is, its concrete model.

The concrete model for the game above will be the following:

S.t.:

Single-Crown-Per-Row Constraints

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

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

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

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

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

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

$x_{71} + x_{72} + x_{73} + x_{74} + x_{75} + x_{76} + x_{77} = 1$ _{(Row 7)}

Single-Crown-Per-Column Constraints

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

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

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

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

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

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

$x_{17} + x_{27} + x_{37} + x_{47} + x_{57} + x_{67} + x_{77} = 1$ _{(Column 7)}

Single-Crown-Per-Region Constraints

$x_{11} + x_{12} + x_{13} + x_{14} + x_{15} + x_{16} + x_{17} + x_{26} + x_{27} + x_{36} + x_{37} + x_{46} + x_{47} + x_{57} + x_{67} + x_{77} = 1$ _{(Purple Region)}

$x_{12} + x_{22} + x_{32} + x_{42} + x_{33} + x_{41} + x_{42} + x_{51} + x_{52} + x_{16} + x_{26} + x_{46} + x_{56} + x_{66} + x_{71} + x_{72} + x_{73} + x_{74} + x_{75} + x_{76} = 1$ _{(Orange Region)}

$x_{25} + x_{35} = 1$ _{(Blue Region)}

$x_{32} + x_{33} = 1$ _{(Green Region)}

$x_{34} + x_{43} + x_{44} + x_{45} + x_{54} = 1$ _{(Gray Region)}

$x_{53} + x_{63} = 1$ _{(Red Region)}

$x_{55} + x_{56} = 1$ _{(Yellow Region)}

Principal Diagonals Constraints

$x_{11} + x_{22} \le 1$

$x_{12} + x_{23} \le 1$

$x_{13} + x_{24} \le 1$

$x_{14} + x_{25} \le 1$

$x_{15} + x_{26} \le 1$

$x_{21} + x_{32} \le 1$

$x_{22} + x_{33} \le 1$

$x_{23} + x_{34} \le 1$

$x_{24} + x_{35} \le 1$

$x_{25} + x_{36} \le 1$

$x_{31} + x_{42} \le 1$

$x_{32} + x_{43} \le 1$

$x_{33} + x_{44} \le 1$

$x_{34} + x_{45} \le 1$

$x_{35} + x_{46} \le 1$

$x_{41} + x_{52} \le 1$

$x_{42} + x_{53} \le 1$

$x_{43} + x_{54} \le 1$

$x_{44} + x_{55} \le 1$

$x_{45} + x_{56} \le 1$

$x_{51} + x_{62} \le 1$

$x_{52} + x_{63} \le 1$

$x_{53} + x_{64} \le 1$

$x_{54} + x_{65} \le 1$

$x_{55} + x_{66} \le 1$

Secondary Diagonals Constraints

$x_{12} + x_{21} \le 1$

$x_{13} + x_{22} \le 1$

$x_{14} + x_{23} \le 1$

$x_{15} + x_{24} \le 1$

$x_{16} + x_{25} \le 1$

$x_{22} + x_{31} \le 1$

$x_{23} + x_{32} \le 1$

$x_{24} + x_{33} \le 1$

$x_{25} + x_{34} \le 1$

$x_{26} + x_{35} \le 1$

$x_{32} + x_{41} \le 1$

$x_{33} + x_{42} \le 1$

$x_{34} + x_{43} \le 1$

$x_{35} + x_{44} \le 1$

$x_{36} + x_{45} \le 1$

$x_{42} + x_{51} \le 1$

$x_{43} + x_{52} \le 1$

$x_{44} + x_{53} \le 1$

$x_{45} + x_{54} \le 1$

$x_{46} + x_{55} \le 1$

$x_{52} + x_{61} \le 1$

$x_{53} + x_{62} \le 1$

$x_{54} + x_{63} \le 1$

$x_{55} + x_{64} \le 1$

$x_{56} + x_{65} \le 1$

Binarity Constraints

$x_{12} \in \B$

$x_{13} \in \B$

$x_{14} \in \B$

$x_{15} \in \B$

$x_{16} \in \B$

$x_{17} \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_{27} \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_{37} \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_{47} \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_{57} \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$

$x_{67} \in \B$

$x_{71} \in \B$

$x_{72} \in \B$

$x_{73} \in \B$

$x_{74} \in \B$

$x_{75} \in \B$

$x_{76} \in \B$

$x_{77} \in \B$

Solving Queens¶

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

So, first of all, let’s import the Queens class and create an instance of it, passing its board dimensions as a (rows, columns) tuple and its colored regions as a dictionary of color: {squares} items, as shown bellow:

The Queens class features the model attribute, which implements a QueensModel class that, in its turn, implements the Linear Optimization logic of the Queens 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
import pyomo.environ as pyo


class QueensModel(pyo.ConcreteModel):
    """The Linear Optimization model for the Queens game."""

    def __init__(self, grid_dims: tuple[int, int], regions: dict[str, set[tuple[int, int]]]) -> None:
        """
        Args:
            grid_dims: Grid dimensionas as a `(rows, columns)` tuple.
            regions: All colored regions on grid as a dictionary of `color: {(row, column), ...}` items.
        """
        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
        K = self.K = pyo.Set(initialize=regions.keys()) # Colored Regions

        # COMPOSITE SETS
        S = self.S = pyo.Set(initialize=lambda model: [(i, j) for i in I for j in J]) # Grid Squares
        R = self.R = pyo.Set(K, initialize=regions, dimen=2, domain=S) # Region Squares
        D = self.D = pyo.Set(initialize=lambda model: # Diagonals
            [((i, j), (i + 1, j + 1)) for (i, j) in S if (i + 1, j + 1) in S] +
            [((i, j), (i + 1, j - 1)) for (i, j) in S if (i + 1, j - 1) in S]
        )

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

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

        # CONSTRAINTS
        self.single_crown_per_row_constraints = pyo.Constraint(
            I, rule=lambda model, i: pyo.quicksum(x[i, j] for j in J) == 1
        )
        self.single_crown_per_column_constraints = pyo.Constraint(
            J, rule=lambda model, j: pyo.quicksum(x[i, j] for i in I) == 1
        )
        self.single_crown_per_region_constraints = pyo.Constraint(
            K, rule=lambda model, k: pyo.quicksum(x[i, j] for (i, j) in R[k]) == 1
        )
        self.adjacent_squares_by_vertex_constraints = pyo.Constraint(
            D, rule=lambda model, i, j, r, s: x[i, j] + x[r, s] <= 1
        )

With model constructed, the public method solve() calls internally the restricted _set_solution() one to save the solution to the private attribute __crowns, which indicates the crowned squares in the game and can be accessed by the public attribute crowns.

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

        """
        The crowned squares of Queens game.

        Returns:
            Locations of all crowns as a list of squares as `(row, column)`
            or `None` if the game is not solved yet.
        """
        if not self.is_solved:
            return None
        return sorted((i+1, j+1) for (i, j) in self.__crowns.nodes())


    def _set_solution(self, verbose:bool = False) -> None:

1
2
3
4
5
6
7
8

                )
                raise ValueError(msg)



    @property
    def crowns(self) -> list[tuple[int, int]] | None:

With the solution obtained, the method show() displays the results as a Matplotlib plot showing the board with the crowned squares marked on it.

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


        x = self.model.x
        S = self.model.S
        nx.set_node_attributes(
            self.grid,
            name="value",
            values={(i-1, j-1): round(pyo.value(x[i, j])) for (i, j) in S}
        )

        crowns = [square for square, value in nx.get_node_attributes(self.grid, "value").items() if value == 1]
        self.__crowns = self.grid.subgraph(crowns)
        
        if verbose:
            print("These are the squares that contain a crown:")
            pprint(self.crowns)


    def show(self) -> None:
        """Show the Queens' grid."""
        width = height = self.size * 0.5
        plt.figure(figsize=(width, height))
        nx.draw(
            self.grid,
            pos={(i, j): (j, -i) for i, j in self.grid.nodes()},
            with_labels=True,
            arrows=False,
            labels=
                dict.fromkeys(self.__crowns.nodes(), "O") if self.__crowns is not None
                else dict.fromkeys(self.grid.nodes(), ""),
            node_size=1100,
            node_color=list(nx.get_node_attributes(self.grid, "color").values()),
            node_shape="s", # Squared-shape nodes
            width=0,
            edgecolors="black",
            linewidths=.5
        )
        plt.show()

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

The output board matches the solution of the Queens No. 307, as expected.