Algorithme de résolution du dragueur de mines [fermé]

la génération du réseau est simple. Il y a quelques algorithmes simples dont vous avez besoin lors de l'exécution du mouvement du joueur, pour déterminer quels carrés à ouvrir et s'ils ont perdu ou gagné.

Génération de la grille

l'algorithme le plus simple est de placer toutes les mines au hasard. (Assurez-vous de ne pas les chevaucher!)

Problème: le premier clic du joueur pourrait être une mine.

amélioration: retarder le génération de la grille jusqu'à ce que l'utilisateur clique sur la première place, et ne pas mettre de mines dans cette place.

Problème: le premier clic du Joueur peut révéler un nombre non-zéro, et ils seront forcés de cliquer au hasard jusqu'à ce que quelque chose s'ouvre.

amélioration: ne générez pas de mines dans les (jusqu'à) huit carrés autour du premier clic, soit.

Problème: le Joueur peut être forcé de devinez à un moment donné, ce qui en fait une triste excuse pour un puzzle logique.

Amélioration: lancer le solveur le long du générateur, en s'assurant que le puzzle a une solution unique. Cela demande de l'intelligence, et n'est pas fait dans la plupart des variantes.

une autre façon, moins commune de résoudre les ambiguïtés est de détecter quand le joueur sait qu'il choisit entre des possibilités tout aussi probables et "faire s'effondrer la forme d'onde" dans la position qu'ils ont décidé sur. Je n'ai jamais vu ça en action, mais ce serait plutôt amusant.

le jeu

en plus de marquer des drapeaux, le Joueur peut faire deux types de mouvements pour tenter de découvrir des carrés:

• simple conjecture: le Joueur clique sur un carré à l'état inconnu et sans drapeau. Révélez le carré, voyez si le joueur est mort, et mettez un numéro dedans. Si le carré contient un 0, répétez ceci récursivement pour tous les carrés environnants. Ce devrait être dans une fonction dédiée, pour le séparer du gestionnaire d'événements de L'interface graphique, pour rendre la récursion facile, et parce qu'il est réutilisé dans le multiguess.

• Multiguess: le Joueur clique sur un carré qui est découvert et connu pour être sûr. Si le nombre de drapeaux entourant est égal au nombre dans ce carré, nous ouvrons les carrés non encadrés en utilisant la même procédure que ci-dessus.

gagner le jeu

si la nombre de places qui sont couvertes est le même que le nombre de mines, puis le joueur a gagné, même si elles n'ont pas placé un drapeau sur chaque carré.

quand le joueur perd, il est d'usage de noter toute estimation incorrecte qu'ils ont faite, les mines restantes, et la mine sur laquelle ils ont marché.

je veux juste ajouter ce qui suit si vous essayez d'écrire un solveur - Démineur est un problème NP complet (Archive Link). Ça veut dire jusqu'à ce que quelqu'un le prouve!--3-- > P = NP il est possible que vous ne puissiez rien faire de mieux que d'effectuer une recherche de force brute dans certaines situations (mais peut-être que le jeu n'est pas NP complet pour les petits champs).

Voici mon démineur solveur:

• pour chaque nombre de places:
  • Si compte de non ouvert autour = = nombre carré: Tous sont des mines
  • si nombre carré-Nombre de drapeaux autour = = 0: Toutes les mines non ouvertes ne sont pas des mines
• utiliser la règle du sous-ensemble

Voici une mise en œuvre réelle, notez qu'il a utilisé la règle du sous-ensemble, qui est plus difficile à expliquer https://github.com/SHiNKiROU/Minesweeper/blob/master/src/org/shinkirou/minesweeper/MinesweeperSolver.java#L27

bien sûr, mon algorithme peut échouer parfois. J'ai l'intention de mettre en œuvre un résolveur de rétrotractage de type Prolog

Je ne suis certainement pas un expert en démineurs, Mais voici l'algorithme que j'utilise quand j'essaie de le résoudre:

passez en revue tous les carrés qui sont la limite de la zone révélée. Pour chacun de ces carrés, le comte nombre de mines que vous avez révélées à côté de lui. soustraire le nombre qui est écrit dans la place (le nombre réel de mines qui sont autour d'elle). C'est le nombre de mines non découvertes autour de cette place. Divisez-le par nombre de carrés non révélés autour du carré actuel. C'est le Probabilité de chacun des carrés adjacents contenant une mine. Si un carré a une probabilité de 1, vous marquez comme une mine. Si un carré a une probabilité de 0, marquez-le comme étant sûr. Puis vous mettez à jour les numéros pertinents.

Que faire si aucun carré n'a de probabilité 0 ou 1? Un algorithme optimal tiendrait compte des contraintes des carrés multiples. Mais comme je l'ai écrit dans au début, je ne suis pas un expert en démineurs, donc je choisis au hasard parmi les autres carrés qui ont la probabilité la plus proche de 0 ou de 1.

Vérifiez ceci: http://quantum-p.livejournal.com/19616.html

toute position sur la carte, qui ne peut être résolu intuitivement avec le singe-raisonnement est une matrice qui pourrait être en mesure de résoudre un individu(ou la position entière) carrés qui peuvent conduire à de meilleures vitesses de résolution. Une simple supposition aléatoire n'a pas donné de bons résultats. J'ai implémenté cette méthode dans mon algorithme de résolution en C++ en ajoutant un système linéaire d'équations-solveur. Je fais des recherches sur le la difficulté du dragueur de mines en exécutant des dizaines de milliers de jeux à travers l'algorithme et en faisant des statistiques.

mon algorithme résout jusqu'à 85% des démineurs de niveau facile (9,9,10). Je n'ai pas encore fait de tests complets sur d'autres niveaux de difficulté, mais des tests plus petits suggèrent que le niveau moyen (16,16,40) a un taux de résolution de 55-60% et le niveau dur(30,16,99) aussi bas que 5-10%. Je vais ajouter quelques nouveautés qui le rendent plus optimale.

comme Henri l'a mentionné, la bonne façon de résoudre le dragueur de mines est avec les mathématiques, spécifiquement les mathématiques à matrice D'algèbre linéaire pour la partie déterministe. J'ai un post ici:

• explique comment cette méthode fonctionne
• a du code de travail que vous pouvez compiler et exécuter sur n'importe quelle plate-forme
• contient le code pour faire le jeu et un solveur trop

Vous pouvez voir que tous ici: https://massaioli.wordpress.com/2013/01/12/solving-minesweeper-with-matricies/

je recommande la lecture à travers et puis d'avoir une bonne pensée à ce sujet. La partie probabiliste de Minsweeper peut être résolue en utilisant les statistiques aussi, mais je n'ai pas encore un bon plan pour cela. Cependant, d'autres personnes ont regardé trop.

Avez-vous vu C# de la mise en œuvre du jeu? Le code source est téléchargeable, et le modèle objet est expliqué.

Les commentaires sont que vous n'avez pas besoin d'un algorithme pour construire le jeu. Je crois que vous voulez dire un algorithme dans le sens de résoudre et tout le monde pourrait le comprendre de cette façon aussi bien.

cependant toute solution à un problème peut être considérée comme un algorithme.

comme la plupart des problèmes de mathématiques, vous pouvez disséquer l'algorithme entier en algorithmes plus petits et moins complexes, jusqu'à ce que vous tombiez sur quelque chose d'assez petit pour résoudre. Vous obtiendrez ainsi la première solution correcte. Tard vous pouvez optimiser les petits algorithmes dans le contexte de l'ensemble de l'algorithme.

le gameboard peut être considéré comme un tableau bidimensionnel. Vous aurez un algorithme associé à chaque opération. La première opération serait probablement un ensemble aléatoire d'emplacements de mines avec des coordonnées x, y et un paramètre du nombre de mines et de la taille du panneau. Vous auriez un autre algorithme associé à la révélation d'un carré, qui prend la carte et un emplacement et détermine combien de mines sont adjacentes. L'algorithme final prendrait le tableau et vérifierait si des carrés sans mines sont laissés pour révéler.

maintenant, vous pouvez prendre chacun de ces algorithmes et essayer d'optimiser chacun d'eux pour une meilleure performance et dire "quelle est la meilleure façon de compter les carrés avec des mines adjacentes à un carré courant, donné un tableau de 2 dimensions en utilisant X,Y coordonnées.