Etant donné que la plupart des démineurs sont souvent résolus par essais et erreurs (et sans faire intervenir de raisonnement), j'ai cherché des situations où le raisonnement s'impose.
La solution est simple : faire une grille où plusieurs solutions existent sans induire d'erreur ! Pour choisir une solution parmi les autres, il faut alors ajouter certains prédicats.
L'exemple classique : "il reste 10 mines à placer". Si la grille admet plusieurs solutions mais qu'une seule fait appel à 10 mines, alors c'est cette solution qu'il faut retenir.
Pour corser les choses, on peut imaginer d'autres prédicats :
1) "Il reste un nombre de mine tel que la grille n'admet qu'une seule solution" : si la grille accepte 3 solutions à 11 mines, et une seule solution à 10 mines, alors il faut retenir la solution à 10 mines.
2) "En plaçant arbitrairement une seule mine, tout le reste de la grille est déterminé" : si la grille admet une et une seule solution en plaçant arbitrairement une mine particulière, et que les autres mines potentielles aboutissent soit à la même grille soit à une situation indéterminée, alors il faut retenir cette seule solution.
Mise en application (la grille vierge est à gauche, ses 3 solutions possibles sont à droite) :
Selon le 1er prédicat ("connaissant le nombre de mines, il n'y a qu'une solution"), la solution est le cas 1 car c'est la seule solution univoque quand on fixe le nombre de mines (en l'occurence 3 mines restantes).
Selon le 2e prédicat ("la grille devient déterminée si l'on pose arbitrairement une seule mine"), la solution est le cas 3 car c'est la seule qui est entièrement déterminée par l'imposition d'une seule mine (en l'occurence la violette), toutes les autres mines étant insuffisantes à elles seules pour déterminer la grille.
Avantage : en essayant de résoudre la grille par essais et erreurs, on aboutit à plusieurs solutions valides et on ne peut pas savoir laquelle est juste.
Inconvénient : on voit qu'une même grille peut admettre des solutions différentes selon le prédicat posé, ce qui pourrait chagriner certains. C'est pourquoi j'ai eu l'idée de faire des grilles qui, pour être résolues, devaient accepter simultanément les 2 prédicats !
Et voilà donc le (mini) défi :
Pouvez-vous résoudre ces deux grilles de démineur sachant ceci :
La solution est unique si l'on connait le nombre de mines restantes ET que l'on place arbitrairement une et une seule mine !
(Image zoomable)
Pour prouver que vous avez bien raisonné, merci d'indiquer précisément l'emplacement de la mine que vous avez dû arbitrairement placer, et aussi d'indiquer tous les nombres de mines restantes qu'auraient pu accepter les deux grilles (càd indiquer les valeurs qu'auraient pu prendre x et y).
Je rappelle le code couleur :
- case grise = à dévoiler
- case rouge = mine
- case avec chiffre = indique le nombre de mines entourant la case.
Ces deux grilles sont extrêmement petites et ne vous prendront pas trop de temps. Mais imaginez une grande grille qui en plus incluerait les méthodes logiques de Clydevil : il y a moyen de faire des grilles d'un niveau diabolique !
En attendant... Bon amusement !