Solving Logic puzzles through optimization

Question

I have the following "logic puzzle" (I think this is considered as a "scheduling problem"):

In this problem, there are 5 basketball players - provided some clues about their nicknames and heights, you are required to find the correct combinations of players-nicknames-heights.

In a previous post (https://stackoverflow.com/questions/70527987/solving-logic-puzzles-using-r), I learned how to solve this problem with "brute force" using the R programming language:

library(dplyr)

dt <- purrr::cross_df(list(
  name = list(c("Bill", "Ernie", "Oscar", "Sammy", "Tony")),
  nickname = combinat::permn(c("Slats", "Stretch", "Tiny", "Tower", "Tree")), 
  height = combinat::permn(c(6.6, 6.5, 6.3, 6.1, 6))
))

dt %>%  
  group_by(id = (seq_len(n()) - 1L) %/% 5L) %>% 
  filter(
    height[name == "Oscar"] > height[nickname == "Tree"], 
    height[nickname == "Tree"] > height[name == "Tony"], 
    height[name == "Bill"] > height[name == "Sammy"], 
    height[name == "Bill"] < height[nickname == "Slats"], 
    nickname[name == "Tony"] != "Tiny",
    height[nickname == "Stretch"] > height[name == "Oscar"], 
    height[nickname == "Stretch"] < 6.6
  )

#output
# A tibble: 5 x 4
# Groups:   id [1]
  name  nickname height    id
  <chr> <chr>     <dbl> <int>
1 Bill  Stretch     6.5 14398
2 Ernie Slats       6.6 14398
3 Oscar Tiny        6.3 14398
4 Sammy Tree        6.1 14398
5 Tony  Tower       6   14398

However, I am curious to know if this problem can be solved using modern optimization algorithms. For instance, if there were 100,000 basketball players in this problem, it would simply be impossible to solve using brute force - to create a list containing combinations of every player-nickname-height would unlikely be storable within a computer.

I have read that there modern optimization algorithms can be used instead (e.g. particle swarm optimization, simulated annealing, nelder-meade, genetic algorithm, etc.) for such problems. I have spent some time reading about the math behind these optimization algorithms and think I understand the general ideas - however, I am not sure how to define the "optimization functions" for these problems, and which "metric" should be used as a target.

For example, in this problem, perhaps the "fraction of the optimization constraints satisfied" by each combination of player-height-nickname can be used as a metric?

If (not factually correct, just sketching a quick example)

• Combinations 1 : Bill = Slats, Ernie = Stretch, Oscar = Tiny, Sammy = Tiny and Tony = Tree. Bill is 6'6, Ernie is 6'5, Oscar is 6'3, Sammy is 6'1 and Tony is 6'. satisfies 3/4th's of the optimization constraints

• Combinations 53 : Bill = Stretch, Ernie = Slats, Oscar = Tiny, Sammy = Tiny and Tony = Tree. Bill is 6'6, Ernie is 6'5, Oscar is 6'3, Sammy is 6 and Tony is 6'1. satisfies only 2/4th's of the optimization constraints

Perhaps we might be able to say that Combination 1 had a higher "performance metric" than Combination 53, and as a result, it might be more advantageous to consider combinations that are "closer" to Combination 1 compared to Combination 53.

Can someone please show me how this basketball problem can be using modern optimization algorithms in the R programming language?

Answer 1

This is similar to the well known Zebra Puzzle.

You can solve it using integer programming techniques as follows:

Define binary variables $x_{p,n}^h$ that take value $1$ if and only if player $p\in \{Bill,...,Tony\}$ has nickname $n \in \{Slats,...,Tree\}$ and height $h \in \{6,...,6'6 \}$. So $x_{p,n}^h=1$ if and only if combination $(p,n,h)$ is valid.

There no objective function here, so just use a dummy one, e.g., $0$, and minimize (or maximize) this function subject to the following set of constraints:

• each player has a unique nickname and height: $$ \sum_{n}\sum_{h}x_{p,n}^h = 1 \quad \forall p $$
• each nickname has a unique player and height: $$ \sum_{p}\sum_{h}x_{p,n}^h = 1 \quad \forall n $$
• each height has a unique player and nickname: $$ \sum_{p}\sum_{n}x_{p,n}^h = 1 \quad \forall h $$
• Oscar is taller than Tree... : $$ x_{Oscar,n}^{h_1} \le \sum_{p}\sum_{h_2| h_2 < h_1 } x_{p,Tree}^{h_2} \quad \forall n, \forall h_1 $$
• ...who is taller than Tony: $$ x_{p,Tree}^{h_1} \le \sum_{n}\sum_{h_2| h_2 < h_1 } x_{Tony,n}^{h_2} \quad \forall n,\; \forall h_1 $$
• Bill is taller than Sammy...: $$ x_{Bill,n_1}^{h_1} \le \sum_{n_2}\sum_{h_2| h_2 < h_1 } x_{Sammy,n_2}^{h_2} \quad \forall n_1,\;\forall h_1 $$
• ...but shorter than Slats: $$ x_{Bill,n}^{h_1} \le \sum_{p}\sum_{h_2| h_2 > h_1 } x_{p,Slats}^{h_2} \quad \forall n,\; \forall h_1 $$
• Tony's nickname is not Tiny: $$ x_{Tony,Tiny}^h = 0 \quad \forall h $$ Note that you could also simply not define these variables.
• Stretch is taller than Oscar...: $$ x_{p,Stretch}^{h_1} \le \sum_{n}\sum_{h_2| h_2 > h_1 } x_{Oscar,n}^{h_2} \quad \forall p,\; \forall h_1 $$
• ...but not the tallest: $$ x_{p,Stretch}^{6'6} = 0 \quad \forall p $$

---

Here is a Python implementation:

from pulp import *

# define data
players = ["Bill", "Ernie", "Oscar", "Sammy", "Tony"]
nicknames = ["Slats", "Stretch", "Tiny", "Tower", "Tree"]
heights = [6, 6.1, 6.3, 6.5, 6.6]

# create problem
prob = LpProblem("B_Balls", LpMinimize)

# define variables
x = LpVariable.dicts("x", (players, nicknames, heights), cat=LpBinary)

# add dummy objective function
prob += 0

# each player has a unique nickame and height
for p in players:
    prob += lpSum(x[p][n][h] for n in nicknames for h in heights) == 1

# each nickname has a unique player and height
for n in nicknames:
    prob += lpSum(x[p][n][h] for p in players for h in heights) == 1

# each height has a unique player and nickname
for h in heights:
    prob += lpSum(x[p][n][h] for n in nicknames for p in players) == 1

# Oscar is taller than Tree
for n in nicknames:
    for h in heights:
        prob += x["Oscar"][n][h] <= lpSum(
            x[p]["Tree"][k] for p in players for k in heights if k < h
        )

# Tree is taller than Tony
for p in players:
    for h in heights:
        prob += x[p]["Tree"][h] <= lpSum(
            x["Tony"][n][k] for n in nicknames for k in heights if k < h
        )

# Bill is taller than Sammy
for n in nicknames:
    for h in heights:
        prob += x["Bill"][n][h] <= lpSum(
            x["Sammy"][m][k] for m in nicknames for k in heights if k < h
        )

# Bill is shorter than Slats
for n in nicknames:
    for h in heights:
        prob += x["Bill"][n][h] <= lpSum(
            x[p]["Slats"][k] for p in players for k in heights if k > h
        )

# Tony is not Tiny
for h in heights:
    prob += x["Tony"]["Tiny"][h] == 0

# Stretch is taller than Oscar
for p in players:
    for h in heights:
        prob += x[p]["Stretch"][h] <= lpSum(
            x["Oscar"][n][k] for n in nicknames for k in heights if k < h
        )

# Stretch is not the tallest
for p in players:
    prob += x[p]["Stretch"][6.6] == 0

# solve problem, and iteratively find different solutions, if any
k = 1
while True:
   print()
   print("solution %s" % k)
   k += 1
   prob.solve(pulp.PULP_CBC_CMD(msg=0))
   print("Status:", LpStatus[prob.status])
   # The solution is printed if it was deemed "optimal" i.e met the constraints
   if LpStatus[prob.status] == "Optimal":
      # print solution
       for p in players:
          for n in nicknames:
             for h in heights:
                if value(x[p][n][h]) > 0.1:
                    print(p, n, h)
    # The constraint is added that the same solution cannot be returned again
    prob += lpSum(x[p][n][h] for p in players for n in nicknames for h in heights if value(x[p][n][h]) > 0.1) <= 5 - 1
 
   # If a new optimal solution cannot be found, we end the program
   else:
       break

A solution is found in 0.12 seconds with the default open-source CBC solver:

And apparently this solution is unique.

If I run the program with CPLEX, the problem is solved in 0.01 sec:

---

Another option would be to use some local search technique (e.g., tabu search), to minimize the number of "conflicts" given a configuration. You would have to define some move, for example, swap two nicknames, and count the number of times a constraint is violated. By iteratively moving around the search space while minimizing the number of violated constraints, you will (or should) converge to the desired solution. This has also been done for the Zebra Problem mentioned above.

Answer 2

This problem can be elegantly formulated through Constraint Programming (CP). This problem does not have an objective function: it's a Constraint Satisfaction Problem, not a Constraint Optimization Problem. CP would be a natural choice for this problem, since CP, similar to how humans would solve this problem, relies on a technique called 'inference'. In CP, variables have a domain (the set of values that can possibly be assigned to a variable). Through Constraint Propagation, a Constraint solver infers which values a variable cannot take and the solver eliminates those values from the domains of the variables until each variable only has 1 value left.

To solve your problem, we would define the following variables:

• $h_p\in \{6,...,6'6 \}$ is the height of player $p\in \{Bill,...,Tony\}$.
• $name_n\in \{Bill,...,Tony\}$ is the name of the person with nick $n \in \{Slats,...,Tree\}$

We specify the following constraints:

• each player has a unique height: $$ alldifferent(h_p|\forall p) $$
• each player has a unique nick name (i.e. no player has 2 nicks): $$ alldifferent(name_n|\forall n) $$
• Oscar is taller than Tree... : $$ h_{Oscar}>h_{name_{Tree}} $$
• ...who is taller than Tony: $$ h_{name_{Tree}}>h_{Tony} $$
• Bill is taller than Sammy...: $$ h_{Bill}>h_{Sammy} $$
• ...but shorter than Slats: $$ h_{Bill}<h_{name_{Slats}} $$
• Tony's nickname is not Tiny: $$ name_{Tiny}\neq Tony $$
• Stretch is taller than Oscar...: $$ h_{name_{Stretch}}>h_{Oscar} $$
• ...but not the tallest: $$ h_{name_{Strech}}<6'6 $$

A few remarks:

• $allDifferent(\cdot)$ is a so-called global constraint in CP that states that all the variables over which the constraint is defined must take pairwise different values
• in CP, unlike in LP/MIP/... you can index a variable with a variable! So $h_{name_{Tree}}$ is a valid statement. This construction is called an element constraint in CP. Also notice how much more concise and readable the above formulation is compared to a MIP formulation.
• "Tony's nickname is not Tiny": In CP, you would not define this as a constraint; instead, you would simply omit the value 'Tony' from the domain of variable $name_{Tiny}$ when you define this variable.

CP would solve the above problem very efficiently. Moreover, since CP is an exact approach, the solver would tell you whether a feasible solution exists at all, or perhaps whether there exist multiple solutions that satisfy the above constraints. This would be a lot more efficient than using some kind of meta heuristic such as the ones you mentioned (genetic algorithm/simulated annealing/etc). Moreover, many heuristics require an objective to guide the search. A common objective in puzzles is to define how 'close' the solution is to a feasible solution, e.g. how many conflicts there are. It is well known for puzzles that a solution with only 1 minor conflict, might still look very different than the actual optimal solution.

---

The above model, implemented in Python and Docplex (IBM CP Optimizer):

from docplex.cp.model import CpoModel


## Data
players = ["Bill", "Ernie", "Oscar", "Sammy", "Tony"]
nicknames = ["Slats", "Stretch", "Tiny", "Tower", "Tree"]
heights = [60, 61, 63, 65, 66]


## Create CPO model
mdl = CpoModel()


## Create model variables

height = mdl.integer_var_dict(keys=players,domain=heights)
player = mdl.integer_var_dict(nicknames,0,len(players))


## Create model constraints

# each player has a unique height:
mdl.add(mdl.all_diff([height[p] for p in players]))

# each player has a unique nick name (i.e. no player has 2 nicks):
mdl.add(mdl.all_diff([player[n] for n in nicknames]))

# Oscar is taller than Tree... :
mdl.add(height["Oscar"] > mdl.element([height[p] for p in players],player["Tree"]))

# ...who is taller than Tony:
mdl.add(mdl.element([height[p] for p in players],player["Tree"]) > height["Tony"])

# Bill is taller than Sammy...: 
mdl.add(height["Bill"] > height["Sammy"])

# ...but shorter than Slats:
mdl.add(height["Bill"] < mdl.element([height[p] for p in players],player["Slats"]))

# Tony's nickname is not Tiny:
mdl.add(player["Tiny"] != players.index("Tony"))

# Stretch is taller than Oscar...: 
mdl.add(mdl.element([height[p] for p in players],player["Stretch"]) > height["Oscar"])

# ...but not the tallest:
mdl.add(mdl.element([height[p] for p in players],player["Stretch"]) < max(heights))


## Solve model
print("\nSolving model....")
msol = mdl.solve(agent='local',execfile='/opt/ILOG/CPLEX_Studio201/cpoptimizer/bin/x86-64_linux/cpoptimizer',TimeLimit=10,DefaultInferenceLevel="Extended")

if msol:
    print("Solution status: " + msol.get_solve_status())
    nick_lookup = {players[msol[player[nick]]]:nick for nick in nicknames}
    
    for name in players:
        print(name+"("+nick_lookup[name]+"): "+str(msol[height[name]]))

else:
    print("No solution found")

A solution was found in 0.02s:

Answer 3

You can solve this using a constraint satisfaction/constraint programming (CP) solver (and possibly modeling language). In R, you might use the rminizinc package package, which links to the open-source MiniZinc language, which comes with a number of solvers.

CP models (which can be optimization models but are often just constraint satisfaction models) can be faster to solve than integer programming models when all variables are discrete and when logic constraints are present in the model. In particular, they generally come with built in "all different" constraints, which apply here. (No two players have the same height or the same nickname.)

Some CP solvers are particularly good for scheduling problems (which this really is not).