Sign in to follow this  
EnigmaticCoder

Logic Puzzle Generator -- Design Questions

Recommended Posts

After Zahlman stated, "writing a bunch of accessor/mutator pairs like that is a big red warning flag", I realized that I program poorly, but that's not the point. I've been pondering the design of a program that generates logic puzzles like the one found at this url: http://winone.iqsociety.org/issues/01.pdf (Top of page 10). What I am trying is this: Create a person class which holds their order of arrival and the color of their hat. In addition to that data, for convenience, I thought I would hold the times that they did not arrive, who arrived before them, who arrived just before them, who arrived after them, etcetera. For instance, if they arrived second of four people, the vector holding those who arrived after would consist of two elements, three and four. After I finished writing this class, the data it holds seems utterly redundant, but all is not lost. I also need to make a similar class which holds the information that has been revealed by the clues. For instance, if a clue states: "Jake hates to wear blue and yellow just like Sally" Then the notColor vector in Jake and Sally's 'revealed information' objects will hold BLUE and RED. Alternatively, I could have a vector store remaining possibilities, and remove possible colors and arrival times after they are proven impossible when a clue is given. Then, if a clue would not remove any remaining possibilities (I.E. it's a duplicate), it would not be given. Also, if the remaining possibilities are down to one for each person, then no more clues will be stated. Here are my questions: - In order to store information about who arrives after a certain person, the total number of people must be known. How can I make this information available to the object? - Is it appropriate for a person class to hold data about other people? (I.E. who arrived after) - I mentioned that I thought it was redundant to hold data regarding when a person did not arrive. Does each person actually need to know when they did not arrive? What about with a revealed information object? - I started this post with a quote about get/set accessor functions for a reason. To avoid the pitfall of accessor functions, should I instead add "actions" (along with constructors of course) for each object to perform and omit the accessor functions? //After rereading my post, the answer to this question is obvious, but it sets up the next question nicely... - If I decide to keep the Person class as is, with data holding who came before, after, etcetera, would an appropriate "action" function be something like: getRelativeArrivalTimes (This could be done after each persons arrival time was set)? Zahlman, with this post, you demonstrated and proved what you've been stating all along: Functions should do something, and I'm understanding the whole idea better. P.S. This is unrelated, but would it be fun to state the puzzle like so: "Four suspects were seen leaving a murder scene (Seth, Rich, Mandy, and Susan), each of them owns a potential murder weapon (bat, crowbar, cane, hammer). The person who left last was the murderer. You know the following facts: - The person who left third does not own a bat - Etcetera, etcetera Who committed the crime and with which weapon?" I'm thinking of toning down the murder weapons to include something more comical. (I.E. feather, joke book, etcetera), but let me know what you think. [Edited by - anothrguitarist on October 14, 2007 12:12:00 AM]

Share this post


Link to post
Share on other sites
Are you sure you're fully aware of the complexity of the problem you're tackling?

Generating new puzzles with conditions as expressed in your example (not simply permuting the names of the actors in the given puzzle, but making a new one) is tricky.

Your post suggests you have no clear algorithm in mind for solving the problem; your approach seems to be 'dump stuff into objects and vectors, and hope a puzzle comes out'. All the worrying about what should and should not be in each class and accessor functions seems beside the point.

These puzzles are called discrete constraint satisfaction problems, and there's tons of CS devoted to them: how best to represent them, how to efficiently solve them, and how to pose them as problems to CS undergraduates.

Generating a set of constraints that are consistent (do not contradict each other) and have a unique solution, is trickier; you have to parametrize the space of constraints to be able to choose among them.

I'd start by writing a solver for these sorts of puzzle first. Hard coding constraints into classes is probably not the way to go: the right tool for the job and all that.

Prolog is exceptionally well suited to this: this puzzle maps directly into the subset of propositional logic supported by prolog, if I'm not mistaken.

I'd experiment with prolog even if you are hell-bent on writing this in C++ at the end of the day.

SICP has great chunks devoted to introducing constraint satisfaction: both for solving constraints:

http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-28.html#%_sec_4.3.2

and for representing constraints:

http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-22.html#%_sec_3.3.5

Now, the amb evaluator as written in scheme in SICP is not something you'd be able to directly translate to a language without support for first class continuations (read: almost any mainstream language), but the points made are language-agnostic.

Good luck!

Share this post


Link to post
Share on other sites
Quote:
Original post by Anonymous P
Are you sure you're fully aware of the complexity of the problem you're tackling?

Generating new puzzles with conditions as expressed in your example (not simply permuting the names of the actors in the given puzzle, but making a new one) is tricky.

Your post suggests you have no clear algorithm in mind for solving the problem; your approach seems to be 'dump stuff into objects and vectors, and hope a puzzle comes out'. All the worrying about what should and should not be in each class and accessor functions seems beside the point.

These puzzles are called discrete constraint satisfaction problems, and there's tons of CS devoted to them: how best to represent them, how to efficiently solve them, and how to pose them as problems to CS undergraduates.

Generating a set of constraints that are consistent (do not contradict each other) and have a unique solution, is trickier; you have to parametrize the space of constraints to be able to choose among them.

I'd start by writing a solver for these sorts of puzzle first. Hard coding constraints into classes is probably not the way to go: the right tool for the job and all that.

Prolog is exceptionally well suited to this: this puzzle maps directly into the subset of propositional logic supported by prolog, if I'm not mistaken.

I'd experiment with prolog even if you are hell-bent on writing this in C++ at the end of the day.

SICP has great chunks devoted to introducing constraint satisfaction: both for solving constraints:

http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-28.html#%_sec_4.3.2

and for representing constraints:

http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-22.html#%_sec_3.3.5

Now, the amb evaluator as written in scheme in SICP is not something you'd be able to directly translate to a language without support for first class continuations (read: almost any mainstream language), but the points made are language-agnostic.

Good luck!


I have to say, those are some great excerpts, and they are absolutely relevant to what I'm doing. I've only looked over them briefly, but I am already thinking of a new way to tackle this problem.

As for using a different language, I am open minded and enjoy learning new technology (I am a programmer, after all). Actually, scheme looks like an interesting language as well -- it's in English.

By the way, the puzzle in section 4.42 is awesome!

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this