Queens game using CP

This is an exciting installment of our newsletter!

I recently came across a fascinating challenge on LinkedIn that caught my attention. It's a perfect example of the kind of problem that can be tackled using constraint programming. Let’s explore how we can solve it with this powerful approach.

Why is this important?

Constraint programming is more than just a tool—it's a game-changer in solving complex problems efficiently. Whether you're managing supply chains, scheduling tasks, or optimizing resources, constraint programming provides a structured way to handle multiple constraints and find the best possible solution. By applying it to this LinkedIn game, we not only sharpen our problem-solving skills but also gain valuable insights into how constraint programming can be used in real-world scenarios, where the stakes are high and efficiency is key.

Game rules:

• Only one queen should be placed at each region
• At most one queen can be placed on each row and column.
• No two queens can touch each other (they can be on the same diagonal if they don't touch)

Data generation

The data associated with board should be created:

data = {
    (0, 0): 0, (0, 1): 0, (0, 2): 0, (0, 3): 0, (0, 4): 0, (0, 5): 0, (0, 6): 0, (0, 7): 0, (0, 8): 0,
    (1, 0): 0, (1, 1): 0, (1, 2): 5, (1, 3): 5, (1, 4): 5, (1, 5): 5, (1, 6): 5, (1, 7): 5, (1, 8): 0,
    (2, 0): 0, (2, 1): 0, (2, 2): 2, (2, 3): 2, (2, 4): 2, (2, 5): 2, (2, 6): 2, (2, 7): 5, (2, 8): 0,
    (3, 0): 0, (3, 1): 0, (3, 2): 2, (3, 3): 2, (3, 4): 4, (3, 5): 4, (3, 6): 2, (3, 7): 1, (3, 8): 0,
    (4, 0): 0, (4, 1): 0, (4, 2): 2, (4, 3): 3, (4, 4): 3, (4, 5): 4, (4, 6): 2, (4, 7): 1, (4, 8): 0,
    (5, 0): 0, (5, 1): 6, (5, 2): 6, (5, 3): 6, (5, 4): 3, (5, 5): 2, (5, 6): 2, (5, 7): 1, (5, 8): 0,
    (6, 0): 8, (6, 1): 7, (6, 2): 7, (6, 3): 6, (6, 4): 2, (6, 5): 2, (6, 6): 2, (6, 7): 1, (6, 8): 0,
    (7, 0): 8, (7, 1): 8, (7, 2): 7, (7, 3): 6, (7, 4): 0, (7, 5): 0, (7, 6): 0, (7, 7): 0, (7, 8): 0,
    (8, 0): 8, (8, 1): 8, (8, 2): 8, (8, 3): 0, (8, 4): 0, (8, 5): 0, (8, 6): 0, (8, 7): 0, (8, 8): 0
}        

Now we know the color and the coordinates of each cell.

The question we need to answer is a To be Or Not To be for each cell --> Binary variable (0/1)

So let's skip to the good part,

Python Code

Model

Let's create a model

model = cp_model.CpModel()
solver = cp_model.CpSolver()        

Sets

Now we need a couple of sets

nodes = range(1,N+1)
colors = info_color.keys()        

nodes: all cells

colors: all distinct colors

Decision variables

Now a number of binary variables are required to find the location of Queens

U = {c:model.NewBoolVar(f"queen_{c}") for c in nodes}        

Constraints

For each colored region we should have only one Queen (use AddExactlyOne)

how to detect ? The

for c in colors:
  expressions = [U[n] for n in nodes if info[n][2] == c]
  model.AddExactlyOne(expressions)
  """
  each color has exactly one queen
  """        

For each row we should have only one Queen (use AddExactlyOne)

for x in range(1,10):
  expressions = [U[n] for n in nodes if info[n][0] == x]
  model.AddAtMostOne(expressions)
  """
  each row has at most one queen
  """        

For each column we should have only one Queen (use AddExactlyOne)

for y in range(1,10):
  expressions = [U[n] for n in nodes if info[n][1] == y]
  model.AddAtMostOne(expressions)
  """
  each column has at most one queen
  """        

No two adjacent cells should have both queens

for n in nodes:
  expressions = [U[n]]+[U[c] for c in nodes if n!=c and (info[n][0] - info[c][0])**2 +(info[n][1] - info[c][1])**2<2]
  model.AddAtMostOne(expressions)
  """
  any two adjacent nodes can not both host queen
  """        

Done !

Final result

Code is available on Git Repo

https://github.com/OptimizationExpert/Pyomo

Importance:

1. Real-World Relevance: The LinkedIn game might be a fun intellectual exercise, but it mirrors the challenges faced in industries like logistics, manufacturing, and operations. Understanding how to apply constraint programming in such a context helps professionals navigate and optimize real-world scenarios.
2. Efficiency and Optimization: Constraint programming is crucial in situations where resources are limited, and multiple conflicting demands must be met. For instance, in supply chain management, you need to ensure products are delivered on time while minimizing costs. In scheduling, you need to allocate resources effectively to meet deadlines.
3. Skill Development: By tackling problems with constraint programming, you enhance your ability to think critically and solve complex issues. These skills are highly valued across many industries, making you better equipped to handle the demands of modern business environments.
4. Broader Impacts: Efficient problem-solving using techniques like constraint programming can lead to significant cost savings, better resource utilization, and improved decision-making. These benefits are not just theoretical—they have a tangible impact on business success and operational excellence.

In summary, this isn't just a fun exercise; it's a practical demonstration of how powerful tools like constraint programming can be applied to solve real challenges, driving efficiency and success in various fields.