Chromatic Polynomials 09 – Logic Puzzles

4 hours ago
12 min read

In this article, I’ll show you how logic puzzles can be encoded into CPs and solved. This is an application of CPs that I had a lot of fun with.

Logic Puzzle 1

We will start with a simple logic problem, matching 3 travelers to their travel class and seat number:

Fred, Harry, and Morty are all traveling on the same train. The person in seat 95C is happy to not be in third class. Harry was not happy to be in seat 74D. All seats numbered from 1 to 35 are first class. Fred's seat has a larger number.

To encode this as a CP, we will assign a constant value to each name, and a vertex to each seat and class:

Names	Classes	Seat
Fred = 1 Harry = 2 Morty = 3	FirstClass = σ₁ SecondClass = σ₂ ThirdClass = σ₃	Seat34A = σ₆ Seat74D = σ₇ Seat95C = σ₈

Implicit in the puzzle is the constraint the no single person is in two seats or classes. We will represent that with:

UniqueClasses = (1 - δ FirstClass SecondClass) (1 - δ FirstClass ThirdClass) (1 - δ SecondClass ThirdClass)

UniqueSeats = (1 - δ Seat34A Seat74D) (1 - δ Seat34A Seat95C) (1 - δ Seat74D Seat95C)

Then we encode the hints as terms in the CP:

“The person in seat 95C is happy to not be in third class.”

Constraint1 = (1 - δ Seat95C ThirdClass)

“Harry was not happy to be in seat 74D.”

Constraint2 = δ Seat74D {Harry}

“All seats numbered from 1 to 35 are in first class.”

Constraint3 = δ Seat34A FirstClass

“Fred’s seat has a larger number (than 35).”

Constraint4 = (1 - δ Seat34A {Fred})

The full CP is the product of all these terms:

PuzzleCP = UniqueClasses UniqueSeats Constraint1 Constraint2 Constraint3 * Constraint4

When I write scripts for my CP engine, I prefer say-what-you-mean names like "Fred" for 1 and "Firstclass" for σ₁. When those aliases are stripped, the formula looks like this:

The number of solutions is found by summing over the 6 vertices.

This puzzle has only one solution, so it is a well-formed puzzle.

Finding Solutions

Summing a CP over all its vertices tells us how many solutions there are. It doesn’t tell us what the solutions are. To find the solutions, we use the Solving function of CPs. Once a full solution has been found, we can stop the process at one solution or use the Iterating function to find all solutions.

For this logic puzzle, since there is only one solution, this is how we would search for a value for σ₁:

This shows us that σ₁ = 3, or “Morty traveled first class”, is part of the solution. Note that assigning a specific value to a vertex associates a class or seat with a name. Repeating the process for the other vertices gives us the full solution:

Fred = Second Class = Seat 95C

Harry = Third Class = Seat 74D

Morty = First Class = Seat 34A

For reference, here is the script I used to solve this logic puzzle with my CP Engine:

// Constants
Fred  = 1;
Harry = 2;
Morty = 3;

// Variables
FirstClass  = s1;
SecondClass = s2;
ThirdClass  = s3;
Seat34A = s4;
Seat74D = s5;
Seat95C = s6;

// Each person only gets one class and one seat.
UniqueClasses = (1 - d FirstClass SecondClass)  (1 - d FirstClass ThirdClass)  (1 - d SecondClass ThirdClass);
UniqueSeats = (1 - d Seat34A Seat74D)  (1 - d Seat34A Seat95C)  (1 - d Seat74D Seat95C);

// Translating hints to constraints:
Constraint1 = (1 - d Seat95C ThirdClass); // The person in seat 95C is happy to not be in third class.
Constraint2 = d Seat74D {Harry};          // Harry was not happy to be in seat 74D.
Constraint3 = d Seat34A FirstClass;       // All seats numbered from 1 to 35 are first class.
Constraint4 = (1 - d Seat34A {Fred});        // Fred's seat has a larger number.

Formula = GetExpression(UniqueClasses  UniqueSeats  Constraint1  Constraint2  Constraint3 * Constraint4);
 
Print "Formula =" Formula;
Print;
Solutions = SumOver(Formula, σ1-σ6, 3);
Print "Solutions =" Solutions;
Print;

Solve(Formula, σ1-σ6, 3);

Logic Puzzle 2

Here is a more complicated logic problem, matching 5 names to 5 family relationships, 5 sports, and 5 movies:

A family consists of a mother, a father, a daughter, and two sons. Their names are Alex, David, Diane, Maria, and Sean. They are each watching a sports game while recording an Alfred Hitchcock movie to watch later.

A man recorded Suspicion. The woman who watched a hockey game isn't the person who recorded Notorious. One of the sons recorded Sabotage while he watched basketball. Either Maria or Alex is the one who watched bowling. Sean is older than Alex but younger than David. Sean didn't record a movie whose title has the initial S. One person watched table tennis while recording The Birds. The one who recorded Rebecca is not the daughter.

What is each person’s relationship in the family, what sport did each one watch, and what movie did each one record?

To encode this as a CP, we will assign a constant value to each name, and a vertex to each family relationship, sport, and movie. The solution will assign a value to each vertex, matching each relationship, sport, and movie to a specific name.

Names	Relationships	Sports	Movies
Alex = 1 David = 2 Diane = 3 Maria = 4 Sean = 5	Daughter = σ₁ Father = σ₂ Mother = σ₃ OlderSon = σ₄ YoungerSon = σ₅	Basketball = σ₆ Bowling = σ₇ Football = σ₈ Hockey = σ₉ TableTennis = σ₁₀	TheBirds = σ₁₁ Notorious = σ₁₂ Rebecca = σ₁₃ Sabotage = σ₁₄ Suspicion = σ₁₅

Implicit in the puzzle is the requirement that each member of the Relations, Sports, and Movies categories must be unique. For example, two different relationships cannot be assigned to the same name. This will need to be encoded in the CP:

UniqueRelationships = (1 - δDaughter Father) (1 - δDaughter Mother) (1 - δDaughter OlderSon) (1 - δDaughter YoungerSon) (1 - δFather Mother) (1 - δFather OlderSon) (1 - δFather YoungerSon) (1 - δMother OlderSon) (1 - δMother YoungerSon) * (1 - δOlderSon YoungerSon)

UniqueSports = (1 - δBasketball Bowling) (1 - δBasketball Football) (1 - δBasketball Hockey) (1 - δBasketball TableTennis) (1 - δBowling Football) (1 - δBowling Hockey) (1 - δBowling TableTennis) (1 - δFootball Hockey) (1 - δFootball TableTennis) * (1 - δHockey TableTennis)

UniqueMovies = (1 - δTheBirds Notorious) (1 - δTheBirds Rebecca) (1 - δTheBirds Sabotage) (1 - δTheBirds Suspicion) (1 - δNotorious Rebecca) (1 - δNotorious Sabotage) (1 - δNotorious Suspicion) (1 - δRebecca Sabotage) (1 - δRebecca Suspicion) * (1 - δSabotage Suspicion)

We take each constraint given in the hints and encode it as a term in the CP:

“A man recorded Suspicion”

Constraint1 = δ Suspicion {Alex,David,Sean}

“The woman who watched a hockey game…”

Constraint2 = δ Hockey {Diane,Maria}

“…isn’t the person who recorded Notorious”

Constraint3 = (1 – δ Hockey Notorious)

“One of the sons recorded Sabotage…”

Constraint4 = (δ Sabotage OlderSon + δ Sabotage YoungerSon)

“… while he watched basketball”

Constraint5 = δ Sabotage Basketball

"Either Maria or Alex is the one who watched bowling.”

Constraint6 = δ Bowling {Maria,Alex}

“Sean is older…”

Constraint7 = δ OlderSon {Sean}

“…than Alex, but younger …”

Constraint8 = δ YoungerSon {Alex}

“…than David.”

Constraint9 = δ Father {David}

“Sean didn’t record a movie whose title has the initial S.”

Constraint10 = (1 – δ Sabotage {Sean}) * (1 – δ Suspicion {Sean})

“One person watched table tennis while recording The Birds.”

Constraint11 = δ TableTennis TheBirds

“The one who recorded Rebecca is not the Daughter.”

Constraint12 = (1 – δ Rebecca Daughter)

The final CP is the product of these terms:

PuzzleCP = UniqueRelationships UniqueSports UniqueMovies Constraint1 Constraint2 Constraint3 Constraint4 Constraint5 Constraint6 Constraint7 Constraint8 Constraint9 Constraint10 Constraint11 Constraint12

Once the aliases are stripped, the formula looks like this:

The number of solutions is found by summing over the 15 vertices.

Searching for the solution gives us these values:

Alex = Younger Son = Basketball = Sabotage

David = Father = Football = Suspicion

Diane = Mother = Hockey = Rebecc

Maria = Daughter = Bowling = Notorious

Sean = Older Son = Table Tennis = The Birds

Logic Puzzle 3

Here is a third logic puzzle, very similar to the previous one:

Five people go to a fortune teller. The fortune teller uses their astrological sign to tell them their lucky color and tell them their fortune.

Either Justin or the Aries was promised a raise, and the other one's lucky color is gold. The one whose lucky color is gold isn't the one whose fortune is to fall in love. Either the Taurus or the person whose lucky color is plum is Rowena, and the other will fall in love. The one who will fall in love isn't Frank. Either the person who will take a trip to a faraway land or the one whose lucky color is teal is the Scorpio, and the other is Nelson (who isn't the Taurus). Either Cindy or the man who should expect to receive a gift is the one whose lucky color is violet, and the other is the Pisces. Frank isn't the Pisces. Frank (whose lucky color is indigo) is neither the one promised the trip nor the Gemini. The Gemini, whose lucky color isn't gold, should expect a new job opportunity.

Before reading any further, I encourage you to try to translate some of the hints into CPs yourself.

Here is how I translated it:

Names	Signs	Fortunes	Lucky Colors
Cindy (F) = 1 Justina (F) = 2 Rowena (F) = 3 Frank (M) = 4 Nelson (M) = 5	Aries = σ₁ Gemini = σ₂ Pisces = σ₃ Scorpio = σ₄ Taurus = σ₅	Gift = σ₆ Job = σ₇ Love = σ₈ Raise = σ₉ Trip = σ₁₀	Gold = σ₁₁ Indigo = σ₁₂ Plum = σ₁₃ Teal = σ₁₄ Violet = σ₁₅

UniqueSigns = (1 - δ Aries Gemini) (1 - δ Aries Pisces) (1 - δ Aries Scorpio) (1 - δ Aries Taurus) (1 - δ Gemini Pisces) (1 - δ Gemini Scorpio) (1 - δ Gemini Taurus) (1 - δ Pisces Scorpio) (1 - δ Pisces Taurus) * (1 - δ Scorpio Taurus)

UniqueFortunes = (1 - δ Gift Job) (1 - δ Gift Love) (1 - δ Gift Raise) (1 - δ Gift Trip) (1 - δ Job Love) (1 - δ Job Raise) (1 - δ Job Trip) (1 - δ Love Raise) (1 - δ Love Trip) * (1 - δ Raise Trip)

UniqueColors = (1 - δ Gold Indigo) (1 - δ Gold Plum) (1 - δ Gold Teal) (1 - δ Gold Violet) (1 - δ Indigo Plum) (1 - δ Indigo Teal) (1 - δ Indigo Violet) (1 - δ Plum Teal) (1 - δ Plum Violet) * (1 - δ Teal Violet);

“Either Justina or the Aries …”

Constraint1 = δ Aries {Cindy, Rowena, Frank, Nelson}

“… was promised a raise …”

Constraint2 = (d Raise {Justina} + δ Aries Raise)

“… and the other one’s …”

Constraint3 = (1 - δ Raise Gold)

“… lucky color is gold.”

Constraint4 = (d Gold {Justina} + δ Aries Gold

“The one whose lucky color is gold isn’t the one whose fortune is to fall in love.”

Constraint5 = (1 - δ Gold Love)

“Either the Taurus or the person whose lucky color is plum …”

Constraint6 = (1 - δ Taurus Plum)

“… is Rowena, …”

Constraint7 = (d Taurus {Rowena} + δ Plum {Rowena})

“… and the other …”

Constraint8 = δ Love {Cindy, Justina, Frank, Nelson)

“… will fall in love …”

Constraint9 = (d Taurus Love + δ Plum Love)

“The one who will fall in love isn’t Frank.”

Constraint10 = δ Love {Cindy, Justina, Rowena, Nelson}

“Either the person who will take a trip to a faraway land or the one whose lucky color is teal …”

Constraint11 = (1 - δ Trip Teal)

“… is the Scorpio …”

Constraint12 = (d Trip Scorpio + δ Teal Scorpio)

“… and the other …”

Constraint13 = δ Scorpio {Cindy, Justina, Rowena, Frank}

“… is Nelson …”

Constraint14 = (d Trip {Nelson} + δ Teal {Nelson})

“… (who isn’t the Taurus).”

Constraint15 = δ Taurus {Cindy, Justina, Rowena, Frank}

“Either the man who should expect to receive a gift …”

Constraint16 = δ Gift {Frank, Nelson}

“… or Cindy is the one whose lucky color is violet, …”

Constraint17 = δ Violet {Cindy, Frank, Nelson}

“… and the other …”

Constraint18 = (1 - δ Violet Pisces)

“… is the Pisces.”

Constraint19 = δ Pisces {Cindy, Frank, Nelson}

“Frank isn’t the Pisces.”

Constraint19a = (1 - δ Pisces {Frank})

Note that after this, Constraint 19a can be reduced to δ Pisces {Cindy, Nelson}.

“Frank (whose lucky color is Indigo) …”

Constraint20 = δ Indigo {Frank}

“… is neither the one promised the trip …”

Constraint21 = δ Trip {Cindy, Justina, Rowena, Nelson}

“… nor the Gemini.”

Constraint22 = δ Gemini {Cindy, Justina, Rowena, Nelson}

“The Gemini, whose lucky color isn’t Gold, …”

Constraint23 = (1 - δ Gemini Gold)

“… should expect a new job opportunity.”

Constraint24 = δ Gemini Job

As with the previous examples, all the constraints are multiplied together to produce a CP expression representing the puzzle. Solving this expression yields:

Frank = Aries = Raise = Indigo

Rowena = Gemini = Job = Plum

Nelson = Pisces = Gift = Teal

Justina = Scorpio = Trip = Gold

Cindy = Taurus = Love = Violet

Inclusive vs Exclusive Constraints

Constraint 1 was encoded as an inclusive requirement, stating that “Aries can take any of these values”, where the values list everyone except Justina:

Constraint1 = δ Aries {Cindy, Rowena, Frank, Nelson}

This could also have been encoded as an exclusive requirement, stating that Aries cannot be Justina:

Constraint1 = (1 - δ Aries {Justina})

In general, inclusive terms are faster to evaluate than exclusive terms, by the simple fact that expanding them does not produce more terms. I will illustrate this in more detail in later articles.

Redundant Constraints

Given Constraint 19, Constraint 19a is redundant:

Constraint19 = δ Pisces {Cindy, Nelson}

Constraint19a = (1 - δ Pisces {Frank})

We can see this just by translating them to English:

Constraint19 = The Pisces is either Cindy or Nelson.

Constraint19a = The Pisces is not Frank.

We can also see this by multiplying the two constraints:

δ Pisces {Cindy, Nelson} * (1 - δ Pisces {Frank})

δ Pisces {Cindy, Nelson} - δ Pisces {Cindy, Nelson} * δ Pisces {Frank}

By our rules for multiplying Extended Kronecker Deltas, if two EKDs have a variable common, the product will contain the union of the sets of variables and the intersection of the sets of constants.

δ Pisces {Cindy, Nelson} - δ Pisces {Cindy, Nelson}∩{Frank}

δ Pisces {Cindy, Nelson} - δ Pisces {}

If a variable can only be equal to the empty set of constants, then the EKD reduces to 0.

δ Pisces {Cindy, Nelson} - 0

δ Pisces {Cindy, Nelson}

We see that multiplying constraints 19 and 19a completely eliminates 19a.

Minimizing Constraints

If constraint 19a can be removed, can other constraints also be removed? To test it, I removed one constraint at a time. If removing a constraint still results in one solution, then that constraint isn’t necessary. If removing the constraint results in more than one solution, then that constraint is required for the puzzle to be well-formed.

I found that the following could be removed:

“Either Justina or the Aries …”

Constraint1 = δ Aries{Cindy,Rowena,Frank,Nelson}

“… and the other one’s …”

Constraint3 = (1 - δ Raise Gold

“Either the Taurus or the person whose lucky color is plum …”

Constraint6 = (1 - δ Taurus Plum)

“… is Rowena, …”

Constraint7 = (d Taurus {Rowena} + δ Plum {Rowena})

“Either the person who will take a trip to a faraway land or the one whose lucky color is teal …”

Constraint11 = (1 - δ Trip Teal)

“… (who isn’t the Taurus).”

Constraint15 = δ Taurus {Cindy,Justina,Rowena,Frank}

“Either the man who should expect to receive a gift …”

Constraint16 = δ Gift {Frank, Nelson}

There may be more than one set of removable constraints

This isn’t necessarily the only set of constraints that could be removed. I found this set through trial and error – try to remove a constraint. If it was removable, I left it out and moved on to the next constraint. It may be that a more exhaustive search would find a larger set that could be removed.

Solvability is not Difficulty

After removing all these constraints, the puzzle still has only one solution. I haven’t tried solving these puzzles by hand, but I’m sure that removing hints can only make the puzzle harder for a person to solve. This gives us a little insight into what CPs can tell us about a puzzle: The CP can only tell if it’s solvable and produce a solution. It does not tell us how hard the puzzle is to solve through traditional methods.

Building Puzzles with CPs

Finally, we can also use this technique to create a logic puzzle – we can create some constraints and see how many solutions there are. If there is more than one solution, we must add more constraints and check again. When more constraints are needed, we could list all the current solutions to help us see where a constraint would be helpful in eliminating solutions. We continue the process until there is only one solution.

CPs are bad at order

I saw one logic puzzle where 5 people lived in 5 different houses on a street. The hints included statements like this:

The man who smokes Chesterfields lives in the house next to the man with the fox.

The concept of order, adjacency, or “next to” does not exist in CPs. An EKD can only test for equality or inequality. It cannot tell if a variable is greater than a value or equal to “a value plus one”. This is why it’s better to think of the constants in a CP as unordered members of a set, not as actual numbers.

For that puzzle, we would have to check for every possible meaning of “next to” (this assumes the houses are numbered 1 – 5, sequentially):

OrderedConstraint = (δ Chesterfields{1} δ Fox{2} + δ Chesterfields{2} δ Fox{1,3} +

δ Chesterfields{3} δ Fox{2,4} + δ Chesterfields{4} δ Fox{3,5} + δ Chesterfields{5} δ Fox{4});

This shows that CPs can be used to create logic puzzles, solve them, and evaluate them for soundness. I found logic puzzles to be a beautiful showcase for CPs as a language of logic.

Previous Post: