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, \quad \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¶

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, i.e., 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, \quad \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, \quad \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, \quad \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, \quad \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, \quad \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 size and its colored regions as a dictionary of color: {squares} items, as shown bellow:

The method solve() class a modeler to implement the Linear Optimization logic of the Queens game before solving 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
39
40
41
42
43
44
45
46
47
48
49
import pyomo.environ as pyo

from .._shared.optimization.modeler.opt_modeler import OptModeler
from ._game_grid import QueensGrid


class QueensOptModeler(OptModeler[QueensGrid]):

    def _set_range_sets(self) -> None:
        super()._set_range_sets()
        self._model.K = pyo.Set(initialize=self._game.regions.keys()) # Colored Regions

    def _set_composite_sets(self) -> None:
        super()._set_composite_sets()
        self._model.R = pyo.Set( # Region Squares
            self._model.K,
            initialize=self._game.regions,
            dimen=2,
            domain=self._model.S
        )
        self._model.D = pyo.Set( # Diagonals
            initialize=lambda model:
                [((i, j), (i + 1, j + 1)) for (i, j) in model.S if (i + 1, j + 1) in model.S] +
                [((i, j), (i + 1, j - 1)) for (i, j) in model.S if (i + 1, j - 1) in model.S]
        )

    def _set_parameters(self) -> None:
        super()._set_parameters()

    def _set_decision_variables(self) -> None:
        self._model.x = pyo.Var(self._model.S, domain=pyo.Binary, initialize=0)

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

The method display(), in its turn, calls a renderer to show the Queens 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
39
40
import matplotlib.pyplot as plt
import networkx as nx

from .._shared.visualization.renderer.renderer import GameRenderer
from ._game_grid import QueensGrid


class QueensRenderer(GameRenderer[QueensGrid]):

    def _set_grid(self) -> None:
        super()._set_grid()
        nx.set_node_attributes( # Adding a color for each square on the grid
            self._grid,
            name="color",
            values={
                (i-1, j-1): color_code
                for color_code, squares in self._game.regions.items()
                for (i, j) in squares
            }
        )

    def display(self) -> None:
        plt.figure(figsize=(self._width, self._height))
        nx.draw(
            self._grid,
            pos={(i, j): (j, -i) for i, j in self._grid.nodes()},
            with_labels=True,
            arrows=False,
            labels={
                (i-1, j-1): "" if not value else "O" if value == 1 else ""
                for (i, j), value in self._game.squares.items()
            },
            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 display().

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