Skip to article frontmatterSkip to article content
Site not loading correctly?

This may be due to an incorrect BASE_URL configuration. See the MyST Documentation for reference.

Solving LinkedIn Queens by Linear Optimization

Queens Banner

Queens is a daily game available on LinkedIn as part of the platform’s strategy to increase user engagement. Personally, I found it a really cool game for testing logical reasoning and problem-solving (it even made me rack my brain over some of the problems). Based on the game’s rules, I realized it could be easily solved using Linear Programming, which turned out to be a great opportunity to apply what I learned in Operations Research courses during my university years. For this, I used Pyomo, a Python library geared towards mathematical modeling.

Linear Optimization

Linear Optimization (LO) is an area of Applied Mathematics that deals with deterministic optimization problems. For a model to represent a Linear Optimization Problem (LOP), its objective function and constraints must be linear formulas, that is, written as a sum of products between constants and variables, as in the following example.

a1x1+a2x2+⋯+anxna_1 x_1 + a_2 x_2 + \cdots + a_n x_n

Therefore, if the objective function is not linear or the problem presents at least one non-linear constraint, then it would already be a Non-Linear Optimization Problem (NLOP) and we would need Non-Linear Programming (NLP) techniques to solve it (which fortunately is not the case for Queens 🙂).

Because the objective function and the model constraints are linear expressions, an LOP implicitly assumes at least four hypotheses in its modeling:

Proportionality
The contribution of each decision variable to the objective function and to the model constraints must be directly proportional to its value. Situations that take into account economies of scale, initial manufacturing setup costs, etc., are examples where this principle is violated.
Additivity
The contribution of each decision variable to the objective function and to the model constraints must be directly proportional to its value. Situations that take into account economies of scale, initial manufacturing setup costs, etc., are examples where this principle is violated.
Divisibility and non-negativity
Each of the decision variables can take any values within the set of positive real numbers, as long as they satisfy the model’s constraints. In the case of Queens, as will be seen later, the variables will be of the binary type, which makes our LOP a Binary Linear Optimization Problem.
Certainty
The coefficients and independent terms of the objective function and the model’s constraints are deterministic, that is, if it is modeled that z(x,y)=2x+3yz(x,y)=2x+3y, it would be assumed that the coefficients 2 and 3 of xx and yy, respectively, would be known and certain, that is, it would be certain that the contribution of xx to zz would always be 2 times the amount of xx, while the contribution of yy to zz would always be 3 times the amount of yy, no matter what the values of xx and yy are. In the BLOP model for the Queens game, all coefficients and independent terms will be equal to 1 (except for the arbitrary constant CC, which can take any value, as will be seen later).

How to Play Queens

Figure 1:Example of a Queens minigame board. Source: LinkedIn

Objective
To place a crown in each row, column, and colored region on the board.
Rules
There can only be one crown in each row, column and colored region.
There cannot be adjacent crowns, not even along adjacent diagonals.

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,⋯ ,n}I = \{1, \cdots, n\}
Range of rows, where nn is the total number of rows on the board (in this case, nn = 7)
J={1,⋯ ,m}J = \{1, \cdots, m\}
Range of columns, where nn is the total number of columns on the board (also nn = 7 for this case)
K={1,⋯ ,p}K = \{1, \cdots, p\}
Range of colored regions in game, where pp is the total number of regions on the board (pp = 7)

Sets

By defining the ranges II and JJ, let’s define three sets for solving the Queens game:

H=I×J={(i,j)∣∀i∈I,∀j∈J}H = I \times J = \{(i,j) \mid \forall i \in I, \forall j \in J\}
Set of all squares (i,j)(i, j) on the board, which is nothing more than the Cartesian product of the ranges II and JJ
R={((i,j),k)∣(i,j)∈H,k∈K}R = \{((i,j),k) \mid (i,j) \in H, k \in K\}
Set of colored regions and says to which region kk a square (i,j)(i,j) belongs. Each region kk will be a subset of RR, composed of the set of ordered pairs (i,j)(i,j) that belong to color kk. Furthermore, the set RkR_k must be a partition of the set of squares HH, that is, the union of all its subsets RkR_k are jointly exhaustive and mutually exclusive, since each square belongs to one color and there is no square that belongs to two different colors.
D={((i,j),(i+1,j+1))∣(i,j),(i+1,j+1)∈H}∪{((i,j),(i+1,j−1))∣(i,j),(i+1,j−1)∈H}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, whose solution we want to find to solve the LOP, will be binary variables xijx_{ij}, which assume only two values:

xij∈{0,1},∀(i,j)∈Hx_{ij} \in \{0,1\}, \forall (i,j) \in H
xij=1x_{ij} = 1, if the crown is located in row ii and column jj;
xij=0x_{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 maximizing (or minimizing, 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.

Max C\text{Max} \ C
(1)

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.
xij∈{0,1},∀i∈I,∀j∈Jx_{ij} \in \{0,1\}, \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 xijx_{ij} belonging to a row ii must equal 1. As there are 7 rows in total, there will be 7 such constraints, one for each row.
∑j∈Jxij=1,∀i∈I\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.
∑i∈Ixij=1,∀j∈J\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 xijx_{ij} belonging to a region kk must be equal to 1. Since there are 7 regions, there will be 7 more constraints.
∑(i,j)∈Rkxij=1,∀k∈K\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 DD well defined, this constraint is easily defined as it follows.
xij+xrs≤1,∀((i,j),(r,s))∈Dx_{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.

Max CS.t.:∑j=1mxij=1,∀i∈I∑i=1nxij=1,∀j∈J∑(i,j)∈Rkxij=1,∀k∈Kxij+xrs≤1,∀((i,j),(r,s))∈Dxij∈{0,1},∀(i,j)∈H\begin{array}{lll} & \text{Max } C \\ \text{S.t.:} & \\ & \sum_{j=1}^{m}{x_{ij}} = 1, & \forall i \in I \\ & \sum_{i=1}^{n}{x_{ij}} = 1, & \forall j \in J \\ & \sum_{(i,j) \in R_k}{x_{ij}} = 1, & \forall k \in K \\ & x_{ij} + x_{rs} \le 1, & \forall ((i,j),(r,s)) \in D \\ & x_{ij} \in \{0,1\}, & \forall (i,j) \in H \end{array}
(7)

Concrete Model

For the Queens game, which will be discussed in this article, we will have the following instance of the abstract model presented earlier, that is, its concrete model.

Max 0\text{Max} \ 0

S.t.:

Single-Crown-Per-Row Constraints
x11+x12+x13+x14+x15+x16+x17=1x_{11} + x_{12} + x_{13} + x_{14} + x_{15} + x_{16} + x_{17} = 1 (Row 1)
x21+x22+x23+x24+x25+x26+x27=1x_{21} + x_{22} + x_{23} + x_{24} + x_{25} + x_{26} + x_{27} = 1 (Row 2)
x31+x32+x33+x34+x35+x36+x37=1x_{31} + x_{32} + x_{33} + x_{34} + x_{35} + x_{36} + x_{37} = 1 (Row 3)
x41+x42+x43+x44+x45+x46+x47=1x_{41} + x_{42} + x_{43} + x_{44} + x_{45} + x_{46} + x_{47} = 1 (Row 4)
x51+x52+x53+x54+x55+x56+x57=1x_{51} + x_{52} + x_{53} + x_{54} + x_{55} + x_{56} + x_{57} = 1 (Row 5)
x61+x62+x63+x64+x65+x66+x67=1x_{61} + x_{62} + x_{63} + x_{64} + x_{65} + x_{66} + x_{67} = 1 (Row 6)
x71+x72+x73+x74+x75+x76+x77=1x_{71} + x_{72} + x_{73} + x_{74} + x_{75} + x_{76} + x_{77} = 1 (Row 7)
Single-Crown-Per-Column Constraints
x11+x21+x31+x41+x51+x61+x71=1x_{11} + x_{21} + x_{31} + x_{41} + x_{51} + x_{61} + x_{71} = 1 (Column 1)
x12+x22+x32+x42+x52+x62+x72=1x_{12} + x_{22} + x_{32} + x_{42} + x_{52} + x_{62} + x_{72} = 1 (Column 2)
x13+x23+x33+x43+x53+x63+x73=1x_{13} + x_{23} + x_{33} + x_{43} + x_{53} + x_{63} + x_{73} = 1 (Column 3)
x14+x24+x34+x44+x54+x64+x74=1x_{14} + x_{24} + x_{34} + x_{44} + x_{54} + x_{64} + x_{74} = 1 (Column 4)
x15+x25+x35+x45+x55+x65+x75=1x_{15} + x_{25} + x_{35} + x_{45} + x_{55} + x_{65} + x_{75} = 1 (Column 5)
x16+x26+x36+x46+x56+x66+x76=1x_{16} + x_{26} + x_{36} + x_{46} + x_{56} + x_{66} + x_{76} = 1 (Column 6)
x17+x27+x37+x47+x57+x67+x77=1x_{17} + x_{27} + x_{37} + x_{47} + x_{57} + x_{67} + x_{77} = 1 (Column 7)
Single-Crown-Per-Region Constraints
x11+x12+x13+x14+x15+x16+x17+x26+x27+x36+x37+x46+x47+x57+x67+x77=1x_{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)
x12+x22+x32+x42+x33+x41+x42+x51+x52+x16+x26+x46+x56+x66+x71+x72+x73+x74+x75+x76=1x_{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)
x25+x35=1x_{25} + x_{35} = 1 (Blue Region)
x32+x33=1x_{32} + x_{33} = 1 (Green Region)
x34+x43+x44+x45+x54=1x_{34} + x_{43} + x_{44} + x_{45} + x_{54} = 1 (Gray Region)
x53+x63=1x_{53} + x_{63} = 1 (Red Region)
x55+x56=1x_{55} + x_{56} = 1 (Yellow Region)
Principal Diagonals Constraints
x11+x22≤1x_{11} + x_{22} \le 1
x12+x23≤1x_{12} + x_{23} \le 1
x13+x24≤1x_{13} + x_{24} \le 1
x14+x25≤1x_{14} + x_{25} \le 1
x15+x26≤1x_{15} + x_{26} \le 1
x21+x32≤1x_{21} + x_{32} \le 1
x22+x33≤1x_{22} + x_{33} \le 1
x23+x34≤1x_{23} + x_{34} \le 1
x24+x35≤1x_{24} + x_{35} \le 1
x25+x36≤1x_{25} + x_{36} \le 1
x31+x42≤1x_{31} + x_{42} \le 1
x32+x43≤1x_{32} + x_{43} \le 1
x33+x44≤1x_{33} + x_{44} \le 1
x34+x45≤1x_{34} + x_{45} \le 1
x35+x46≤1x_{35} + x_{46} \le 1
x41+x52≤1x_{41} + x_{52} \le 1
x42+x53≤1x_{42} + x_{53} \le 1
x43+x54≤1x_{43} + x_{54} \le 1
x44+x55≤1x_{44} + x_{55} \le 1
x45+x56≤1x_{45} + x_{56} \le 1
x51+x62≤1x_{51} + x_{62} \le 1
x52+x63≤1x_{52} + x_{63} \le 1
x53+x64≤1x_{53} + x_{64} \le 1
x54+x65≤1x_{54} + x_{65} \le 1
x55+x66≤1x_{55} + x_{66} \le 1
Secondary Diagonals Constraints
x12+x21≤1x_{12} + x_{21} \le 1
x13+x22≤1x_{13} + x_{22} \le 1
x14+x23≤1x_{14} + x_{23} \le 1
x15+x24≤1x_{15} + x_{24} \le 1
x16+x25≤1x_{16} + x_{25} \le 1
x22+x31≤1x_{22} + x_{31} \le 1
x23+x32≤1x_{23} + x_{32} \le 1
x24+x33≤1x_{24} + x_{33} \le 1
x25+x34≤1x_{25} + x_{34} \le 1
x26+x35≤1x_{26} + x_{35} \le 1
x32+x41≤1x_{32} + x_{41} \le 1
x33+x42≤1x_{33} + x_{42} \le 1
x34+x43≤1x_{34} + x_{43} \le 1
x35+x44≤1x_{35} + x_{44} \le 1
x36+x45≤1x_{36} + x_{45} \le 1
x42+x51≤1x_{42} + x_{51} \le 1
x43+x52≤1x_{43} + x_{52} \le 1
x44+x53≤1x_{44} + x_{53} \le 1
x45+x54≤1x_{45} + x_{54} \le 1
x46+x55≤1x_{46} + x_{55} \le 1
x52+x61≤1x_{52} + x_{61} \le 1
x53+x62≤1x_{53} + x_{62} \le 1
x54+x63≤1x_{54} + x_{63} \le 1
x55+x64≤1x_{55} + x_{64} \le 1
x56+x65≤1x_{56} + x_{65} \le 1
Binarity Constraints
x12∈{0,1}x_{12} \in \{0,1\}
x13∈{0,1}x_{13} \in \{0,1\}
x14∈{0,1}x_{14} \in \{0,1\}
x15∈{0,1}x_{15} \in \{0,1\}
x16∈{0,1}x_{16} \in \{0,1\}
x17∈{0,1}x_{17} \in \{0,1\}
x21∈{0,1}x_{21} \in \{0,1\}
x22∈{0,1}x_{22} \in \{0,1\}
x23∈{0,1}x_{23} \in \{0,1\}
x24∈{0,1}x_{24} \in \{0,1\}
x25∈{0,1}x_{25} \in \{0,1\}
x26∈{0,1}x_{26} \in \{0,1\}
x27∈{0,1}x_{27} \in \{0,1\}
x31∈{0,1}x_{31} \in \{0,1\}
x32∈{0,1}x_{32} \in \{0,1\}
x33∈{0,1}x_{33} \in \{0,1\}
x34∈{0,1}x_{34} \in \{0,1\}
x35∈{0,1}x_{35} \in \{0,1\}
x36∈{0,1}x_{36} \in \{0,1\}
x37∈{0,1}x_{37} \in \{0,1\}
x41∈{0,1}x_{41} \in \{0,1\}
x42∈{0,1}x_{42} \in \{0,1\}
x43∈{0,1}x_{43} \in \{0,1\}
x44∈{0,1}x_{44} \in \{0,1\}
x45∈{0,1}x_{45} \in \{0,1\}
x46∈{0,1}x_{46} \in \{0,1\}
x47∈{0,1}x_{47} \in \{0,1\}
x51∈{0,1}x_{51} \in \{0,1\}
x52∈{0,1}x_{52} \in \{0,1\}
x53∈{0,1}x_{53} \in \{0,1\}
x54∈{0,1}x_{54} \in \{0,1\}
x55∈{0,1}x_{55} \in \{0,1\}
x56∈{0,1}x_{56} \in \{0,1\}
x57∈{0,1}x_{57} \in \{0,1\}
x61∈{0,1}x_{61} \in \{0,1\}
x62∈{0,1}x_{62} \in \{0,1\}
x63∈{0,1}x_{63} \in \{0,1\}
x64∈{0,1}x_{64} \in \{0,1\}
x65∈{0,1}x_{65} \in \{0,1\}
x66∈{0,1}x_{66} \in \{0,1\}
x67∈{0,1}x_{67} \in \{0,1\}
x71∈{0,1}x_{71} \in \{0,1\}
x72∈{0,1}x_{72} \in \{0,1\}
x73∈{0,1}x_{73} \in \{0,1\}
x74∈{0,1}x_{74} \in \{0,1\}
x75∈{0,1}x_{75} \in \{0,1\}
x76∈{0,1}x_{76} \in \{0,1\}
x77∈{0,1}x_{77} \in \{0,1\}

Solving with Pyomo and NetworkX

Along this book, it’ll be used the following Python libraries that will enable us to solve the games:

Pyomo
Open-source library for modeling optimization problems. Its main advantage is the ability to model problems using set logic, which allows defining a set of variables, parameters, and constraints from the definition of other sets of objects. For example, once one defines the set of ranges II, JJ, and KK, it’s possible to define, e.g., the set of squares, regions and diagonals with just one line of code each instead of defining them one by one, saving considerable time!
NetworkX
Geared towards manipulating and studying network structures. With it, it’s possible to create graphs and solve problems modeled in network logic quickly and easily, such as the Shortest Path problem, Minimum Spanning Tree, Transportation and Transshipment problem, and other graph problems. Furthermore, it’s possible to quickly draw graphs when combined with Matplotlib.

After installing the solver, let’s import the used libraries.

import matplotlib.pyplot as plt # For displaying the solved game.
import networkx as nx
import pyomo.environ as pyo

Solving Queens

As an example of applying the presented model, the Queens No. 307 problem, published on the platform on March 3rd, 2025, was used.

Queens No. 307, March 3rd, 2025. Source: LinkedIn

Figure 2:Queens No. 307, March 3rd, 2025. Source: LinkedIn

In order to model and solve the game, it was defined the solve_queen() function in the code below.

def solve_queens(n:int, m:int, regions:dict) -> None:

    # Instantiating the model
    model = pyo.ConcreteModel()

    # Ranges
    I = model.I = pyo.RangeSet(n)
    J = model.J = pyo.RangeSet(m)
    K = model.Colors = pyo.Set(initialize=regions.keys())

    # Sets
    H = model.Squares = pyo.Set(initialize=lambda model: [(i,j) for i in I for j in J])
    R = model.Regions = pyo.Set(K, initialize=regions, dimen=2)
    D = model.Diagonals = pyo.Set(initialize=lambda model: [
        ((i, j), (i+1, j+1)) for (i,j) in H if (i+1,j+1) in H] + [
        ((i, j), (i+1, j-1)) for (i,j) in H if (i+1,j-1) in H
    ])

    # Objective function
    model.obj = pyo.Objective(expr=0, sense=pyo.maximize)

    # Decision Variables
    x = model.x = pyo.Var(H, within=pyo.Binary, initialize=0)

    # Constraints
    model.single_crown_per_row_constraints = pyo.Constraint(
        I,
        rule=lambda model, i: sum(x[i,j] for j in J) == 1
    )

    model.single_crown_per_column_constraints = pyo.Constraint(
        J,
        rule=lambda model, j: sum(x[i,j] for i in I) == 1
    )

    model.single_crown_per_region_constraints = pyo.Constraint(
        K,
        rule=lambda model, k: sum(x[i,j] for (i,j) in R[k]) == 1
    )

    model.adjacent_squares_by_vertex_constraints = pyo.Constraint(
        D,
        rule=lambda model, i, j, r, s: x[i,j] + x[r,s] <= 1
    )

    # Optmization result
    solver = pyo.SolverFactory("gurobi")
    results = solver.solve(model)
    solution = [(i, j) for i in I for j in J if model.x[i,j].value == 1]

    if str(results.Solver.status) == "ok":
        G = nx.grid_2d_graph(n,m)
        plt.figure(figsize=(3.4, 3.4))
        
        squares = sorted(list(H))
        squares = [(i-1, j-1) for (i,j) in squares]

        color_map = [{(i-1, j-1): region for (i,j) in squares} for region, squares in regions.items()]
        color_map = {square: region for d in color_map for square, region in d.items()}
        color_map = [color_map[square] for square in squares]
        
        hex_map = {
            "purple": "#BBA3E1",
            "orange": "#FFC794",
            "blue": "#94BEFF",
            "green": "#B3DF9E",
            "gray": "#E0E0E0",
            "red": "#FF7B61",
            "yellow": "#E6F388"
        }

        color_map = [hex_map[color] for color in color_map]

        nx.draw(
            G,
            pos= {(i,j): (j, -i) for i, j in G.nodes()},
            with_labels= True,
            labels= {(i-1, j-1): "O" for (i,j) in solution},
            node_size= 1000,
            node_color= color_map,
            node_shape="s",
            width=0
        )
        plt.show()
        
    else:
        print("No valid solution was found!")

With the function created, it’s only needed to pass the necessary inputs to solve the Queens game.

regions = {
    "purple": [(1,1), (1,2), (1,3), (1,4), (1,5), (1,6), (1,7), (2,6), (2,7), (3,6), (3,7), (4,6), (4,7), (5,7), (6,7), (7,7)],
    "orange": [(2,1), (2,2), (2,3), (2,4), (3,1), (4,1), (4,2), (5,1), (5,2), (6,1), (6,2), (6,4), (6,5), (6,6), (7,1), (7,2), (7,3), (7,4), (7,5), (7,6)],
    "blue": [(2,5), (3,5)],
    "green": [(3,2), (3,3)],
    "gray": [(3,4), (4,3), (4,4), (4,5), (5,4)],
    "red": [(5,3), (6,3)],
    "yellow": [(5,5), (5,6)]
}

solve_queens(7,7,regions)
<Figure size 340x340 with 1 Axes>

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

Solution of Queens No. 307

Figure 3:Solution of Queens No. 307, March 3rd, 2025. Source: LinkedIn

References

Solving LinkedIn Games by Linear Optimization
Solving LinkedIn Games by Linear Optimization
How to Solve
Tango