Je crée un jeu de puzzle qui, tout en jouant à la main pour des niveaux faciles, est destiné à être résolu par des programmes informatiques pour les plus difficiles. Le puzzle est un plan d'inondation sur une planche hexagonale. Vous pouvez essayer un prototype ici .
Voici comment fonctionne le puzzle: en choisissant une couleur du haut, vous effectuez un remplissage d'inondation à partir de la tuile supérieure gauche. Cela convertit progressivement le tableau en une couleur unie. Le défi consiste à le faire dans un certain nombre de mouvements.
J'ai créé plusieurs énigmes similaires à celles-ci, et la clé est d'utiliser un algorithme qui génère des cartes difficiles à résoudre sans savoir comment ils ont été créés. Par exemple, ici, nous pourrions produire une carte en inversant le remplissage des inondations: Travailler à l'envers d'une planche solide jusqu'à ce qu'il soit non conçu. Nous savons combien d'étapes cela a pris et peut définir cela comme une liaison inférieure sur une solution.
Le problème que je suis confronté est que lorsque j'essaie cette approche, ma limite supérieure est trop élevée. Il devient trivial de résoudre le casse-tête dans ce nombre de mouvements, même en bougeant de manière aléatoire.
Une approche qui n'est pas une solution ne génère une carte aléatoire puis de la résoudre de manière optimale et de la définir comme la cible. Le but est de créer un puzzle où la résolution de la résolution est une heure de NP ou au moins un dur p.
Alors, que je cherche est un algorithme qui peut générer des planches extrêmement dures où les résoudre leur, car ils deviennent plus grands, devient un défi sérieux. 
(Source: Hacker.org )
3 Réponses :
Lors du cryptage RSA, nous ne trouvons pas de nombres premiers, nous sélectionnons des numéros aléatoires, puis appliquons des tests à ceux qui nous donnent une probabilité de plus en plus élevée du nombre étant primordiale, sans le prouver.
Je suggère la même chose. Essayez de trouver des conditions qui donnent une bonne probabilité que le puzzle ait les propriétés souhaitées et les tests pour ceux-ci. Ou vous pouvez utiliser des algorithmes génétiques / des réseaux neuronaux et les former pour reconnaître les "bons" puzzles, ce qui constitue la même chose.
J'essaierais de prouver que c'est NP-complet ou en P, d'avoir une idée des configurations difficiles.
Je résumant également les hexagones et utiliserais une représentation comme graphique.
J'ai joué beaucoup le puzzle de l'inondation rectangulaire ( http://labpiixies.com/ gadget_page.php? id = 10 ). Excité de voir une version hexagone! Je pense que la recherche d'un jeu dur est aussi simple que: Évitez les gros blocs de la même couleur à apparaître dans le puzzle. Au moins dans les cas rectangulaires que j'ai vus, presque tous les énigmes pouvant être résolus dans un petit nombre d'étapes ont de gros blocs de couleurs.
P.s. Je pense que votre "limite inférieure" n'est pas valide. Lorsque vous travaillez en avant, si une bonne stratégie est utilisée, vous pouvez réellement terminer en moins de pas. La "limite inférieure" est vraiment une limite supérieure de la solution optimale.
Je n'aurais probablement pas dû utiliser «Bombe inférieure» car il est un peu ambigu lorsque l'objectif est de minimiser, mais oui, nous parlons de la même chose. Éviter de gros blocs de couleur a du sens de faire du mal à faire un puzzle, mais j'ai besoin d'un moyen de prouver une solution rapide.
Veuillez déplacer le "problème que je suis confronté ..." phrase au début d'un paragraphe. À la fin du plus long paragraphe, il est perdu.
C'est deux ans plus tard, pouvez-vous nous poster votre pensée actuelle?
Je ne pouvais pas venir avec quoi que ce soit de bien, je n'ai donc jamais mis le puzzle en ligne, malheureusement. Si quelqu'un arrive jamais avec un bon algorithme, je vais toujours le faire!