Saturday, September 15, 2018

Solving (some) Logic Puzzles with Sets

As you may have noticed, since around this time last year, I have been playing around with generating puzzles based on those found in some of Raymond Smullyan's books. This has included Knights and Knaves, Portia's Caskets, The Case Files of Inspector Craig, Tigers and Treasure, and The Isle of Dreams. Some of the differences between puzzles are superficial: A "Portia's Casket" puzzle can be recast as a "Knights and Knaves" puzzle, for example. Even though there is some common deep structure to these various puzzles, I've found that sometimes the puzzle types call out for different approaches when writing solvers or generators.

The latest puzzle type that I have been enjoying is based on some puzzles found in Smullyan's What is the Name of This Book?. The "Lion and the Unicorn" puzzles are built around characters from Lewis Carroll's Through the Looking-Glass, and What Alice Found Thereand for this logic puzzle variation, I found that using sets to model the puzzle (rather than, say, propositions, truth tables, or graphs) seemed to make the most sense.

The Lion and the Unicorn, posing
at the East Block 

As described in the chapter 47 Alice and the Forest of Forgetfulness,
When Alice entered the Forest of Forgetfulness, she did not forget everything, only certain things. She often forgot her name, and the one thing she was most likely to forget was the day of the week. Now, the Lion and the Unicorn were frequent visitors to the forest. These two are strange creatures. The Lion lies on Mondays, Tuesdays, and Wednesdays, and tells the truth on the other days of the week. The Unicorn, on the other hand, lies on Thursdays, Fridays, and Saturdays, but tells the truth on other days of the week.
One day, Alice met the Lion and the Unicorn resting under a tree. They made the following statements: 
Lion: Yesterday was one of my lying days. 
Unicorn: Yesterday was one of my lying days too.
Alice must know: What day is today? 
If you think you have a solution to this - test it out on the interactive version of the puzzle.

If we model this using sets, our universe of discourse for this problem is the days of the week.
$$ \begin{split} Days =& \{\textrm{Monday, Tuesday, Wednesday,} \\ & \textrm{Thursday, Friday, Saturday, Sunday} \} \end{split} $$ We consider the set L of days for which the lion is lying, and the set U of days for which the unicorn is lying.
$$ \begin{split} L =& \{ \textrm{Monday, Tuesday, Wednesday}\} \\ U =& \{ \textrm{Thursday, Friday, Saturday}\} \end{split} $$
The days that the animals are telling the truth are listed in the complements of each set.
$$ \begin{split} \overline{L} =&\{ \textrm{Thursday, Friday, Saturday, Sunday}\} \\ \overline{U} =& \{ \textrm{Sunday, Monday, Tuesday, Wednesday}\} \end{split} $$ These two sets have an empty intersection - the two characters never lie at the same time. The intersection of their truth-telling days is non empty, however: both tell the truth on the same day once a week.
$$ \begin{split} L \cap U =& \emptyset \\ \overline{L} \cap \overline{U} =& \{ \textrm{Sunday} \} \end{split} $$ The set Days is a set with structure, the days are an ordered set - the lion and the unicorn can talk about 'yesterday' and 'tomorrow.' For any set of days we can ask for its 'tomorrows' - the set of next days, or its set of 'yesterdays', the set of preceding days. When the lion says "I told lies yesterday" this can be translated as "today is a tomorrow for one of my lying days." The set of days covered by Lion's statement would be:
$$ S_L = t(L) = \{ \textrm{Tuesday, Wednesday, Thursday}\} $$ But do any of the days covered by Lion's statement coincide with a day that he is telling the truth? To believe his statement about what day it is, it must describe a day that he is actually speaking truthfully. If Lion is telling the truth, it must be a day in the intersection of the days in Lion's statement and the set of Lion's truthful days.
$$S_L \cap \overline{L} = \{ \textrm{Thursday}\}$$ But, Lion could be lying. If Lion is lying, then today is in the intersection of the days not in Lion's statement, and Lion's lying days.
$$\overline{S_L} \cap L = \{ \textrm{Monday} \}$$ Since we don't know whether the lion is telling the truth or lying, we have to consider both possibilities, so the set of days that it could be, based only on Lion's statement is: $$ \begin{split} D_L &= ( S_L \cap \overline{L} ) \cup ( \overline{S_L} \cap L ) \\ &= \{ \textrm{Monday, Thursday} \} \end{split} $$ Going through a similar process, we can get another set of days based on the Unicorn's statements.
$$ \begin{split} D_U &= ( S_U \cap \overline{U} ) \cup ( \overline{S_U} \cap U ) \\ &= \{ \textrm{Sunday, Thursday} \} \end{split} $$ Days that fall in both the set from the Lion and the set from the Unicorn are possible solutions for today's day - if the intersection is empty, then there is no solution, if there are several days in the intersection, then the puzzle is ambiguous, if there is a single day in the intersection, that is today:
$$ \begin{split} D &= D_L \cap D_U \\ &= [ (S_L \cap \overline{L} ) \cup ( \overline{S_L} \cap L)] \cap [ (S_U \cap \overline{U} ) \cup ( \overline{S_U} \cap U)] \\ &= \{ \textrm{Thursday} \} \end{split} $$ The notation might make this way of thinking seem difficult - here is the process stated a bit more plainly (see that it lines up with the formula above...):

1. Consider the Lion. Which days does the Lion's statement refer to?
2. Of these days, which coincide with Lion's truthful days?
3. Which of the days are not covered by the Lion's statement? Do any of these coincide with Lion's lying days?
4. Combine these two lists of days from the Lion.
5. Follow steps 1 through 4 for the Unicorn to produce a list of possible days from the Unicorn.
6. If there is one day that that is in both the Lion's list and the Unicorn's list, that is the solution.

We can come up with variations on this puzzle by varying the statements made by the Lion and the Unicorn. Instead of saying "I told lies yesterday," we could have them say things like "I will tell truths tomorrow" or "today is a week day", or even "today is Wednesday." Some of these will generate good puzzles (one element in the final set), others may not.

A Jupyter notebook that generates 132 puzzles like this can be found here, and you can the puzzles out over here.