8
\$\begingroup\$

What my problem is:

There is a puzzle by Raymond Smullyan that works something like this: You are in a room with many doors. Behind some of those doors, there are ladies; behind the others, there are tigers. Your goal is to pick one of the right doors (the ones with the ladies). On every door, there's a sign that says something like There's a lady behind this door or There is a lion behind door II and VI and so on. Now, you also have some additional information like Only one of the signs says the truth or The sign on a door is true only if there is a lady behind that door and so on. For example, the first puzzle goes like this:

There are two doors with one sign each. One of the signs is true, the other one is false:

 ---------------------    ---------------------
|      DOOR I         |  |      DOOR II        |
| There's a lady in   |  | In one of those     |
| this room and a     |  | rooms, there's a    |
| a tiger in the      |  | lady, in the other  |
| other one           |  | one there's a tiger |
 ---------------------    ---------------------

Behind which door is a lady?

Now, getting to the topic of this question: I'm looking for possible ways to auto-generate such puzzles. The (far away) goal is to build an algorithm that requires, as parameters, the number of doors (and maybe the difficulty of the resulting puzzle) and creates corresponding texts for the doors.

What I have tried so far:

Not much, as I don't really know where to start. It's easy to create a pattern for the text on the signs and it's also easy to randomly assign true and false statements to those signs, corresponding to the true-false-rule you use (e.g. Only one sign says the truth). But that's the part where it get's tricky: How to create a puzzle that is solvable and has a unique solution? My first idea was to create a random puzzle and use backtracking to search for solutions. But that way, it could take very long until the algorithm has finally found a working set of signs. Also, that way you can't easily determine how difficult a given puzzle is.

So, summing it up: Do you have any idea, any helpful links, etc.? Any help is appreciated, I don't expect anyone to post a perfect and complete solution for my problem.

(Note: I originally asked the following question on stackoverflow but was told there that I would be more likely to get an answer here!)

\$\endgroup\$
  • \$\begingroup\$ You might find aaai.org/Papers/AAAI/2007/AAAI07-361.pdf useful. \$\endgroup\$ – Adam Nov 19 '13 at 23:45
  • 1
    \$\begingroup\$ In fact, I think you may get better answers at the math SE. I would say that this is a variant of the SAT problem, which is naively O(2^n), which means that the solution of a problem can be proved unique via brute force to 20-ish doors very quickly. I'd say the difficulty is directly tied to the length of the expression, and I'd create expressions semi-randomly with predefined constraint patterns. \$\endgroup\$ – Panda Pajama Nov 20 '13 at 2:09
  • \$\begingroup\$ You may be interested in this question as well \$\endgroup\$ – Panda Pajama Nov 21 '13 at 1:30
1
\$\begingroup\$

Text generation is a separate issue, but for a small number of doors perhaps you could use a Karnaugh map. Pick a random cell that will be true, all others will be false, then use an appropriate algorithm to find the most efficient boolean expression that matches that map, e.g.

http://www.codeproject.com/Articles/37031/Karnaugh-Map-Minimizer-3-Variables

\$\endgroup\$
  • \$\begingroup\$ That will find a puzzle with a valid solution, but I think can't guarantee it will have a unique solution... Or can it? \$\endgroup\$ – Panda Pajama Nov 20 '13 at 11:12
  • \$\begingroup\$ By setting every other cell as zero you guarantee there will be no other solutions I believe. \$\endgroup\$ – David Cummins Nov 20 '13 at 22:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.