Thursday, December 7, 2017

Constructing Portia's Caskets

In Shakespeare's The Merchant of Venice, Portia tested her suitors by asking them to discover which of three caskets concealed her portrait. Inscriptions on the caskets presented riddles that would challenge the virtue of her potential mates. In his classic What is the Name of this Book? logician Raymond Smullyan, imagined several generations of clever Portias, who presented potential suitors with caskets inscribed with logic puzzles that provided the key to finding her hidden portrait.

On this page I have set up interactive puzzle generators that correspond (roughly) to Smullyan’s first three generations of Portias. In this post I thought I would describe what I find interesting about the way the puzzles are solved and  how they are generated. The code that generates and presents these puzzles is found here.

Here's the first Portia's Caskets puzzle in "What is the Name of this Book?":

One way to solve problems like this is to work backwards. For each casket, imagine that the portrait is concealed within that casket, then count how many statements would be true. When you find the portrait placement that matches the requirement that "at most one is true" you have your solution.

Building our first 348 Portia Puzzles

Working backwards also gives us a way to generate puzzles like this one. To generate these puzzles, consider all possible statements on the caskets. Each set of statements gives you three possible puzzles: a puzzle where the portrait is in the gold casket, a puzzle where the portrait is in the silver casket, and a puzzle where it is in the lead casket. To find out if any (or all) of these are valid solvable puzzles, check to see if the portrait placement gives you a 'truth count' that unique within that group of potential puzzles.

But what about generating 'all possible statements'? What are the statements that can be included? The statements on the caskets can be thought of as pointers to caskets, pointers that are either positive ("the portrait is in the silver casket") or negative ("the portrait is not in the gold casket"), and that may be directed at the current casket itself ("the portrait is in this casket").

For three caskets, this can be represented as an array of three integers. For example the statements for the puzzle above would be represented as [1, -2, -1], the 1 in the first position is saying that the first casket is pointing positively to itself ("the portrait is in this casket"). The -2 in the second position is saying  that the second casket is pointing negatively to itself ("the portrait is not in this casket"), and the -1 in the third position is saying that the third casket is pointing negatively at the first casket ("the portrait is not in the gold casket"). We can analyse this puzzle using a chart like the one below:

For the puzzle that says "there is at most one true statement," this means that the portrait is in casket 2 (silver), the only placement which gives at most one true statement. The chart also tells us that we cannot use this statement arrangement to make up other puzzles like "there are no true statements" or "there are exactly two true statements," as the other casket positions (p=1, p=3) both make two statements true.

So, generating this sort of Portia Casket problem is easy: first generate all lists of length three (for the three caskets) made up of the values -1, -2, -3, 1, 2, 3 (for positive and negative statements about the three caskets). Each of these lists gives a family of three possible puzzles - one for the portrait being in each casket. Check each possible solution to see how many statements become true with that solution. Any solution that gives a truth count that is unique in that family corresponds to a valid puzzle.

For three caskets, following this method of generating puzzles, we get a total of 348 puzzles. Some of these are trivially easy, as in the case where the clue is "all statements are true" and one of the caskets says "the portrait is in here."

Smullyan's first Portia puzzle, puzzle 67a, corresponds to the puzzle with identifier portia1-44 in our Portia I generator. Smullyan presents another puzzle by the first generation of Portias, puzzle 67b. This puzzle has statements [-2, -2, 3], and corresponds to portia1-271 in the Portia I generator.

All the Portia I puzzles are listed in this json file. Here is an example of one from the page:

Hopefully, you can see that we would represent the statements as [-1, -2, 2] and that the solution to this puzzle would have to be casket 1.

Finding 16152 more!

In "What is the Name of this Book?" a second generation Portia makes more difficult puzzles by putting two statements on each casket. Our Portia II generator is based on Smullyan's puzzle 68b.

It seems clear that these puzzles are very similar to the Portia I puzzles except: (1) there are two lists of statements, and (2) instead of giving a total count of the true statements, we describe the distribution ("on one lid both statements are true, on another both statements were false, and on a third one statement was true and one false").

If we model the statements as two lists of integers, such as [-1, -1, -3], [2 ,3, 1] for the above, and then for each pair of lists include puzzles where a portrait position generates a unique distribution, we can create puzzles like this one. It makes sense to exclude statement lists where the second set of statements is the same as the first, and to consider puzzles the same if we just exchange the first list of statements with the second list.

Following this approach we get a large number (16152) of puzzles (all of them are here). These are generally quite a bit trickier to solve than Portia I puzzles, although the method for solving them is essentially the same. Puzzle 68b above corresponds to portia2-6854, although the Portia II algorithm we used swaps the first statement list for the second (it generates as  [2 ,3, 1],  [-1, -1, -3]).

Here's an example of a generated puzzle:

For this particular puzzle we don't have to work backwards, we can take a direct approach aided by the contradictory statements on casket 2: We know this must be the one casket with one true statement. Since the statements on casket 1 cannot both be true, we know that this must be the casket with no true statements. This implies that casket 3 is the casket with two true statements. One of the statements on casket 3 says the portrait is in casket 2... so that is where it must be.

Bellini and Cellini give us 3600 more puzzles

Instead of telling us how many of the caskets have true statements, or how true statements are distributed across the caskets, what if solving another riddle was the key to figuring out which statements are true and which are false?

When attempting to generate "Bellini and Cellini" puzzles, I decided on an approach that does not quite match up with any of the puzzles in "What is the Name of this Book," but is a combination of Portia I, Portia II, and the "Knights and Knaves" puzzles that Smullyan describes in an earlier chapter (see this post).

For Portia III, we imagine that the caskets have inscriptions similar to Portia I, but also have an extra inscription that says something about the provenance of the caskets. For example, casket 1 might have an inscription "casket 2 was made by Bellini." You might think "great, that means that whatever is written on casket 2 must be true." Well, that is correct only if casket 1 was also made by Bellini, if it was made by Cellini, then whatever is written on casket 2 is actually false.

So, our Portia III algorithm is actually a set of Portia I statements with a "three-islander Knights and Knaves puzzle" layered on top of it. You can learn more about these here. For simplicity, a specific kind of "three islander" problem was chosen: the three caskets (islanders) point at each other using 2 "accusation/affirmations" and one "similarity/difference" statement. These are always (pretty easily) solvable. Maybe a future Portia puzzle generator will involve different varieties of Bellini & Cellini statements.

All the Portia III puzzles that the current algorithm generates are listed in this json file. Let's try one:

Casket 2 includes the inscription "Fashioned by a different maker than 1." If casket 2 is made by Bellini, this means that casket 1 is made by Cellini, since we can trust casket  2 in this case. If on the other hand, casket 2 is made by Cellini, then we should disbelieve the statement, and conclude that casket 1 is made by the same maker (Cellini). Hence, regardless of who made casket 2, we know that casket 1 is made by Cellini, and its inscriptions will be false. Now casket 1 makes the (false) assertion that casket 3 is made by Cellini - so we know that actually casket 3 is made by Bellini and must contain only true inscriptions. Casket 3 says that the portrait is in casket 2, so we believe it:

Working backwards is not the approach to take with Portia III: these puzzles require you to first solve the Bellini/Cellini riddle and figure out which caskets are stating the truth, and which are lying. Next you can use this information to follow the true (or false) statements to the portrait.

When generating these puzzles, the method is to first generate all possible Portia I statements. For a given set of statements, each possible solution (casket 1, casket 2, or casket 3) makes each statement either true or false. To verify if the puzzle is solvable, we need to check whether the portrait can be discovered once the truth or falsehood of each statement is known. There is a simple rule for this: if p is the position of the portrait, then either we need a statement with value +/-p or we need a statement for each of the remaining caskets. An example of a puzzle that does not work would be [1, 1, 1] where p = 2. The three caskets would all be lying (they would all be saying the portrait was in casket 1), but there would not be enough information to tell us if the portrait was in casket 2 or 3. The same statement list, [1,1,1] is a valid puzzle if p = 1. Once we have a solvable puzzle, we can overlay a few different Bellini & Cellini riddles that would say which caskets are lying and which are stating truths.

So, all told, these three Portias have given us 20100 puzzles, enough to keep us busy for a while. I had a lot of fun digging into them, and I hope you have fun with them as well - please try them out: 

Thus hath the candle singed the moth.
O, these deliberate fools! when they do choose,
They have the wisdom by their wit to lose. 
- Act II, Scene VII, The Merchant of Venice