Demineur : création et solution

Soyez le premier à donner votre avis sur cette source.

Vue 8 575 fois - Téléchargée 372 fois


Description

Ce programme permet de créer une grille de démineur et cherche la solution. On peut aussi lui passer une grille en paramètre et le faire chercher.

Les règles que j'ai trouvées ne sont pas toutes évidentes. Bon courage (il vaut mieux faire des dessins pour chaque cas).

Source / Exemple :


Voici les règles utilisées dans la résolution.
Si ça peut vous être utile ...

Les règles 6 et 7 sont utilisées en dernier ressort car 
plus complexes.
Si aucune règle ne marche, j'utilise une pseudo règle
statistique (surement à améliorer).

Chaque règle est donnée en français puis en pseudo-code.

// ********************************************
// Pour les formules
// I(x) = Inconnus autour de x
// V(x) = Tous les voisins directs de x
// E(x) = Etat de x
// B(x) = Nombre total de bombes voisines de x
// T(x) = Nombre de bombes non trouvées autour de x
// C(x) = Nombre de bombes connues autour de x
// x inc y = voisins de x Inclus dans y
// x int y = intersection de x et y
// !(x) = contraire de x
// ********************************************

// Règle 0
S'IL reste autant de bombes à trouver qu'il y a d'inconnus
autour de x 
ALORS tous les inconnus autour de x sont des bombes
Si I(x) == T(x)
   I(x) = Bombe
Fsi

// Règle 1
SI toutes les bombes à trouver autour de x sont trouvées
ALORS tous les inconnus autour de x sont vides
Si T(x) == 0
 	I(x) = Libre
 Fsi

// Règle 2
SI les inconnus de x sont inclus dans les inconnus de y et
le nombre de bombes non trouvées autour de x est égal au
nombre de bombes à trouver autour de y
ALORS les inconnus autour de y (et de x) qui ne sont pas
dans l'intersection de x et y sont libres
Si I(x) inc I(y) ET T(x) == T(y)
 	I(y) - (x int y) = Libre
Fsi

// Règle 3
SI les inconnus autour de x sont inclus dans ceux de y et 
le nombre de bombes non trouvées autour de x
 -  le nombre de bombes non trouvées autour de y
 = le nombre d'inconnus autour de x - le nombr
d'intersections
ALORS les inconnus de y qui ne sont pas dans l'intersection
ont une bombe
Si I(x) inc I(y) ET T(y) - T(x) == C(I(x) - (x int y))
 	I(y) - (x int y) = Bombe
Fsi

// Règle 4
SI le nombre de bombes non trouvées autour de x - le nombre
d'inconnus de x qui n'appartiennent pas à l'intersection 
de x et y est égal au nombre de bombes non trouvées autour
de y
ALORS les inconnus de y qui ne sont pas dans l'intersection
sont libres
Si T(x) - C(I(x) - (x int y)) == T(y)
 	I(y) - (x int y) = Libre
Fsi

// Règle 5
SI le nombre de bombes non trouvées autour de x - le nombre
de bombes non trouvées autour de y est égal au nombre de
bombes non trouvées autour de x qui n'appartiennent pas à
l'intersection de x et y
ALORS les inconnus de x qui ne sont pas dans l'intersection
ont une bombe
Si C(I(x) - (x int y)) == T(x) - T(y)
 	I(x) - (x int y) = Bombe
Fsi

// Règle 6
SI le nombre de bombes non trouvées autour de x - le nombre
d'inconnus de x qui n'appartiennent pas à l'intersection de
x et y est égal au nombre de bombes non trouvées autour de y
ALORS les inconnus de y qui ne sont pas dans l'intersection
sont libres
Si T(x) - C(I(x) - (x int y)) == T(y)
 	I(y) - (x int y) = Libre
Fsi

// Règle 7
SI le nombre de bombes non trouvées autour de x - le nombre
de bombes non trouvées autour de y est égal au nombre de
bombes non trouvées autour de x qui n'appartiennent pas à
l'intersection de x et y
ALORS les inconnus de x qui ne sont pas dans l'intersection
ont une bombe
Si C(I(x) - (x int y)) == T(x) - T(y)
 	I(x) - (x int y) = Bombe
Fsi

Conclusion :


C standard, devrait être compilable sous tous les environnements.

Codes Sources

A voir également

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.