# Data Structures for Logic Games / Deduction Rules / Sufficient Set of Clues?

I've been cogitating about developing a logic game similar to Einstein's Puzzle , which would have different sets of clues for every new game replay.

What data structures would you use to handle the different entities (pets, colors of houses, nationalities, etc.), deduction rules, etc. to guarantee that the clues you provide point to a unique solution?

I'm having a hard time thinking about how to get the deduction rules to play along with the possible clues; any insight would be appreciated.

• I don't think it would be very interesting to play. After you solve it once, doing it again with different rules wouldn't be much different from playing sudoku.
– o0'.
Nov 24, 2010 at 17:14
• On the other hand, people do hundreds of sudoku before getting bored with them. And if you tie the answers to some kind of action-in-world rather than just typing in a number or name, people won't even complain it's sudoku.
– user744
Nov 24, 2010 at 18:01
• This reminds me of this game: nick.com/games/series.html Nov 24, 2010 at 19:38
• I would suggest taking a look at Everett Kaser's games - he has made a ton of games of this nature, in particular Sherlock which was inspired by that very puzzle, but also some of the other games, like Honeycomb Hotel or his latest game, Mrs. Hudson. It might help you to see this sort of thing in action. Nov 25, 2010 at 1:59
• @Joe: what you say is technically right, but the important thing here is to know what you are (he is) doing. Doing a sudoku-like game is fine if you are aware you are doing that, while it will almost certainly lead to crap results if you think you are doing something else.
– o0'.
Nov 25, 2010 at 15:06

Wow. This actually seems like a situation where old-school AI semantic webs, like Richard Bartle thought were going to be important to the future of games when he wrote Artificial Intelligence and Computer Games, would be useful. You basically have a couple of data lists (database tables, whatever), the first of which specifies rules about how things can relate to each other, like:

a PERSON must LIVE IN a DOMICILE
a PERSON must OWN an ANIMAL
a PERSON must DRINK a BEVERAGE
a PERSON must SMOKE a CIGARETTE BRAND
a PERSON must BE OF a NATIONALITY
a DOMICILE must BE IN a POSITION
a DOMICILE must BE OF a COLOR


Then you have instances of the categories:

ANIMAL: dog snail zebra fox horse
BEVERAGE: milk tea OJ coffee water
CIGARETTE BRAND: Kools Parliaments Luckies OldGold Chesterfields
NATIONALITY: Englishman Spaniard Ukrainian Japanese Norwegian
POSITION: first second third fourth fifth
COLOR: red green yellow ivory blue


These data structures don't completely encapsulate the situation -- you need the uniqueness constraints, and some of the categories need meta-rules, like POSITION needs handling of the "to the right of", "to the left of", and "next to" concepts, for example -- but the structure of the problem seems to strongly suggest them.

Dunno if this will take you very far, but I hope it helps.

My recommendation is to look at the Python code for Constraint Satisfaction Problems (CSPs) provided with the AIMA project. They use a Dictionary (associative array/hash table) to keep track of valid constraints. Also, there are implementations of several algorithms used to solve CSPs, like min-conflicts and AC3.

The code includes a sample Zebra problem as an example, like the one you linked to.

This goes very deep actually. Strange that Wikipedia never mentions it.

What you are looking for are very hard proofs that can, probably, be reached with things like Fitch proofs. So we are trying to deduct things out of our given data. There are a lot of Fitch proof builders that do a lot of work for you. But some exercises are just not to proof.

I don't know if the user should do the calculations. If so, be aware of things like 3SAT, which are undoable problems for polynomial time.

As for the data structures you want to use, I think you want to have some kind of Rule class. The rule can be anything, depending on the type. There aren't a lot of rules in predicate logics, so this can be overcome by inheriting (if, iff, and, or, not...). These rules only have to be evaluated. And the only thing a rule can do, is return true or false. Because that is what you do with predicate logics. At university, I was recommended to read this book by John Kelly.

Going back to the classes: You should see these problems like you would see implementing normal calculations with math. What is a + operator? It contains two parameters, which can be a new equation by itself, or just a number. I think you have the same with Rules. They can have new Rules as a parameter, or just a boolean (so called predicate).

I hope this helps you a lot, especially the references. If you want to know more, or if I'm going into the wrong direction, please tell me.

• The problem isn't simply proofs in predicate logic over a finite (and tiny!) model, or I would've answered rather than put a bounty up. The goal isn't to solve the problem - the goal is to automatically make the problem, and in an interesting way.
– user744
Feb 1, 2011 at 0:29
• @Joe The problem, even for a tiny set, would still be the 3SAT problem. If you only create AND's and OR's, this could lead to things that are not satisfyable, so I think it would be very hard to just generate a random puzzle. The puzzle should contain at least some restrictions. Sometimes, backwards reasoning could be the answer (have a solution, leave things out) Feb 1, 2011 at 10:49
• General predicate logic is actually harder than 3SAT; however, modern proof algorithms are really pretty good in practice. Aside from that, simply generating a model, a puzzle, and checking a solution can be done in linear time - the trick is making sure the constraints provided produce a unique, discoverable solution.
– user744
Feb 1, 2011 at 11:12
• @Joe so are there any constraints that we can be certain about for creating this puzzle? The question still was: what datastructure to use. So I still think that the Rule class is a good idea. Modelling these constraints is still done by predicate logic I think. Feb 1, 2011 at 13:04

I have no good answer, but looking for hints on the same kind of problem, I found this repository on github:

https://github.com/nateinaction/Zebra-Puzzle

It contains some logic for selecting clues and deciding how many clues you would need to make the puzzle solvable.

There's this on solving it.

Of course, I think it wouldn't be too difficult to work backwards; that is have a list like this:

• Fred Red Dog

• Steve Blue Cat

• Bill Purple Whale

• Eric Cyan Dolphin

Which could be easily generated, and then make up a set of rules from that.

As for storage, why not a set of each separate thing, so [Fred, Steve, Bill, Eric] and a set of the answer [Fred, Red, Dog]. Then have 'NAME does (not) ACTION OBJECT'.

When you get down to it, does a unique solution really matter? As long as your game can split them into the lists, and check 'set 1 does not contain Whale'.

• The trick is, you want the problem to still be hard. If the rules you generate admit 90% of the possible combinations as valid answers, it's no longer an interesting puzzle.
– user744
Nov 24, 2010 at 17:05
• I guess that is a valid point - but isn't the solution just to lower the number of clues given? Nov 24, 2010 at 17:43
• No. Underspecification is more likely to lead to many valid conclusions. Overspecification is likely to lead to one very obvious conclusion. A good logic puzzle avoids both.
– user744
Nov 24, 2010 at 17:45
• Ah yes, I missed that somehow. I will try and add a better solution if I can think of one. Nov 24, 2010 at 17:48
• Joe: Exactly right with your first comment. A puzzle that lets you jam clues together willy-nilly isn't so much a puzzle as a kindergarten art project. Nov 25, 2010 at 17:55