Mahjong - Organisez les tuiles pour assurer au moins un chemin vers la victoire, quel que soit le tracé

Question

Indépendamment de la disposition utilisée pour les tuiles, existe-t-il un bon moyen de les séparer afin de garantir à l'utilisateur qu'au début du jeu, il existe au moins un chemin pour terminer le puzzle et gagner le jeu?

Évidemment, en fonction des déplacements de l'utilisateur, celui-ci peut se couper de la victoire. Je veux juste pouvoir toujours dire à l'utilisateur que le casse-tête est gagnable s'il joue bien.

Si vous placez au hasard des tuiles au début du jeu, il est possible que l'utilisateur effectue quelques mouvements et ne puisse plus le faire. Savoir que le puzzle est au moins résoluble devrait le rendre plus amusant à jouer.

Answer 1

Placez toutes les tuiles en sens inverse (c’est-à-dire, en commençant par le tableau, en travaillant)

Pour taquiner davantage le lecteur, vous pouvez le faire de manière visible mais à une vitesse très élevée.

Answer 2

Jouez le jeu à l'envers.

Disposez au hasard des pièces deux à une à des endroits où vous pourrez les glisser dans le tas. Vous aurez besoin d’un moyen de savoir où vous êtes autorisé à placer des pièces afin de vous retrouver avec un tas qui correspond à un modèle prédéfini, mais vous en auriez besoin de toute façon.

Answer 3

Je sais que c’est une vieille question, mais j’en suis venu à le résoudre moi-même. Aucune des réponses ici n’est tout à fait parfaite, et plusieurs d’entre elles ont des mises en garde compliquées ou vont se briser sur des schémas pathologiques. Voici ma solution:

Résolvez le tableau (en avant et non en arrière) avec des carreaux non marqués. Enlevez deux tuiles libres à la fois. Poussez chaque paire que vous supprimez sur une "paire correspondante". empiler. C’est souvent tout ce que vous devez faire.

Si vous rencontrez une impasse (numFreeTiles == 1), réinitialisez simplement votre générateur :) J'ai constaté que d'habitude je ne me trouvais pas dans l'impasse, et j'ai jusqu'à présent un nombre maximal de tentatives de 3 pour le 10 des mises en page que j'ai essayées. Une fois que j'ai frappé 8 tentatives, j'abandonne et attribue simplement le reste des tuiles de manière aléatoire. Cela me permet d’utiliser le même générateur pour la configuration de la carte et pour la fonction de lecture aléatoire, même si le joueur a tout gâché et créé un état impossible à résoudre à 100%.

Une autre solution lorsque vous vous retrouvez dans une impasse consiste à faire marche arrière (enlevez la pile, en remplaçant les tuiles sur le tableau) jusqu'à ce que vous puissiez prendre un chemin différent. Choisissez un chemin différent en veillant à bien assortir les paires qui vont supprimer la tuile de blocage d'origine.

Malheureusement, selon le tableau, cela peut tourner en boucle pour toujours. Si vous finissez par retirer une paire qui ressemble à un "pas de point de vente" route, où tous les "& routes; routes" " suivants sont une impasse, et il y a plusieurs impasses, votre algorithme ne sera jamais complet. Je ne sais pas s'il est possible de concevoir un tableau où ce serait le cas, mais dans ce cas, il existe toujours une solution.

Pour résoudre ce problème plus important, traitez chaque état de carte possible comme un nœud dans un DAG, chaque paire sélectionnée constituant une arête sur ce graphique. Faites une traversée aléatoire jusqu'à ce que vous trouviez un nœud feuille à la profondeur 72. Gardez une trace de votre historique de traversée afin de ne jamais répéter une descente.

Les impasses étant plus rares que les solutions du premier essai dans les présentations que j'ai utilisées, on pense immédiatement à une solution hybride. Essayez d’abord de le résoudre avec un minimum de mémoire (stockez les paires sélectionnées sur votre pile). Une fois que vous avez atteint la première impasse, dégagez-vous de la génération complète de marquage / bord lors de la visite de chaque nœud (évaluation lazy si possible).

Cependant, j’ai très peu étudié la théorie des graphes, alors il existe peut-être une meilleure solution au problème de parcours / recherche aléatoire DAG:)

Edit: Vous pouvez utiliser n’importe laquelle de mes solutions pour générer le tableau en sens inverse, comme dans le post du 13 octobre 2008. Vous avez toujours les mêmes mises en garde, car vous pouvez toujours vous retrouver avec des impasses. Générer une planche à l'envers a des règles plus compliquées, cependant. Par exemple, vous êtes assuré que votre configuration échouera si vous ne démarrez pas au moins CERTAINES de vos lignes avec la première pièce au milieu, comme dans une présentation avec une longue ligne. Choisir un premier coup complètement légal (légal) dans un générateur de résolution avant est plus susceptible de mener à un conseil résoluble.

Answer 4

La seule chose que j’ai été capable de faire est de placer les carreaux par paires comme une sorte de jeu de Mahjong Solitaire inversé. Ainsi, à n'importe quel moment du placement des tuiles, le tableau devrait ressembler au milieu d'un vrai jeu (c'est-à-dire qu'il ne devrait pas y avoir de tuiles flottant 3 couches au-dessus des autres tuiles).

Si les tuiles sont placées par paires identiques dans un jeu inversé, il devrait toujours en résulter au moins un chemin avant pour résoudre le jeu.

J'aimerais entendre d'autres idées.

Answer 5

Je pense que la meilleure réponse a déjà été avancée: créer un ensemble en le résolvant "à l'envers". - c’est-à-dire en commençant par un tableau vierge, puis en ajoutant une paire quelque part, en ajoutant une autre paire dans une position résoluble, etc.

Si vous préférez " Big Bang " approche (générant l’ensemble complet au début au hasard), que vous soyez un développeur très macho ou que vous vous sentiez masochiste aujourd’hui, vous pouvez représenter toutes les paires que vous pouvez éliminer de l’ensemble donné et comment elles dépendent de chaque autre via un graphe orienté.

À partir de là, il vous suffira d'obtenir la fermeture transitive de cet ensemble et de déterminer s'il existe au moins un chemin parmi au moins une des paires légales initiales menant à la fin souhaitée (il ne reste aucune paire de tuiles).

La mise en œuvre de cette solution est laissée au lecteur sous forme d’exercice: D

Answer 6

Voici les règles que j'ai utilisées dans mon implémentation.

Lors de la construction de tas, pour chaque frette d'une paire séparément, trouvez une cellule (lieux), qui sont:

• toutes les cellules des niveaux inférieurs sont déjà remplies
• place pour la deuxième frette ne bloque pas en premier, en considérant si la première frette déjà mise à bord
• les deux endroits sont "sur les bords" de tas déjà construit:
  • SOIT au moins un voisin à gauche ou à droite
  • OU c'est la première frette de suite (toutes les cellules de droite et de gauche sont récursivement libres)

Ces règles ne garantissent pas qu'une construction réussira toujours - elle laisse parfois les 2 dernières cellules libres auto-bloquantes, et la construction doit être retentée (ou au moins quelques dernières frettes). En pratique, " tortue " construit en pas plus de 6 tentatives.

La plupart des jeux existants semblent restreindre le fait de placer les premières frettes ("premier sur la rangée") quelque part au milieu. Cela donne des configurations plus pratiques, quand il n'y a pas de frettes aux bords des très longues lignes, restant en place jusqu'au dernier joueur. Cependant, " middle " est différent pour différentes configurations.

Bonne chance:)

P.S. Si vous avez déjà trouvé un tas de créations solubles en un tour, faites-le moi savoir.

Answer 7

Vous avez 144 tuiles dans le jeu, chacune des 144 tuiles a une liste de blocage. (la mosaïque en haut de la pile a une liste de blocs vide)

Tous les déplacements valides nécessitent que leur " current__vertical_Block_list " être vide .. cela peut être une matrice 144x144 donc 20k de mémoire plus une liste de blocs LEFT et RIGHT, également 20k chacun.

Génère une table de déménagement valide à partir de (remaning_tiles) AND ((vide la liste des blocs verticaux actuels) et ((vide la liste des blocs actuels gauche) ou (vide la liste des blocs sociaux actuels))))

Choisissez 2 tuiles aléatoires dans la table des coups valides, enregistrez-les Mettez à jour les (tables actuelles Vert, gauche et droite), enregistrez les tuiles supprimées dans une pile

Nous avons maintenant une liste de coups qui constituent un jeu valide. Attribuez des types de mosaïques correspondants à chacun des 72 déplacements.

pour les jeux difficiles, dépistez quand chaque tuile devient disponible. trouvez les ensembles qui ont été (tôt tôt tôt tard) et (tardivement tard tard) car il est vide, vous trouvez 1 blocs EE 1 LL et 2 blocs LE .. du bloc 2 LE, trouvez un TÔT qui bloque TOUT autre TÔT ( sauf à bloquer une pièce latérale gauche)

Une fois que vous avez un jeu valide, jouez avec la commande.

Answer 8

Solitaire? Juste une supposition, mais je suppose que votre ordinateur aurait besoin de battre le jeu (ou presque) pour le déterminer.

Une autre option pourrait consister à avoir plusieurs dispositions prédéfinies (permettant de gagner, mélangées à votre niveau actuel.

Dans une certaine mesure, vous pouvez vous assurer que l'une des 4 tuiles n'est pas supérieure à X couches sous un autre X.

La plupart des jeux que je vois ont la commande shuffle lorsque quelqu'un est bloqué.

Je voudrais essayer un mélange de choses et voir ce qui fonctionne le mieux.