Using Linear Equations + LLM to Solve LinkedIn Queens Game
Queens (generated using Canva)Prompting GPT to form and solve the linear equations using PuLPIn 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 10x10.How I Solved LinkedIn Queens Game Using BacktrackingEven 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 playFor 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 diagonallySo, 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 equationsThese 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 equationsBut 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 inversionLinear 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 5x5 grid with one variable assigned to each cell from x₁₁ to x₅₅named gridFollowing 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 1row equationsEach column should have precisely one Queen — which means the sum of all the variables of each column should also be equal to 1column equationsThen 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 equationsAnd 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₁₂ ≤ 1Column wise: x₁₁ + x₂₁ ≤ 1Across (right — to — left): x₂₁ + x₁₂ ≤ 1Across (left — to — right): x₁₁ + x₂₂ ≤ 1We 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 imageSince 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 GitHubIn 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 secondsSolving Linear Equations with PythonI 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 problemprob = pulp.LpProblem("linkedin-queens-solver-math", pulp.LpMinimize)grid_size = 5# Create the grid_sizeXgrid_size of binary variablesmatrix = [[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 variablesprob += 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 constraintsfor i in range(grid_size): prob += pulp.lpSum(matrix[i][j] for j in range(grid_size)) == 1# Column sum = 1 constraintsfor j in range(grid_size): prob += pulp.lpSum(matrix[i][j] for i in range(grid_size)) == 1Creating color constraints:group_positions = defaultdict(list)# Populate the dictionary with the positions of each groupfor 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) == 1Now, 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 constraintfor 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 constraintfor i in range(grid_size - 1): for j in range(1, grid_size): prob += matrix[i][j] + matrix[i + 1][j - 1] <= 1That 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 problemprob.solve()# Check if the problem has a feasible solutionif 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 5x5 grid gives the output.input puzzle and output of PuLPUsing AIThough 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-dotenvImport 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 AzureChatOpenAIfrom langchain.prompts import ChatPromptTemplate, PromptTemplatefrom langchain_core.messages import SystemMessagefrom dotenv import find_dotenv, load_dotenvfrom langchain_core.tools import toolfrom langchain_experimental.utilities import PythonREPLfrom langchain_experimental.tools import PythonREPLToolfrom langchain.agents import AgentExecutor, create_react_agent, create_tool_calling_agent# load .env fileload_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 12. Each column sum should be 13. Each number region sum should be 14. Parwise sum of all adjacent cells, row wise, column wise and diagonally should be <= 1Form 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.@tooldef 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 testingmessage = 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 puzzleagent_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 listarray_list = eval(array_string)# Replace 1s with 'Q' and convert to numpy arrayconverted_array = np.array([['Q' if cell == 1 else 0 for cell in row] for row in array_list])output from ReAct agentConclusionIn 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 otherwiseUsing 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.
Welcome to Billionaire Club Co LLC, your gateway to a brand-new social media experience! Sign up today and dive into over 10,000 fresh daily articles and videos curated just for your enjoyment. Enjoy the ad free experience, unlimited content interactions, and get that coveted blue check verification—all for just $1 a month!
Account Frozen
Your account is frozen. You can still view content but cannot interact with it.
Please go to your settings to update your account status.
Open Profile Settings