Jindosh Riddle as a Constraint Satisfaction Problem

Jindosh Riddle as a Constraint Satisfaction Problem.md

Jindosh Riddle as a Constraint Satisfaction Problem

In Dishonored 2 players encounter a version of the Zebra Puzzle that opens up a shortcut. These riddles are generated for each player so there isn't a single solution. Instead this script formulates them as a constraint satisfaction problem that is solved automatically.

jindosh_constraint.py

from constraint import Problem, AllDifferentConstraint # https://pypi.org/project/python-constraint/
from typing import Callable

# The Jindosh Riddle is randomly generated.
# This is the solution for the riddle I encountered.
# To solve yours, you'll have to rewrite the constraints based on your riddle.
# This gist contains a couple of helper functions that should help with writing constraints.

problem = Problem()
variables: [[str, str]] = []

# Create five variables with distinct values
def addDistinctVariables(base: str, values: [str]) -> [str]:
    keys = list(map(lambda i: f"{base}{i}", range(5)))
    problem.addVariables(keys, values)
    problem.addConstraint(AllDifferentConstraint(), keys)
    variables.append([base, keys])
    return keys

# Create variables for all properties at all positions
names = addDistinctVariables("name", ["winslow", "marcolla", "contee", "natsiou", "finch"])
drinks = addDistinctVariables("drink", ["rum", "whiskey", "wine", "beer", "absinthe"])
colors = addDistinctVariables("color", ["blue", "purple", "red", "white", "green"])
cities = addDistinctVariables("city", ["dunwall", "dabokva", "karnaca", "fraeport", "baleton"])
things = addDistinctVariables("thing", ["bird", "diamond", "tin", "medal", "ring"])

# Add a constraint to elements at relative offset, e.g. winslow_right_off_rum, names, drinks, [-1]
def __add_relative_disjunctive(constraint: Callable[[str, str], bool], keysA: [str], keysB: [str], offsets: [int]):
    disjunction_constraint = lambda a, *bs: any(map(lambda b: constraint(a, b), bs))
    for i in range(5):
        keysRelative = list(map(lambda j: keysB[j],
            filter(lambda j: j >= 0 and j < 5,
                map(lambda offset: i + offset, offsets))))
        if (len(keysRelative) == 0): continue
        problem.addConstraint(disjunction_constraint, [keysA[i]] + keysRelative)

# Add absolute constraint: keys[index] == value
def add_absolute(value: str, keys: [str], index: int):
    problem.addConstraint(lambda a: a == value, [keys[index]])

# Add relative constraint: Exists offset, index: keysA[index] == value <==> keysB[index + offset] == value
def add_relative(valueA: str, keysA: [str], valueB: str, keysB: [str], offsets: [int] = [0]):
    __add_relative_disjunctive(lambda a, b: (a == valueA) == (b == valueB), keysA, keysB, offsets)

# At the dinner party were Lady Winslow, Doctor Marcolla, Contess
# Contee, Madam Natsiou, and Baroness Finch.

# The women sat in a row. They all wore different colors and Baroness
# Finch wore a jaunty blue hat.
add_relative("finch", names, "blue", colors)

# Madam Natsiou was at the far left, next to the guest wearing a purple jacket.
add_absolute("natsiou", names, 0)
add_relative("natsiou", names, "purple", colors, [-1, +1])

# The lady in red sat left of someone in white.
add_relative("red", colors, "white", colors, [+1])

# I remember that red outfit because the woman spilled her absinthe all over it.
add_relative("red", colors, "absinthe", drinks)

# The traveler from Dunwall was dressed entirely in green.
add_relative("dunwall", cities, "green", colors)

# When one of the dinner guests bragged about her Bird Pendant, the woman next
# to her said they were finer in Dunwall, where she lived.
add_relative("bird", things, "dunwall", cities, [-1, +1])

# So Doctor Marcolla showed off a prized Ring, at which the lady from
# Dabokva scoffed, saying it was no match for her Snuff Tin.
add_relative("marcolla", names, "ring", things)
add_relative("dabokva", cities, "tin", things)

# Someone else carried a valuable War Medal and when she saw it, the visitor
# from Karnaca next to her almost spilled her neighbor's rum.
add_relative("karnaca", cities, "medal", things, [-1, +1])
add_relative("karnaca", cities, "rum", drinks, [-1, +1])

# Lady Winslow raised her wine in toast.
add_relative("winslow", names, "wine", drinks)

# The lady from Fraeport, full of beer, jumped up onto the table, falling onto
# the guest in the center seat, spilling the poor woman's whiskey.
add_relative("fraeport", cities, "beer", drinks)
add_absolute("whiskey", drinks, 2) # Center of [0,1,2,3,4] being 2

# Then Countess Contee captivated them all with a story about her wild youth in Baleton.
add_relative("contee", names, "baleton", cities)

# In the morning, there were four heirloom under the table: the Bird
# Pendant, Diamond, the Snuff Tin, and the War Medal.

# But who owned each?
for solution in problem.getSolutions():
    print("Solution:")
    for [base, keys] in variables:
        values = map(lambda value: solution[value].ljust(10), keys)
        print((base + ":").ljust(10) + " ".join(values))