Algorithmus zur Herstellung von 'Lady or Tiger'-Rätseln?

8

Was ist mein Problem:

Es gibt ein Puzzle von Raymond Smullyan, das ungefähr so ​​funktioniert: Sie befinden sich in einem Raum mit vielen Türen. Hinter einigen dieser Türen stehen Damen; hinter den anderen stehen tiger. Ihr Ziel ist es, eine der richtigen Türen auszuwählen (die mit den Damen). An jeder Tür befindet sich ein Schild mit der Aufschrift "Hinter dieser Tür steht eine Dame" oder hinter Tür II und VI befindet sich ein Löwe und so weiter. Jetzt haben Sie auch einige zusätzliche Informationen wie Nur eines der Zeichen sagt die Wahrheit oder Das Zeichen an einer Tür ist nur wahr, wenn sich hinter dieser Tür eine Dame befindet und so weiter. Das erste Puzzle sieht zum Beispiel so aus:

Es gibt zwei Türen mit jeweils einem Schild. Eines der Zeichen ist wahr, das andere ist falsch:

 ---------------------    ---------------------
|      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 |
 ---------------------    ---------------------

Hinter welcher Tür steht eine Dame?

Kommen wir nun zum Thema dieser Frage: Ich suche nach Möglichkeiten, solche Rätsel automatisch zu generieren. Das (weit entfernte) Ziel besteht darin, einen Algorithmus zu erstellen, der als Parameter die Anzahl der Türen (und möglicherweise die Schwierigkeit des resultierenden Puzzles) erfordert und entsprechende Texte für die Türen erstellt.

Was ich bisher versucht habe:

Nicht viel, da ich nicht wirklich weiß, wo ich anfangen soll. Es ist einfach, ein Muster für den Text auf den Zeichen zu erstellen, und es ist auch einfach, diesen Zeichen zufällig wahre und falsche Aussagen zuzuweisen, die der von Ihnen verwendeten Richtig-Falsch-Regel entsprechen (z. B. sagt nur ein Zeichen die Wahrheit ). Aber genau hier wird es schwierig: Wie erstelle ich ein Puzzle, das lösbar ist und eine einzigartige Lösung hat ? Meine erste Idee war, ein zufälliges Puzzle zu erstellen und mithilfe von Backtracking nach Lösungen zu suchen. Auf diese Weise kann es jedoch sehr lange dauern, bis der Algorithmus endlich einen funktionierenden Satz von Zeichen gefunden hat. Auf diese Weise können Sie auch nicht leicht feststellen, wie schwierig ein bestimmtes Puzzle ist.

Zusammenfassend lässt sich sagen: Haben Sie eine Idee, hilfreiche Links usw.? Jede Hilfe wird geschätzt, ich erwarte nicht, dass jemand eine perfekte und vollständige Lösung für mein Problem veröffentlicht.

(Hinweis: Ich habe ursprünglich die folgende Frage zum Stapelüberlauf gestellt, aber dort wurde mir gesagt, dass ich hier eher eine Antwort bekommen würde!)

Messgerät
quelle
Vielleicht finden Sie aaai.org/Papers/AAAI/2007/AAAI07-361.pdf nützlich.
Adam
1
Tatsächlich denke ich, dass Sie bei der Math SE vielleicht bessere Antworten bekommen. Ich würde sagen, dass dies eine Variante des SAT-Problems ist, das naiv O (2 ^ n) ist, was bedeutet, dass die Lösung eines Problems durch rohe Gewalt an 20-ish-Türen sehr schnell als einzigartig erwiesen werden kann. Ich würde sagen, dass die Schwierigkeit direkt mit der Länge des Ausdrucks zusammenhängt, und ich würde Ausdrücke halb zufällig mit vordefinierten Einschränkungsmustern erstellen.
Panda Pyjama
Vielleicht interessiert Sie werden diese Frage auch
Panda Pajama

Antworten:

1

Die Texterzeugung ist ein separates Problem, aber für eine kleine Anzahl von Türen könnten Sie möglicherweise eine Karnaugh-Karte verwenden. Wählen Sie eine zufällige Zelle aus, die wahr ist, alle anderen sind falsch, und verwenden Sie dann einen geeigneten Algorithmus, um den effizientesten booleschen Ausdruck zu finden, der dieser Karte entspricht, z

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

David Cummins
quelle
Das wird ein Rätsel mit einer gültigen Lösung finden, aber ich denke, ich kann nicht garantieren, dass es eine einzigartige Lösung gibt ... Oder kann es?
Panda Pyjama
Wenn Sie jede andere Zelle auf Null setzen, garantieren Sie, dass es meiner Meinung nach keine anderen Lösungen gibt.
David Cummins