ciel

Le démineur

Résolution d'une grille en probabilité

Ce jeu classique a pour objet de localiser des mines cachées dans un champ avec pour seule indication le nombre de mines dans les zones adjacentes et le nombre de mines total dans le champs.

Taille de la grille :

Mode d'emploi

Algorithme

Dans un premier temps, quelques règles déterministes permettent de dévoiler les mines les plus évidentes. A ce stade, les zones connexes autour des cases dévoilées sont résolues de manière indépendante. A l'intérieur d'une zone, les unions et intersections d'information permettent souvent de confirmer ou d'exclure une mine. Ces études locales permettent également de déterminer le nombre minimal et maximal de mines pouvant être cachées dans la zone. L'algorithme se montre d'une efficacité moyenne sur cette partie, il procède à de nombreuses itérations mais peut ne pas aboutir totalement.

Dans un second temps, l'algorithme procède à un dénombrement des possibilités d'enfouissement de mines cohérentes avec les informations déja dévoilées ou calculées dans la première étape. Cette étape se montre fiable mais est extrêment coûteuse, les nombres en jeux croissant de manière exponentielle avec la taille de la grille.


Conforme au standard HTML 4.01 Feuille de style CSS valide Page non-fumeur(c) JM17-10-2010 Me laisser un message Page d'accueil