Using Linear Equations + LLM to Solve LinkedIn Queens Game

Queens (generated using Canva)

Prompting GPT to form and solve the linear equations using PuLP

In my How I Solved LinkedIn Queens Game article, I’ve discussed solving the LinkedIn Queens game using backtracking, a hit-and-trail method. It places a Queen on one of the cells of the grid and continues to do so, respecting all the constraints until it can’t anymore. At this point, it rolls back the last placedQueen and keeps repeating this process until it finds a solution or exhausts all the cells on the grid. Since LinkedIn guarantees there will always be a solution, our backtracking method is perfect and will always be successful. However, its time complexity is of O(n²) but is still solved in less than 0.1 seconds because the max grids (as far as I have played) are only 10×10.

How I Solved LinkedIn Queens Game Using Backtracking

Even though backtracking is performing well in terms of time complexity and implementation, let’s take it a step further and try to solve it even better. Did you know all the constraints of the game can be translated into a set of linear equations? When we solve those equations, we should find the perfect solution in no time. It’s just simple math!

How to play

For those of you who haven’t played or are unfamiliar with LinkedIn’s Queens game:

Goal: Place exactly one Q in each row, column, and color region.

Rule: Two Qs cannot touch each other — horizontally, vertically or diagonally

So, what are Linear Equations?

A set (or a system) or Linear Equations is a collection of two or more linear equations that involve the same set of variables. The linear part comes from the fact that the variables are always raised to the power one and nothing more. Geometrically speaking, a set of equations with two variables are straight lines that may or may not intersect. The ones that intersect with each other will have a solution representing a value for each variable, which is the point of intersection of the lines. Consider the below equations:

sample equations

These are a system of linear equations,
a. with variables (x and y)
b. with coefficients (2, 3) and (1, -4)
c. with constants terms (1 and -3)

The solution of these two equations would be the value of x and y that satisfy both equations. These can be solved in various ways, and the easiest one with intuition here is to subtract 2nd equation from first.

solving sample equations

But this is just one way of solving it. There are many practical methods to solve a system of linear equations, each with its unique advantages. The most common methods are:
Graphical — to plot each equation on a graph and find the intersection point.
Elimination — the method we employed to solve the above equations eliminates variables using other equations, which would yield one value, then repeat the process to find other variable values.
Gaussian Elimination — extract the coefficient and ordinate matrix and use Gaussian elimination or matrix inversion
Linear Programming — optimize for the sum of all the variables based on the given constraints. We will use this method because you will see later that our system will also have linear inequalities.

We will first develop the intuition on how to get the set of linear equations to solve the puzzle, then use popular Python packages to translate and solve those equations. Finally, we will ask GPT-4o to formulate and solve the equations instead of us manually forming the equations.

How to form the Linear Equations?

Consider the following 5×5 grid with one variable assigned to each cell from x₁₁ to x₅₅

named grid

Following the rules of the game:

Each row should have precisely one Queen — Which means the sum of all the variables of each row should be equal to 1

row equations

Each column should have precisely one Queen — which means the sum of all the variables of each column should also be equal to 1

column equations

Then comes the color equations — Each color should have precisely one Queen — so the sum of all the variables of each color should be equal to 1. If you consider the pink color in our example, x₁₁ should be one since there is no other cell with that color. Similarly, the sum of x₂₂ and x₃₂ should be one since only two cells exist of the color green. Forming all the equations based on the color looks like:

color equations

And finally, the most important constraint is the adjacency constraint. No two Queens should be adjacent row-wise, column-wise, or across. This gives us a bunch of inequalities. Let’s take the first cell x₁₁ and see what all adjacency constraints are applied over it:
Row wise: x₁₁ + x₁₂ ≤ 1
Column wise: x₁₁ + x₂₁ ≤ 1
Across (right — to — left): x₂₁ + x₁₂ ≤ 1
Across (left — to — right): x₁₁ + x₂₂ ≤ 1

We have to make similar equations for every adjacent cell pairs on the entire grid. Since these will become too many, we shall skip writing them here and directly implement them in our code in the following steps. Solving the set of all the above equations should give us which cells should have 1 and which ones should have a 0, where 1 represents a Queen and 0 represents an X.

Extracting grid from image

Since we don’t want to convert the image to a 2D array, we will use a similar approach we’ve used in the other article; we will programmatically extract the grid using OpenCV.

For more details you can go through the grid_detection.py file on GitHub

In short, the piece of code takes an image/screenshot that contains LinkedIn’s Queens game and converts it into a 2D array, solves it using backtracking, and recreates the board again with properly placed Qs and XsWe will replace the solve_n_queens method with solve_n_queens_with_math and keep the grid detection and re-generation the same and check for performance again at the end.

Puzzle screen shot as input and detection and solving using backtracking in 0.06 seconds

Solving Linear Equations with Python

I started off trying to solve it with SymPy. It didn’t work because we have inequalities along with equalities in our constraints (I have left all my failed attempts in the iPython notebooks in the GitHub repo). After searching for libraries, I settled on PuLP, which was built to solve Linear Programming problems. First, we create an LP problem using PuLP to minimize the sum of all variables.

import pulp

# Create a new LP problem
prob = pulp.LpProblem(“linkedin-queens-solver-math”, pulp.LpMinimize)
grid_size = 5

# Create the grid_sizeXgrid_size of binary variables
matrix = [[pulp.LpVariable(f’matrix_{i}_{j}’, 0, 1, cat=’Binary’) for j in range(grid_size)] for i in range(grid_size)]

# Objective function (since we’re not optimizing anything specific, we can set a dummy objective)
# Let’s minimize the sum of all variables
prob += pulp.lpSum(matrix[i][j] for i in range(grid_size) for j in range(grid_size))

Creating row, column constraint equations:

# Each row sum = 1 constraints
for i in range(grid_size):
prob += pulp.lpSum(matrix[i][j] for j in range(grid_size)) == 1

# Column sum = 1 constraints
for j in range(grid_size):
prob += pulp.lpSum(matrix[i][j] for i in range(grid_size)) == 1

Creating color constraints:

group_positions = defaultdict(list)
# Populate the dictionary with the positions of each group
for i in range(len(copy_board)):
for j in range(len(copy_board[i])):
group_positions[copy_board[i][j]].append((i, j))

for _, positions in group_positions.items():
prob += pulp.lpSum(matrix[i][j] for i,j in positions) == 1

Now, we move on to the most critical constraints: pairwise adjacent cell sums should be at max one.

# Adding row-wise adjacent constraints (sum of horizontally adjacent cells <= 1)
for i in range(grid_size):
for j in range(grid_size – 1): # Horizontally adjacent cells in the same row
prob += matrix[i][j] + matrix[i][j + 1] <= 1

# Adding column-wise adjacent constraints (sum of vertically adjacent cells <= 1)
for j in range(grid_size):
for i in range(grid_size – 1): # Vertically adjacent cells in the same column
prob += matrix[i][j] + matrix[i + 1][j] <= 1

# Adding diagonal adjacent constraints (sum of diagonally adjacent cells <= 1)
# Top-left to bottom-right diagonal constraint
for i in range(grid_size – 1):
for j in range(grid_size – 1):
prob += matrix[i][j] + matrix[i + 1][j + 1] <= 1

# Top-right to bottom-left diagonal constraint
for i in range(grid_size – 1):
for j in range(1, grid_size):
prob += matrix[i][j] + matrix[i + 1][j – 1] <= 1

That concludes all our equations!! In total, we can see how many constraints have been added to our problem using len(prob.constraints)

Now, let’s solve it. It’s as simple as calling solve() on our problem! Although LinkedIn guarantees there will always be a solution, let’s add conditions to check if it has found the minima of our problem.

# Solve the problem
prob.solve()

# Check if the problem has a feasible solution
if pulp.LpStatus[prob.status] == ‘Optimal’:
solution = [[pulp.value(matrix[i][j]) for j in range(grid_size)] for i in range(grid_size)]
print(“Solution found:”)
for row in solution:
print(row)
else:
print(“No solution found. The problem may be infeasible.”)

Running the code for our 5×5 grid gives the output.

input puzzle and output of PuLP

Using AI

Though the initial idea was to make the AI solve the puzzle independently and give us insights on how exactly it took steps to solve it, GPT-4o has failed miserably. I couldn’t even get it to correctly answer how many Qs are there on the current board. I kept writing custom tools to provide these and finally decided GPT-4o was unsuitable for tasks of this kind. All the failures still served as valuable lessons in prompt engineering and structured inputs and outputs for tools. These are for another article; in this article, let’s give the linear programming idea to GPT-4o and ask it to generate the equations and solve them using Python REPL tool. For this, will use LangChain’s ReAct Agent implementation.

Lets install the necessary packages:

pip install langchain, langchain-openai, langchain-experimental, python-dotenv

Import necessary packages and initialize an LLM. I am using the AzureChatOpenAI model. This model can be replaced with any other one, and the code would work fine. Thanks to LangChain.

from langchain_openai import AzureChatOpenAI
from langchain.prompts import ChatPromptTemplate, PromptTemplate
from langchain_core.messages import SystemMessage
from dotenv import find_dotenv, load_dotenv
from langchain_core.tools import tool
from langchain_experimental.utilities import PythonREPL
from langchain_experimental.tools import PythonREPLTool
from langchain.agents import AgentExecutor, create_react_agent, create_tool_calling_agent

# load .env file
load_dotenv(find_dotenv())

llm = AzureChatOpenAI(model=”gpt-4o”,
temperature = 1,
api_version=”2023-03-15-preview”,
verbose=True)

After some tinkering with the prompt, I have settled on the one that produces the exact output of a 2D array after solving the equations. This is still an assumption; we can never predict what LLM will give as output; in production, we should be using an OutputParser to get the required output.

template = “””
You are puzzle solver. Given a {grid_size}x{grid_size} grid, use PuLP to solve the puzzle.
You should solve the puzzle for the constraints:
1. Each row sum should be 1
2. Each column sum should be 1
3. Each number region sum should be 1
4. Parwise sum of all adjacent cells, row wise, column wise and diagonally should be <= 1

Form these constraints using PuLP and solve them for Binary category since all variables can be either 0 or 1.
Dont give any explanation, execute the code and give me the final answer as 2d array.
Grid:
{grid}
“””

Next, we will create a custom function tool or use the PythonREPLTool out of the box provided by LangChain to execute our code and return the output.

@tool
def execute_python_tool(code):
“””
A Python shell. Use this to execute python commands. Input should be a valid python command. If you want to see the output of a value, you should print it out with `print(…)`.
“””
python_repl = PythonREPLTool()
return python_repl.invoke(code)

Finally, we create the agent and pass it to the input grid, which we got from processing the image using OpenCV. Here, I am hardcoding the values to test the LLM part; we shall hook this to our OpenCV step once we are confident in prompt and output parsing.

# Hardcoded puzzle grid for testing
message = prompt_template.invoke({“grid_size”: 7, “grid”:
“””[
[‘1’, ‘1’, ‘1’, ‘2’, ‘2’, ‘2’, ‘3’, ‘3’],
[‘1’, ‘4’, ‘1’, ‘4’, ‘2’, ‘3’, ‘3’, ‘3’],
[‘1’, ‘4’, ‘4’, ‘4’, ‘2’, ‘5’, ‘5’, ‘5’],
[‘1’, ‘4’, ‘4’, ‘4’, ‘2’, ‘6’, ‘6’, ‘6’],
[‘1’, ‘1’, ‘4’, ‘2’, ‘2’, ‘6’, ‘4’, ‘6’],
[‘1’, ‘1’, ‘4’, ‘4’, ‘4’, ‘4’, ‘4’, ‘6’],
[‘1’, ‘7’, ‘4’, ‘4’, ‘4’, ‘4’, ‘4’, ‘6’],
[‘7’, ‘7’, ‘4’, ‘8’, ‘8’, ‘8’, ‘4’, ‘6’]
]”””})

agent = create_react_agent(llm, tools, prompt)
agent_executor = AgentExecutor(agent=agent, tools=tools, verbose=True)

# invoking the agent to solve the puzzle
agent_executor.invoke({“input”: message})

Since we get the output of an LLM as a string, we have to write a tiny parser that takes a string of 2D arrays and converts it into a 2D array of strings; we return this to our OpenCV to form the final answer.

array_string = result[“output”].strip(“`”)

# Convert the string to a Python list
array_list = eval(array_string)

# Replace 1s with ‘Q’ and convert to numpy array
converted_array = np.array([[‘Q’ if cell == 1 else 0 for cell in row] for row in array_list])output from ReAct agent

Conclusion

In this article, we started by solving LinkedIn’s Queens game using linear programming, forming the equations using code, and solving them using the PuLP package. Later, we used GPT-4o to auto-generate and solve the system of linear equations, which gave us the final answer. Though this is not the desired outcome of an intelligence that can think for itself, we saw that with little prompting and parsing, LLMs can take the heavy lifting of generating code and executing it just like we did in the first half of the article.

🚀 Explore the code on GitHub and show your support with a ⭐ if you find it helpful! 🙌✨All images are by the author unless stated otherwise

Using Linear Equations + LLM to Solve LinkedIn Queens Game was originally published in Towards Data Science on Medium, where people are continuing the conversation by highlighting and responding to this story.

Author:

Leave a Comment

You must be logged in to post a comment.