Last Tango with Math (CP)

The Last Tango is no longer in Paris and it seems to be on Linkedin. After coming across a logic puzzle on LinkedIn, I decided to, as some might say, take the fun out of it by solving it using constraint programming (hopefully it fills you with another type of fun) . Voilà, here is the latest episode of Optimization Online.

Here is the description of the puzzle:

• There is a board which should be filled with sun (1) and moon (0).
• Some Cells should have different values (cross)
• Some Cells should have similar values (=)
• The number of suns and stars in each row and column should be the same
• The value of some specific cells are already known (as shown in the picture)

How should we solve the problem?

Disclaimer: We're not addressing any particularly useful, meaningful, or world-changing problem here. So if you're looking for that, this may not be suitable for you. We assume you already know how to make transition from toy problems to realistic ones.

• Step zero: is to create a simple visualisation to know what is known and what is unknown.

• Let's make it more informative and inject the known values into it ( i know this is not star but matplotlib does not have a marker with 'moon' shape, sorry about it)

• The first step is to decide what kind of variables and constraints should be used. The obvious answer is boolean variables (to determine 0/1 value of unknown cells).
• Step 2: we need to create the constraints according to the problem requirements:

For each row/column the number of suns = number of stars = 3

for r in range(6):
  model.Add(sum([U[c] for c in nodes if cell[c][0] == r]) == 3)
  model.Add(sum([U[c] for c in nodes if cell[c][1] == r]) == 3)        

• For every three consecutive cells they should not have the same value
• to address this requirement, all 3 consecutive cells (horizontally and verticall) are first found and then the rules are applied to them

all_verticals = [(n,m,p) for n in nodes for m in nodes for p in nodes 
                if (cell[n][0]== cell[m][0]  and cell[m][0]== cell[p][0]) and 
                
                (cell[n][1]+1 == cell[m][1]  and cell[m][1]+1== cell[p][1])
                ]
all_horizonss = [(n,m,p) for n in nodes for m in nodes for p in nodes 
                if (cell[n][1]== cell[m][1]  and cell[m][1]== cell[p][1]) and 
                
                (cell[n][0]+1 == cell[m][0]  and cell[m][0]+1== cell[p][0])
                ]        

• Rules

for (n,m,p) in all_verticals:
  model.Add(U[n] + U[m] + U[p] <= 2)
  model.Add(U[n].Not() + U[m].Not() + U[p].Not() <= 2)
  
for (n,m,p) in all_horizonss:
  model.Add(U[n] + U[m] + U[p] <= 2)
  model.Add(U[n].Not() + U[m].Not() + U[p].Not() <= 2)        

• Some cells should have the same values (keep them in a list)

for (n,m) in same:
  model.Add(U[n] == U[m])        

• Some cells should have the different values (keep them in a list)

for (n,m) in dif:
  model.Add(U[n] != U[m])        

The whole model is here :

model = cp_model.CpModel()
solver = cp_model.CpSolver()
U = {c:model.NewBoolVar(f"sunorstar_{c}") for c in nodes}

for n in nodes:
  if cell[n][2] == 1:
    model.Add(U[n] == 1)
  elif cell[n][2] == 0:
    model.Add(U[n] == 0)


for r in range(6):
  model.Add(sum([U[c] for c in nodes if cell[c][0] == r]) == 3)
  model.Add(sum([U[c] for c in nodes if cell[c][1] == r]) == 3)

all_verticals = [(n,m,p) for n in nodes for m in nodes for p in nodes 
                if (cell[n][0]== cell[m][0]  and cell[m][0]== cell[p][0]) and 
                
                (cell[n][1]+1 == cell[m][1]  and cell[m][1]+1== cell[p][1])
                ]
all_horizonss = [(n,m,p) for n in nodes for m in nodes for p in nodes 
                if (cell[n][1]== cell[m][1]  and cell[m][1]== cell[p][1]) and 
                
                (cell[n][0]+1 == cell[m][0]  and cell[m][0]+1== cell[p][0])
                ]

for (n,m,p) in all_verticals:
  model.Add(U[n] + U[m] + U[p] <= 2)
  model.Add(U[n].Not() + U[m].Not() + U[p].Not() <= 2)
  
for (n,m,p) in all_horizonss:
  model.Add(U[n] + U[m] + U[p] <= 2)
  model.Add(U[n].Not() + U[m].Not() + U[p].Not() <= 2)

for (n,m) in same:
  model.Add(U[n] == U[m])
for (n,m) in dif:
  model.Add(U[n] != U[m])

status = solver.Solve(model)        

Results:

All rules are satisfied and all cell values are identified.

Feel free to join Optimization Online news letter.

The full code is available on github repo