This assignment covers the following topics:
Complete all sections. Some questions will require written answers, while others will involve coding. Be sure to run your code cells to verify your solutions.
One could view the clues given in logic puzzles, like a murder mystery, as constraints in a constraint satisfaction problem (CSP).
For example if the clue were to be "The Revolver was not in the Kitchen or the Ballroom" we can turn this into constraints. If the Revolver were to be the murder weapon then the room of the murder could not be the Kitchen or the Ballroom. Conversely, if the murder room was found to be the Kitchen or the Ballroom then the murder weapon could not be the revolver.
Given below are a series of clues and some starter code, your job as the lead detective in this case is to turn the clues into a series of "constraint functions" (the first has been given as a reference implementation) and then write the basic backtracking algorithm to help solve the murder! Good luck detective, we're counting on you.
To discover who killed Mr. Boddy, you need to learn where each person was, and what weapon was in the room. Clues are scattered throughout the quiz.
To begin, you need to know the suspects. There are three men (George, John, Robert) and three women (Barbara, Christine, Yolanda). Each person was in a different room (Bathroom, Dining Room, Kitchen, Living Room, Pantry, Study). A suspected weapon was found in each room (Bag, Firearm, Gas, Knife, Poison, Rope).
The man in the kitchen was not found with the rope, knife, or bag. Which weapon, then, which was not the firearm, was found in the kitchen?
Barbara was either in the study or the bathroom; Yolanda was in the other. Which room was Barbara found in?
The person with the bag, who was not Barbara nor George, was not in the bathroom nor the dining room. Who had the bag in the room with them?
The woman with the rope was found in the study. Who had the rope?
The weapon in the living room was found with either John or George. What weapon was in the living room?
The knife was not in the dining room. So where was the knife?
Yolanda was not with the weapon found in the study nor the pantry. What weapon was found with Yolanda?
The firearm was in the room with George. In which room was the firearm found?
It was discovered that Mr. Boddy was gassed in the pantry. The suspect found in that room was the murderer. Who, then, do you point the finger towards?
# Define variables
people = ["George", "John", "Robert", "Barbara", "Christine", "Yolanda"]
rooms = ["Bathroom", "Dining Room", "Kitchen", "Living Room", "Pantry", "Study"]
weapons = ["Bag", "Firearm", "Gas", "Knife", "Poison", "Rope"]
# Set of all assignments
assignments = []
# Clues as constraints
def is_valid(assignment):
"""
Check if the current assignment satisfies all clues.
"""
if len(assignment) < 6:
return True
# Extract assignments for people, rooms, and weapons
person_to_room = {person: room for person, room, weapon in assignment}
person_to_weapon = {person: weapon for person, room, weapon in assignment}
room_to_weapon = {room: weapon for person, room, weapon in assignment}
# Clue 1: The man in the kitchen was not found with the rope, knife, or bag.
# Which weapon, then, which was not the firearm, was found in the kitchen?
if person_to_room.get("George", "") == "Kitchen" or \
person_to_room.get("John", "") == "Kitchen" or \
person_to_room.get("Robert", "") == "Kitchen":
kitchen_weapon = room_to_weapon.get("Kitchen", "")
if kitchen_weapon in ["Rope", "Knife", "Bag", "Firearm"]:
return False
# TODO
# Fill out the remaining clues as constraints much like Clue 1 above, most clues will only take a couple lines
# 2 points
# Clue 2: Barbara was either in the study or the bathroom; Yolanda was in the other.
# Clue 3: The person with the bag, who was not Barbara nor George, was not in the bathroom nor the dining room.
# Clue 4: The woman with the rope was found in the study.
# Clue 5: The weapon in the living room was found with either John or George.
# Clue 6: The knife was not in the dining room.
# Clue 7: Yolanda was not with the weapon found in the study nor the pantry.
# Clue 8: The firearm was in the room with George.
# Final clue: Mr. Boddy was gassed in the pantry, and the suspect found in that room is the murderer.
return True
# Backtracking algorithm
def backtrack(assignment):
"""
Perform backtracking to solve the puzzle.
"""
if len(assignment) == 6:
return assignment
# Get the next unassigned person
for person in people:
if person not in [p for p, r, w in assignment]:
break
# Try all rooms and weapons
for room in rooms:
pass
# TODO
# Write the backtracking algorithm for solving CSPs similar to the example code on the slides
# My implementation was about 8 lines
# 5 points
return None
# Find the solution
solution = backtrack(assignments)
# Print the solution
if solution:
print("Solution found:")
for person, room, weapon in solution:
print(f"{person} was in the {room} with the {weapon}")
else:
print("No solution found.")
Symbolic reasoning involves using symbols to represent concepts and relationships, while knowledge representation focuses on encoding information about the world in a form that a computer system can utilize to solve complex tasks.
Which of the following is NOT a form of knowledge representation? (1 pt.)
Symbolic Reasoning with Emojis:
Consider the following symbolic representation of a relationship between emojis:
1. 🍎 → 🍏 (If it’s an apple, then it’s a green apple.)
2. 🍏 → 🍐 (If it’s a green apple, then it’s a pear.)
3. 🍐 → 🍇 (If it’s a pear, then it’s a grape.)
Given the above relationships, answer the following questions:
a) What can you conclude if you know that you have an apple (🍎)?
b) If you have a grape (🍇), what can you infer about whether you have an apple (🍎)? Explain your reasoning.
c) If 🍎 is False, what can you say about 🍇?
Symbolic Reasoning in the real world
Watson for Healthcare applies symbolic reasoning in the context of medical diagnostics and treatment recommendations. The system is designed to assist doctors by analyzing vast amounts of medical literature, patient records, and clinical guidelines to provide evidence-based treatment options.
Here’s how symbolic reasoning is used in Watson:
1. Knowledge Representation: Watson encodes medical knowledge in a structured, symbolic form, representing relationships between diseases, symptoms, treatments, and outcomes. For example, it might encode that if a patient has symptom X and test result Y, then disease Z is a possible diagnosis.
2. Logical Inference: Given a set of patient symptoms and test results, Watson uses symbolic reasoning to infer possible diagnoses by applying rules and relationships from its knowledge base. It reasons through chains of implications, much like the emoji example, to determine which diseases are most likely based on the provided data.
3. Explainability: One of the key advantages of using symbolic reasoning in Watson is its ability to provide clear explanations for its recommendations. It can trace the logical steps it took to arrive at a particular diagnosis or treatment, which is crucial for gaining the trust of medical professionals.