Solving logic puzzles with F# and Z3

Computers can help to solve non-trivial problems (e.g. scheduling, optimization, software verification) by automatically deriving models that satisfy sets of constraints. This is called reasoning with computer support or automated reasoning. There are various tools on the market that can be applied; I will be using Microsoft's Z3 theorem prover. In this blog post, I will be solving a logic puzzle with Z3. The puzzle consists of a set of constraints that a solution must satisfy.

Zebra puzzle

The zebra puzzle (also known as "Einstein's puzzle", although there is no proof of Einstein being the author) consists of 15 rules involving 5 people, 5 houses, 5 pets, 5 drinks and 5 brands of cigarettes. The cigarettes are not used in more politically correct versions of the puzzle. The rules are as follows:

  1. The British person lives in the red house.
  2. The Swede keeps dogs as pets.
  3. The Dane drinks tea.
  4. The green house is on the left of the white house.
  5. The green homeowner drinks coffee.
  6. The man who smokes Pall Mall keeps birds.
  7. The owner of the yellow house smokes Dunhill.
  8. The man living in the center house drinks milk.
  9. The Norwegian lives in the first house.
  10. The man who smokes Blend lives next to the one who keeps cats.
  11. The man who keeps the horse lives next to the man who smokes Dunhill.
  12. The man who smokes Bluemaster drinks beer.
  13. The German smokes Prince.
  14. The Norwegian lives next to the blue house.
  15. The man who smokes Blend has a neighbor who drinks water.

The question is: who owns the zebra?. We can use a theorem prover to answer this question. In order to do this, we need to first come up with a representation of these constraints in logical terms. Each nationality, pet, house color, cigarette brand and drink is associated with a house number (1 through 5) for which we construct a variable. Notice that that this representation is convenient for expressing constraints (4), (9), (14) and (15). We have 5 sets of variables that can be indexed (arrays/lists):

 \begin{array}{l} Nat = \{\text{brit}, \text{swede}, \text{dane}, \text{norwegian}, \text{german}\} \\ Col = \{\text{red}, \text{white}, \text{green}, \text{yellow}, \text{blue}\} \\ Pet = \{\text{dogs}, \text{birds}, \text{horses}, \text{cats}, \text{zebra}\} \\ Drk = \{\text{tea}, \text{beer}, \text{coffee}, \text{water}, \text{milk}\} \\ Smk = \{\text{pallmall}, \text{dunhill}, \text{blends}, \text{prince}, \text{bluemasters}\} \end{array}

Assume that V = Nat \cup Col \cup Pet \cup Drk \cup Smk describes all variables.

Basic constraints

Before we begin with the 15 rules, we need to make sure that some implicit constraints are expressed.

Each variable is associated with a house 1 through 5

\forall x \in V. 1 \leq x \leq 5

All variables in each category refer to different houses

 \text{diff}(S) \mathrel{\mathop:}= \forall (i, j) \in \{1, \cdots, 5\}^2. i \neq j \implies S_i \neq S_j

. Then we have the following constraints: \text{diff}(Nat), \text{diff}(Col), \text{diff}(Pet), \text{diff}(Drk) and \text{diff}(Smk).

Rules

  • The British person lives in the red house.

     \text{brit} = \text{red}

  • The Swede keeps dogs as pets.

     \text{swede} = \text{dogs}

  • The Dane drinks tea.

     \text{dane} = \text{tea}

  • The green house is on the left of the white house.

     \text{green} = \text{white} - 1

  • The green homeowner drinks coffee.

     \text{green} = \text{coffee}

  • The man who smokes Pall Mall keeps birds.

     \text{pallmall} = \text{birds}

  • The owner of the yellow house smokes Dunhill.

     \text{yellow} = \text{dunhill}

  • The man living in the center house drinks milk.

     \text{milk} = 3

  • The Norwegian lives in the first house.

     \text{norwegian} = 1

  • The man who smokes Blend lives next to the one who keeps cats.

     (\text{blend} = \text{cats} - 1) \vee (\text{blend} = \text{cats} + 1)

  • The man who keeps the horse lives next to the man who smokes Dunhill.

     (\text{horse} = \text{dunhill} - 1) \vee (\text{horse} = \text{dunhill} + 1)

  • The man who smokes Bluemaster drinks beer.

     \text{bluemaster} = \text{beer}

  • The German smokes Prince.

     \text{german} = \text{prince}

  • The Norwegian lives next to the blue house.

     (\text{norwegian} = \text{blue} - 1) \vee (\text{norwegian} = \text{blue} + 1)

  • The man who smokes Blend has a neighbor who drinks water.

     (\text{water} = \text{blend} - 1) \vee (\text{water} = \text{blend} + 1)

Feeding Z3

Now that we have a representation, we can feed it to Z3. The tool is available here. Create a F# project and add a reference to "Microsoft.Z3.dll" so that we can use the API. We start with the definition of the Z3 context. Make sure you have opened the Microsoft.Z3 namespace and add the following line:


let context = new Context()

Now, let us add the sets in the form of lists:


let Nat = ["brit"; "swede"; "dane"; "norwegian"; "german"]
let Col = ["red"; "white" ;"green";"yellow";"blue"]
let Pet = ["dogs"; "birds"; "horses"; "cats";"fish"]
let Drk = ["tea";"beer";"coffee";"water";"milk"]
let Smk = ["pallmall";"dunhill";"blends";"prince";"bluemasters"]
let V   = Nat @ Col @ Pet @ Drk @ Smk

In order to use these variables, we need to define them in the Z3 context. Define a dictionary that maps names to variable references, where each variable is of type integer:


//the body of vars is only evaluated once
let vars = V |> List.map ( fun v -> (v, context.MkConst(v, context.MkIntSort())) ) |> dict

Construct the "diff" function; it returns a term that represents a constraint:


let diff lst = 
    let constr = [|for v in lst do 
                      let cs = [|for v' in lst do if v' <> v then yield context.MkNot(context.MkEq(vars.[v], vars.[v']))|]
                      yield context.MkAnd(cs)
                 |]
    context.MkAnd(constr)

Note that a chain of conjunctions is constructed, which is equivalent to the universal quantifier we used in diff.
Also, we define a helper function to construct an integer constant and a function to define a "neighbor" constraint term:


let mkInt (n:int) = context.MkIntNumeral(n)

//is x a neighbor of y
let isNeighborOf x y = context.MkOr(context.MkEq(vars.[x], context.MkSub(vars.[y], mkInt 1)),
                            context.MkEq(vars.[x], context.MkAdd(vars.[y], mkInt 1))
                        )

Define the constraint that all variables range between 1 and 5:


let rangeConstr = 
        let constr = vars |> Seq.map ( fun kv -> 
                                     context.MkAnd(context.MkGt(kv.Value, mkInt 0), context.MkLt(kv.Value, mkInt 6))
                                   )
        context.MkAnd(Array.ofSeq constr)

Define the constraint that all variables in a set point to different houses:


let allDiff = context.MkAnd(
                    [| 
                        diff Nat;
                        diff Col;
                        diff Pet;
                        diff Drk;
                        diff Smk
                    |])

Now define all the game rules:


let isEqual x y = context.MkEq(vars.[x], vars.[y])
//The Brit lives in the red house
let constr1 = isEqual "brit" "red"
//The Swede keeps dogs as pets.
let constr2 = isEqual "swede" "dogs"
//The Dane drinks tea.
let constr3 = isEqual "dane" "tea"
//The green house is on the left of the white house.
let constr4 = context.MkEq(vars.["green"], context.MkSub(vars.["white"], mkInt 1))
//The green house's owner drinks coffee.
let constr5 = isEqual "green" "coffee"
//The person who smokes Pall Mall rears birds.
let constr6 = isEqual "pallmall" "birds"
//The owner of the yellow house smokes Dunhill.
let constr7 = isEqual "yellow" "dunhill"
//The man living in the center house drinks milk.
let constr8 = context.MkEq(vars.["milk"], mkInt 3)
//The Norwegian lives in the first house.
let constr9 = context.MkEq(vars.["norwegian"], mkInt 1)
//The man who smokes Blends lives next to the one who keeps cats.
let constr10 = isNeighborOf "blends" "cats"
//The man who keeps the horse lives next to the man who smokes Dunhill.
let constr11 = isNeighborOf "horses" "dunhill"
//The owner who smokes Bluemasters drinks beer.
let constr12 = isEqual "bluemasters" "beer"
//The German smokes Prince.
let constr13 = isEqual "german" "prince"
//The Norwegian lives next to the blue house.
let constr14 = isNeighborOf "norwegian" "blue"
//The man who smokes Blends has a neighbor who drinks water.
let constr15 = isNeighborOf "water" "blends"

Combine all the constraints we defined in one term:


let puzzle = context.MkAnd([|allDiff; rangeConstr; constr1; constr2; constr3; constr4; constr5; constr6; constr7; constr8; constr9;constr10;
                             constr11; constr12; constr13; constr14; constr15|])

Now ask Z3 for a model that satisfies our constraints:


let program = 
    let _ = context.AssertCnstr(puzzle)
    let model:Model ref = ref null
    let result = context.CheckAndGetModel(model)
    if result = LBool.True then model.Value.Display(System.Console.Out)

In the model, zebra and german have the value 4 (4th house). Therefore, the german has the zebra.

Comments are closed.