Find Assignment (friends)

Run LPL Code  ,  PDF Document

Problem

“Last week my friends Anne, Carl, Eva, Gustaf and I went out for dinner every night, Monday to Friday. I missed the meal on Friday because I was visiting my sister and her friends. But otherwise, every one of us had selected a restaurant for a particular night and served as a host for that dinner. Overall, the following restaurants were selected: a French bistro, a sushi bar, a pizzeria, A Greek restaurant, and the Brauhaus. Eva took us out on Wednesday. The Friday dinner was at the Brauhaus. Carl, who doesn’t eat sushi, was the first host. Gustaf had selected the bistro for the night before one of the friends took everyone to the pizzeria. Tell me, who selected which restaurant for which night?”. This puzzle has been published in [1] p. 56.

Modeling Steps

We introduce three (ordered) sets of five elements each: a set of persons p, a set of restaurant types r, and a set of weekdays w.

1. The binary variables x_p,r,w is used as follows: x_p,r,w = 1 (true), if person p has taken us to the restaurant r on weekday w, otherwise it is 0 (false).

2. First of all, we must make sure that there is a unique assignment for a triple (p,r,w), that is, for each person p there must be a unique tuple (r,w) to be assigned, and for each restaurant r there should be a unique (p,w) tuple, and for each weekday w there must be a unique (p,r) tuple. Hence

   

3. “I missed the meal on Friday” is a constraint saying that x_5,r,5 = 0  forall r

4. “Eva took us out on Wednesday” is formulated as ∨ _rx_3,r,3

5. “The Friday dinner was at the Brauhaus” is modeled as ∨ _px_p,5,5

6. “Carl, who doesn’t eat sushi, was the first host” is ∨ _r|r⁄=2x_2,r,1

7. “Gustaf had selected the bistro…” is ∨ _wx_4,1,w

8. “…for the night before one of the friends took everyone to the pizzeria” can be formulated as

   We are interested in a feasible solution subject to all these requirements and conditions.

model friends "Find Assignment"; 
    set p:=[Anne Carl Eva Gustaf I]; 
        r:=[French Sushi Pizzeria Greek Brauhaus]; 
        w:=[Mon Tue Wed Thu Fri]; 
    binary variable x{p,r,w}; 
    constraint 
      A{p}: sum{r,w} x = 1; 
      B{r}: sum{p,w} x = 1; 
      C{w}: sum{p,r} x = 1; 
      M1{r}: ~x[5,r,5]; 
      M2   : or{r} x[3,r,3]; 
      M3   : or{p} x[p,5,5]; 
      M4   : or{r|r<>2} x[2,r,1]; 
      M5   : or{w} x[4,1,w]; 
      M6{w|w>1}: x[4,1,w-1] -> or{p} x[p,3,w]; 
    solve; 
    Write{w,p,r|x}('On %s %s took us to the %s' n',w,p,r); 
  end

Solution

The solution is

   On Mon Carl took us to the Greek     On Tue Gustaf took us to the French     On Wed Eva took us to the Pizzeria     On Thu I took us to the Sushi     On Fri Anne took us to the Brauhaus

Further Comments

This model is one way to represent the problem. Another model approach for a similar problem is given in model einstein. The approach used here is more appropriate for integer linear solvers, whereas the model in einstein is more suitable for constraint programming.

Questions

1. The solution is unique, that is there is exactly one solution. How can you check this?

2. Give a solution if Carl also hates Pizzas.

Answers

1. Five variable out of 125 are true, all others are false. To check the uniqueness, assign false to each true variable in turn and solve all models with this additional constraints. It shows that they are all infeasible, therefore the solution is unique.

2. The solution is already in the previous solution: Since Carl invite to a Greek restaurant the fact that he does not like Pizzas does not change anything. To be sure change a constraint to:

      constraint M4: or{r|r<>2 and r<>3} x[2,r,1];

References