Logic Games

The most famous of the logic games/puzzles is the Zebra or Einstein Puzzle. The simplest one that I've run across is the Basic 1 from BrainZilla.

Let's start with a very simple one:

3 Stuy students are seated in Chairs 0, 1 and 2. (this is CS)
Their names are: Bill, Karl and Joy
Their political affiliations are: Republican (rep), Democrat (dem) and Libertarian (lib)
They're deciding on courses for next year: Biology (bio), Artificial Intelligence (ai), AP US History (apush)

Each student has different poilitics, will take a different course, and as a matter of decorum, sits in a different chair. Match the course and politics to each student, and each student to the chair.

	Chair 0	Chair 1	Chair 2
Name: Bill, Karl, Joy
Politics: Republican, Democrat, Libertarian
Course: Biology, A.I., APUSH

Here's what we know:

Karl is to the left of the Republican.
There'll be no Joy in AI,
but there's always Joy being in the middle.
Bill needs APUSH.
The Libertarian is always right.

Let's organize the basic properties:

Properties = {'Name':['Bill','Karl','Joy'],\
'Politics':['Republican','Democrat','Libertarian'],\
'Course':['Biology','AI','APUSH']}

Now we also have to organize the constraints:

LeftOf = [
            ['Name','Karl','Politics','Republican'],\
            ['Politics','Republican','Politics','Libertarian'],\
            ['Politics','Democrat','Politics','Libertarian']\
        ]

Positions = [[1,['Name','Joy']]]

Connections = [['Name','Bill','Course','APUSH']]

NoConnections = [['Name','Joy','Course','AI']]

The fundamental object that we'll modify is the set of possibilities for each chair. Every constraint that is applied to this object removes some internal possibilities from it, until we conclude that for each property (name, politics and course) there can only be one value for each property for each chair. We start with a full set of possibilities, namely a dictionary of all the possibilities for each chair:

Possibilities = [{'Name':['Bill','Karl','Joy'],\
                'Politics':['Republican','Democrat','Libertarian'],\
                'Course':['Biology','AI','APUSH']},\

                {'Name':['Bill','Karl','Joy'],\
                'Politics':['Republican','Democrat','Libertarian'],\
                'Course':['Biology','AI','APUSH']},\

                {'Name':['Bill','Karl','Joy'],\
                'Politics':['Republican','Democrat','Libertarian'],\
                'Course':['Biology','AI','APUSH']}]

At this point, we know nothing. Here is how we can proceed:

1. Check every constraint for a violation. For instance, if we've previously concluded that Bill is in chair 1 (due to the results of a prior bad guess), then that's a violation. Also, if we're eliminated all possibilities for a chair's property, then it's a violation. If there's a violation, backtrack.

2. Use the constraints to infer property-values.
- For instance, if we conclude that Bill is in chair 2, then that chair's Course must be APUSH, and other names and courses for that chair can be eliminated.
- Also, no other chair's Name can be Bill, and no other chair's Course can be APUSH, so you can remove those possibilities.
- There is also a tacit constraint: every chair's Name must be different, and that's true of Course and Politics as well -- so if chairs 1 and 2 both have set names, then we can infer the Name of chair 0 -- also, if we've set chair 1's Name to "Joy", then we can remove "Joy" from all other chairs' Names.
- If an inference has been made, then try all other constraints again to see if other inferrences can be made -- other options can be narrowed down as well.
- Finally, when finished inferring, if any inferences have been made during this time, then go back to step 1, and check for violations. Otherwise, if no inferences have been made since we checked for violations, then go to step 3.

3. Guess. If we're done (all properties have single values), then celebrate. Otherwise, make a guess by pushing a copy (deepcopy) of the current Possibilities list onto the stack ... and then choosing a chair's property which has more than one possible value and setting it to one of its possibilities (e.g. set chair 2's Course to "AI") and go to step 1.