ZebraPuzzles.jl 🦓

Welcome to the documentation for ZebraPuzzles.jl!

ZebraPuzzles is a Julia package for the logical puzzles of the zebra type. It provides a framework for defining puzzles, adding clues about the puzzle, and finding a solution which satisfies the clues.

Getting Started 🚀

To get started, you'll need to define a puzzle. A puzzle is defined by a set of attributes and a set of clues.

Defining a Puzzle 🗺️

A zebra puzzle is characterized by a number of subjects and a number of attribute types of which every subject has a unique variant.

ZebraPuzzles.ZebraPuzzle — Type

ZebraPuzzle{K,N,Attrs}

Represents a Zebra Puzzle, a type of logic puzzle where one deduces relationships between different subjects and their attributes based on a set of clues.

Type Parameters

K: number of puzzle subjects and therefore also the number of distinct values of every attribute type
N: number of attributes of per subject
Attrs: attribute types Tuple{Attr1,Attr2,...} where Attri can be e.g. Hat, Nationality, Person or House. It has length N.

source

There are two forms of a puzzle that you may want to create.

If you would like to have a puzzle that is not yet solved (for example with the intention of solving it later), you can define it by stating the variants of attributes that can be associated with a subject.

Unsolved Puzzle: A puzzle which has a set of variants for each attribute type, but they are not yet grouped as belonging to a single subject. (UnsolvedZebraPuzzle)

puz_unsolved = ZebraPuzzle(
    Drink => ("coffee", "milk", "orange juice", "tea", "water"),
    House => ("blue", "green", "ivory", "red", "yellow"),
    Nationality => ("Englishman", "Japanese", "Spaniard", "Ukrainian", "Norwegian"),
    Pet => ("dog", "horse", "snails", "zebra", "fox"),
    Smoke => ("Chesterfields", "Lucky Strike", "Old Gold", "Parliaments", "Kools"),
)

UnsolvedZebraPuzzle{5, 5, Tuple{Drink, House, Nationality, Pet, Smoke}} with no clues
┌────────────────────────────────────────────────────────────────────────┐
│    Drink              coffee, milk, orange juice, tea, water           │
├────────────────────────────────────────────────────────────────────────┤
│    House                  blue, green, ivory, red, yellow              │
├────────────────────────────────────────────────────────────────────────┤
│ Nationality    Englishman, Japanese, Spaniard, Ukrainian, Norwegian    │
├────────────────────────────────────────────────────────────────────────┤
│     Pet                   dog, horse, snails, zebra, fox               │
├────────────────────────────────────────────────────────────────────────┤
│    Smoke     Chesterfields, Lucky Strike, Old Gold, Parliaments, Kools │
└────────────────────────────────────────────────────────────────────────┘

Solved Puzzle: A puzzle which is defined by a truth table, which specifies which attributes belong together. (SolvedZebraPuzzle)

puz_solved = ZebraPuzzle(
    (House("yellow"), Nationality("Norwegian"), Drink("water"), Smoke("Kools"), Pet("fox")),
    (House("blue"), Nationality("Ukrainian"), Drink("tea"), Smoke("Chesterfields"), Pet("horse")),
    (House("red"), Nationality("Englishman"), Drink("milk"), Smoke("Old Gold"), Pet("snails")),
    (House("ivory"), Nationality("Spaniard"), Drink("orange juice"), Smoke("Lucky Strike"), Pet("dog")),
    (House("green"), Nationality("Japanese"), Drink("coffee"), Smoke("Parliaments"), Pet("zebra")),
)

SolvedZebraPuzzle{5, 5, Tuple{House, Nationality, Drink, Smoke, Pet}} with no clues
┌──────────────────────────────────────────────────────────┐
│ House   Nationality      Smoke         Drink       Pet   │
├──────────────────────────────────────────────────────────┤
│ yellow   Norwegian       Kools         water       fox   │
├──────────────────────────────────────────────────────────┤
│  blue    Ukrainian   Chesterfields      tea       horse  │
├──────────────────────────────────────────────────────────┤
│  red    Englishman     Old Gold         milk      snails │
├──────────────────────────────────────────────────────────┤
│ ivory    Spaniard    Lucky Strike   orange juice   dog   │
├──────────────────────────────────────────────────────────┤
│ green    Japanese     Parliaments      coffee     zebra  │
└──────────────────────────────────────────────────────────┘

Both of these puzzle types can contain clues which can lead the solver to a solution and in order to define a puzzle that is solvable, you need to add these to enable a solver to infer it.

Adding Clues 📐

There are various types of clues that can help solve a zebra puzzle. They may hint towards the position of the subject in relation to other subjects (direction, distance, etc.) or relation of the attributes (belong together, do not belong together, etc.). Clues may be added to the puzzle by directly specifying them and adding them with add_clue!

add_clue!(
    puz_unsolved,
    Clue(Drink("coffee"), Pet("snails")) # attributes "coffee" and "snails" belong together
)

and they are checked for consistency with the puzzle in the process so that they do not contradict the previous clues. Checking the clues may also be done separately by the check function

julia> ZP.check(
           puz_unsolved,
           Clue(Drink("coffee"), Not(Pet("snails")))
       ) # ❌ inconsistent clue (contradiction)ERROR: ConflictingClue: clue Drink("coffee") ⟹ ¬Pet("snails") is in conflict with the current rules/clues in the puzzle.

It does not only control the consistency of the clues but also checks that the clue is not implied by the previous ones to assure the minimality property of the puzzle clue set.

julia> add_clue!(puz_unsolved, Clue(House("ivory"), Pet("snails")));
julia> ZP.check(puz_unsolved, Clue(Drink("coffee"), House("ivory"))) # ❌ clue implied by the previous onesERROR: ImpliedClue: clue Drink("coffee") ⟹ House("ivory") is implied by the rules and clues already included in the puzzle.

You can also add multiple clues at once with add_clues!

add_clues!(puz_unsolved,
    [
         ExactRelativePosition(House("green"), House("ivory"), 1),
         Clue(Smoke("Old Gold"), Pet("snails")),
         Clue(Smoke("Kools"), House("yellow")),
         AbsolutePosition(Drink("milk"), 3),
         AbsolutePosition(Nationality("Norwegian"), 1),
         AbsoluteDistance(Smoke("Chesterfields"), Pet("fox"), 1),
         AbsoluteDistance(Smoke("Kools"), Pet("horse"), 1),
         Clue(Smoke("Lucky Strike"), Drink("orange juice")),
    ]
)

It is also possible to fill clues so that the puzzle is solvable (uniquely) using fill_clues!

fill_clues!(puz_unsolved)

We end up with a uniquely solvable puzzle with a minimal number of clues (i.e. any clue removal leads to non-uniqueness/insolubility).

julia> puz_unsolvedUnsolvedZebraPuzzle{5, 5, Tuple{Drink, House, Nationality, Pet, Smoke}} with 19 clues
┌────────────────────────────────────────────────────────────────────────┐
│    Drink              coffee, milk, orange juice, tea, water           │
├────────────────────────────────────────────────────────────────────────┤
│    House                  blue, green, ivory, red, yellow              │
├────────────────────────────────────────────────────────────────────────┤
│ Nationality    Englishman, Japanese, Spaniard, Ukrainian, Norwegian    │
├────────────────────────────────────────────────────────────────────────┤
│     Pet                   dog, horse, snails, zebra, fox               │
├────────────────────────────────────────────────────────────────────────┤
│    Smoke     Chesterfields, Lucky Strike, Old Gold, Parliaments, Kools │
└────────────────────────────────────────────────────────────────────────┘

clues:
1) Drink("coffee") ⟹ Pet("snails")
2) House("ivory") ⟹ Pet("snails")
3) Pos[House("green")] == Pos[House("ivory")] + 1
4) Smoke("Old Gold") ⟹ Pet("snails")
5) Smoke("Kools") ⟹ House("yellow")
6) Pos[Drink("milk")] == 3
7) Pos[Nationality("Norwegian")] == 1
8) abs(Pos[Smoke("Chesterfields")] - Pos[Pet("fox")]) == 1
9) abs(Pos[Smoke("Kools")] - Pos[Pet("horse")]) == 1
10) Smoke("Lucky Strike") ⟹ Drink("orange juice")
11) Pos[Smoke("Lucky Strike")] > Pos[Smoke("Old Gold")]
12) Pos[Smoke("Lucky Strike")] == 2
13) Pos[House("blue")] < Pos[Pet("zebra")]
14) House("blue") ⟹ ¬Nationality("Spaniard")
15) House("red") ⟹ Nationality("Spaniard")
16) Nationality("Japanese") ⟹ Pet("zebra")
17) Pos[Pet("horse")] > Pos[Pet("zebra")]
18) Drink("orange juice") ⟹ ¬Nationality("Ukrainian")
19) abs(Pos[Drink("milk")] - Pos[Drink("water")]) == 1

All of the above methods can also be used for the solved puzzle and additionally the correctness of the clues against the solution is checked

julia> add_clue!(puz_solved, Clue(Drink("milk"), House("green")))ERROR: InvalidClue: `DirectClue` clue Drink("milk") ⟹ House("green") is not satisfied in the puzzle. Truth value of the clue is `true` which is in conflict with the puzzle.

Clues are filled so that they are in accordance with the puzzles truth table

julia> fill_clues!(puz_solved)SolvedZebraPuzzle{5, 5, Tuple{House, Nationality, Drink, Smoke, Pet}} with 21 clues
┌──────────────────────────────────────────────────────────┐
│ House   Nationality      Smoke         Drink       Pet   │
├──────────────────────────────────────────────────────────┤
│ yellow   Norwegian       Kools         water       fox   │
├──────────────────────────────────────────────────────────┤
│  blue    Ukrainian   Chesterfields      tea       horse  │
├──────────────────────────────────────────────────────────┤
│  red    Englishman     Old Gold         milk      snails │
├──────────────────────────────────────────────────────────┤
│ ivory    Spaniard    Lucky Strike   orange juice   dog   │
├──────────────────────────────────────────────────────────┤
│ green    Japanese     Parliaments      coffee     zebra  │
└──────────────────────────────────────────────────────────┘

clues:
1) Pos[Smoke("Old Gold")] < Pos[Drink("orange juice")]
2) Pos[House("ivory")] == 4
3) Pos[Smoke("Chesterfields")] == 2
4) Pos[Drink("tea")] < Pos[Nationality("Englishman")]
5) Pos[House("blue")] < Pos[House("green")]
6) Pos[Smoke("Kools")] + 3 == Pos[Smoke("Lucky Strike")]
7) Pos[Pet("horse")] + 3 == Pos[Smoke("Parliaments")]
8) Pos[House("red")] == 3
9) Pos[Pet("fox")] + 2 == Pos[Nationality("Englishman")]
10) abs(Pos[Nationality("Spaniard")] - Pos[Drink("coffee")]) == 1
11) Pos[Nationality("Ukrainian")] < Pos[Smoke("Lucky Strike")]
12) Pos[Nationality("Norwegian")] < Pos[House("red")]
13) abs(Pos[Pet("horse")] - Pos[Drink("milk")]) == 1
14) Nationality("Japanese") ⟹ ¬Drink("milk")
15) Pos[Nationality("Norwegian")] == 1
16) Pet("horse") ⟹ ¬Drink("water")
17) Pos[Drink("water")] == 1
18) abs(Pos[Smoke("Parliaments")] - Pos[Pet("snails")]) == 2
19) Pos[House("red")] == Pos[House("yellow")] + 2
20) abs(Pos[Drink("orange juice")] - Pos[Pet("fox")]) == 3
21) Pos[Smoke("Chesterfields")] + 2 == Pos[Pet("dog")]

Question ❓

You may not want to require the full truth table as the solution. In this case, you may want to phrase a specific Question about the puzzle. You can either ask a question about an attribute of a subject (AttributeQuestion)

attrq = rand(AttributeQuestion, puz_unsolved)

AttributeQuestion{Pet, House}(House("ivory"))

or a question about the position of a subject (PositionQuestion)

posq = rand(PositionQuestion, puz_unsolved)

PositionQuestion{Pet}(Pet("snails"))

Similarly to the case of clues, we can add a question to the puzzle with add_question!.

Random Puzzle Generation 🎲

Puzzles with a given number of attributes and subject can also be randomly generated

rand(UnsolvedZebraPuzzle{3,3})

UnsolvedZebraPuzzle{3, 3, Tuple{Person, Drink, Pet}} with 5 clues and 1 questions
┌──────────────────────────────────┐
│ Person     Dan, Grace, David     │
├──────────────────────────────────┤
│ Drink   tea, orange juice, water │
├──────────────────────────────────┤
│  Pet    cat, ferret, guinea pig  │
└──────────────────────────────────┘

clues:
1) abs(Pos[Pet("ferret")] - Pos[Drink("tea")]) == 1
2) Pos[Drink("orange juice")] == Pos[Person("David")] + 1
3) Pos[Pet("cat")] == Pos[Pet("guinea pig")] + 2
4) Drink("tea") ⟹ Person("Dan")
5) Pos[Drink("water")] > Pos[Person("Dan")]

questions:
1) Pet[Drink("water")]?

rand(UnsolvedZebraPuzzle{3,4})

UnsolvedZebraPuzzle{4, 3, Tuple{Person, Drink, Pet}} with 7 clues and 1 questions
┌─────────────────────────────────────────┐
│ Person      Dan, Grace, David, Luke     │
├─────────────────────────────────────────┤
│ Drink   tea, orange juice, water, milk  │
├─────────────────────────────────────────┤
│  Pet    cat, ferret, guinea pig, snails │
└─────────────────────────────────────────┘

clues:
1) abs(Pos[Pet("guinea pig")] - Pos[Drink("tea")]) == 1
2) Pos[Drink("water")] == Pos[Person("Luke")] + 2
3) Pos[Pet("cat")] == Pos[Pet("snails")] + 3
4) Drink("tea") ⟹ Person("Dan")
5) Pos[Drink("milk")] > Pos[Person("Dan")]
6) Pos[Drink("milk")] == 2
7) Drink("water") ⟹ ¬Person("David")

questions:
1) Pos[Person("Dan")]?

Solving the Puzzle 🧠

Even if the puzzle has the clues to ensure a unique solution, it is still unsolved.

@assert ZP.issolved(puz_unsolved) == false

To solve an unsolved puzzle, you can call the solve! function.

solve!(puz_unsolved);

This will add the truth table to the puz_unsolved. You can check that it now contains the solution with issolved

@assert ZP.issolved(puz_unsolved) == true

and you can inspect the solution using show_solution

puz_unsolved |> ZebraPuzzles.show_solution

SolvedZebraPuzzle{5, 5, NTuple{5, Union{Missing, ZebraPuzzles.Attribute}}}
┌──────────────────────────────────────────────────────────┐
│    Drink      House   Nationality   Pet        Smoke     │
├──────────────────────────────────────────────────────────┤
│    coffee     ivory    Norwegian   snails    Old Gold    │
├──────────────────────────────────────────────────────────┤
│ orange juice  green   Englishman    fox    Lucky Strike  │
├──────────────────────────────────────────────────────────┤
│     milk       blue    Ukrainian    dog    Chesterfields │
├──────────────────────────────────────────────────────────┤
│    water      yellow   Japanese    zebra       Kools     │
├──────────────────────────────────────────────────────────┤
│     tea        red     Spaniard    horse    Parliaments  │
└──────────────────────────────────────────────────────────┘

Natural Language 📖

If you would like to give the puzzle to someone (person 🤦 or an AI agent 🤖), you probably want to have it in natural language phrasing. You can get this using the function riddle

riddle(puz_unsolved)

There are 5 houses.

  * The person who drinks coffee owns the snails.
  * The man who owns the snails lives in the ivory house.
  * The green house is immediately to the right of the ivory house.
  * The person who smokes Old Gold is the owner of the snails.
  * The man who smokes Kools lives in the yellow house.
  * The person who drinks milk lives in the third house.
  * The Norwegian lives in the first house.
  * The man who smokes Chesterfields lives immediately next to the man who owns the fox.
  * The smoker of Kools lives immediately next to the person who owns the horse.
  * The man who smokes Lucky Strike drinks orange juice.
  * The man who smokes Lucky Strike lives to the right of the man who smokes Old Gold.
  * The smoker of Lucky Strike lives in the second house.
  * The blue house is to the left of the house where the person who owns the zebra lives.
  * The Spaniard does not live in the blue house.
  * The Spaniard lives in the red house.
  * The Japanese owns the zebra.
  * The man who owns the horse lives to the right of the person who owns the zebra.
  * The drinker of orange juice is not a Ukrainian.
  * The drinker of milk lives immediately next to the man who drinks water.