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!)
Antworten:
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
quelle