Quel est mon problème:
Il y a un puzzle de Raymond Smullyan qui fonctionne comme ceci: vous êtes dans une pièce avec de nombreuses portes. Derrière certaines de ces portes, il y a des femmes; derrière les autres, il y a des tigres. Votre objectif est de choisir l'une des bonnes portes (celles avec les dames). Sur chaque porte, il y a un panneau qui dit quelque chose comme Il y a une dame derrière cette porte ou Il y a un lion derrière la porte II et VI et ainsi de suite. Maintenant, vous avez également des informations supplémentaires comme Un seul des panneaux dit la vérité ou Le panneau sur une porte n'est vrai que s'il y a une dame derrière cette porte et ainsi de suite. Par exemple, le premier puzzle se présente comme suit:
Il y a deux portes avec un panneau chacune. L'un des signes est vrai, l'autre est faux:
--------------------- --------------------- | 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 | --------------------- ---------------------Derrière quelle porte se trouve une dame?
Passons maintenant au sujet de cette question: je cherche des moyens possibles de générer automatiquement de tels puzzles. Le but (loin) est de construire un algorithme qui nécessite, comme paramètres, le nombre de portes (et peut-être la difficulté du puzzle résultant) et crée des textes correspondants pour les portes.
Ce que j'ai essayé jusqu'à présent:
Pas grand chose, car je ne sais pas trop par où commencer. Il est facile de créer un motif pour le texte sur les signes et il est également facile d'attribuer au hasard des déclarations vraies et fausses à ces signes, correspondant à la règle vraie-fausse que vous utilisez (par exemple, un seul signe dit la vérité ). Mais c'est la partie où cela devient délicat: comment créer un puzzle qui est résoluble et a une solution unique ? Ma première idée a été de créer un puzzle aléatoire et d'utiliser le retour arrière pour rechercher des solutions. Mais de cette façon, cela pourrait prendre très longtemps jusqu'à ce que l'algorithme ait finalement trouvé un ensemble de signes fonctionnel. De plus, de cette façon, vous ne pouvez pas facilement déterminer la difficulté d'un puzzle donné.
Donc, pour résumer: avez-vous une idée, des liens utiles, etc.? Toute aide est appréciée, je ne m'attends pas à ce que quelqu'un poste une solution parfaite et complète à mon problème.
(Remarque: j'ai initialement posé la question suivante sur stackoverflow mais on m'a dit que je serais plus susceptible d'obtenir une réponse ici!)
Réponses:
La génération de texte est un problème distinct, mais pour un petit nombre de portes, vous pourriez peut-être utiliser une carte de Karnaugh. Choisissez une cellule aléatoire qui sera vraie, toutes les autres seront fausses, puis utilisez un algorithme approprié pour trouver l'expression booléenne la plus efficace qui correspond à cette carte, par exemple
http://www.codeproject.com/Articles/37031/Karnaugh-Map-Minimizer-3-Variables
la source