Démineur est un jeu de puzzle populaire où vous devez découvrir quelles tuiles sont des "mines" sans cliquer sur ces tuiles. Au lieu de cela, vous cliquez sur les tuiles à proximité pour révéler le nombre de mines adjacentes. Un inconvénient du jeu est qu'il est possible de se retrouver dans un scénario où il y a plusieurs réponses valides et que vous ne pouvez que deviner. Par exemple, prenez le tableau suivant:

1110
2*31
3*??
2*4?
112?

Dans ce format, un nombre représente le nombre de mines adjacentes, un *représente une mine connue et un "?" représente une mine potentielle. Ce qui est regrettable dans ce casse-tête, c'est qu'il existe quatre solutions potentielles distinctes et valides :

1110    1110    1110    1110    
2*31    2*31    2*31    2*31
3*4*    3*5*    3**2    3**1
2*42    2*4*    2*4*    2*42
112*    1121    1121    112*

Cela signifie que la carte est insoluble . Voici un exemple de panneau soluble :

1121
1??*
12?*
0122

Cette carte est résoluble car il n'y a qu'une seule solution valable possible:

1121
1*4*
12**
0122

Votre tâche consiste à écrire un programme ou une fonction qui prend une carte de dragueur de mines valide et détermine si elle est résoluble ou non. Par "carte de démineur valide", je veux dire que l'entrée sera toujours rectangulaire, aura au moins une solution et ne contiendra aucun caractère invalide.

Votre entrée peut être un tableau de caractères, un tableau de chaînes, une chaîne contenant des sauts de ligne, etc. La sortie doit être une valeur véridique si elle est résoluble et une valeur fausse si elle ne l'est pas. Je ne suis pas extrêmement préoccupé par les performances, mais votre solution doit théoriquement fonctionner pour n'importe quelle entrée de taille.

Comme d'habitude, les failles standard s'appliquent et la solution la plus courte en octets gagne!

Exemples:

Les exemples suivants sont tous résolubles:

1121
1??*
12?*
0122

1110
1???
1110
0000

1110
3???
??20
*310

****
****
****
****

0000
0000
0000
0000

1100
*100
2321
??*2
13*2
1221
1*10
1110

1121
2*??
2*31
2220
1*10

Les exemples suivants sont tous insolubles:

1110
2*31
3*??
2*4?
112?

01??11*211
12??2323*1
1*33*2*210
12?2122321
13?3101**1
1***101221

1***
3*52
2*31
12??
02??
01??

00000111
000012*1
00001*21
22101110
**100111
?31123*1
?311**31
**113*20

GNU Prolog, 493 octets

z(_,[_,_]).
z(F,[A,B,C|T]):-call(F,A,B,C),z(F,[B,C|T]).
i([],[],[],[]).
i([H|A],[I|B],[J|C],[H-I-J|T]):-i(A,B,C,T).
c(A/_-B/_-C/_,D/_-_/T-E/_,F/_-G/_-H/_):-T#=A+B+C+D+E+F+G+H.
r(A,B,C):-i(A,B,C,L),z(c,L).
q(63,V):-var(V).
q(42,1/_).
q(X,0/Y):-Y#=X-48.
l([],[0/_]).
l([H|T],[E|U]):-q(H,E),l(T,U).
p([],[[0/_,0/_]],0).
p([],[[0/_|T]],N):-M#=N-1,p([],[T],M).
p([H|T],[[0/_|E]|U],N):-p(T,U,N),l(H,E).
m([H|A],B):-length(H,N),p([],[R],N),p([H|A],M,N),z(r,[R|M]),p(B,M,N).
s(A):-setof(B,m(A,B),[_]).

Un prédicat supplémentaire qui peut être utile pour les tests (ne fait pas partie de la soumission):

d([]).
d([H|T]):-format("~s~n",[H]),d(T).

Prolog est certainement le bon langage pour résoudre cette tâche du point de vue pratique. Ce programme énonce à peu près les règles du démineur et permet au solveur de contraintes de GNU Prolog de résoudre le problème à partir de là.

zet isont des fonctions d'utilité ( zfait une sorte d'opération de type pli mais sur des ensembles de trois éléments adjacents plutôt que 2; itranspose 3 listes de n éléments en une liste de n 3-tuples). Nous stockons en interne une cellule comme , où xx/y est 1 pour une mine et 0 pour une mine non, et y est le nombre de mines adjacentes; cexprime cette contrainte au tableau. rs'applique cà chaque rangée du tableau; et z(r,M)vérifie donc si Mc'est une carte valide.

Malheureusement, le format d'entrée requis pour faire ce travail directement est déraisonnable, j'ai donc également dû inclure un analyseur (qui représente probablement plus de code que le moteur de règles réel, et la plupart du temps consacré au débogage; le moteur de règles du démineur fonctionnait à peu près) première fois, mais l'analyseur était plein de thinkos). qconvertit une seule cellule entre un code de caractère et notre format. convertit une ligne du plateau (en laissant une cellule connue pour ne pas être une mine, mais avec un nombre inconnu de mines voisines, à chaque bord de la ligne comme frontière);x/ylpconvertit la carte entière (y compris la bordure inférieure, mais à l'exclusion de la bordure supérieure). Toutes ces fonctions peuvent être exécutées vers l'avant ou vers l'arrière, ce qui permet d'analyser et d'imprimer la carte à la fois. (Il y a des agitations agaçantes avec le troisième argument de p, qui spécifie la largeur de la carte; c'est parce que Prolog n'a pas de type de matrice, et si je ne contrains pas la carte à être rectangulaire, le programme entrera dans une boucle infinie essayant des bordures progressivement plus larges autour de la planche.)

mest la principale fonction de résolution du démineur. Il analyse la chaîne d'entrée, générant une carte avec une bordure correcte (en utilisant le cas récursif de ppour convertir la majeure partie de la carte, puis en appelant directement le cas de base pour générer la bordure supérieure, qui a la même structure que la bordure inférieure). Ensuite, il appellez(r,[R|M])pour exécuter le moteur de règles du démineur, qui (avec ce modèle d'appel) devient un générateur générant uniquement des cartes valides. À ce stade, la carte est toujours exprimée comme un ensemble de contraintes, ce qui est potentiellement gênant pour nous; nous pourrions peut-être avoir un seul ensemble de contraintes qui pourraient représenter plus d'un conseil. De plus, nous n'avons encore spécifié nulle part que chaque carré contient au plus une mine. En tant que tel, nous devons explicitement "réduire la forme d'onde" de chaque carré, en exigeant qu'il s'agisse spécifiquement d'une mine (unique) ou d'une mine non, et la manière la plus simple de le faire est de la faire passer par l'analyseur vers l'arrière (le var(V)sur le q(63,V)le boîtier est conçu pour empêcher le ?boîtier de tourner en arrière, et ainsi l'analyse de la carte force à être pleinement connue). Enfin, nous renvoyons la planche analysée dem; mdevient ainsi un générateur qui prend une carte partiellement inconnue et génère toutes les cartes connues qui lui correspondent.

C'est vraiment suffisant pour résoudre le démineur, mais la question demande explicitement de vérifier s'il y a exactement une solution, plutôt que de trouver toutes les solutions. En tant que tel, j'ai écrit un prédicat supplémentaire squi convertit simplement le générateur men un ensemble, puis affirme que l'ensemble a exactement un élément. Cela signifie que sretournera truey ( yes) s'il y a en effet exactement une solution, ou falsey ( no) s'il y en a plus d'une ou moins d'une.

dne fait pas partie de la solution et n'est pas inclus dans le bytecount; c'est une fonction pour imprimer une liste de chaînes comme s'il s'agissait d'une matrice, ce qui permet d'inspecter les cartes générées par m(par défaut, GNU Prolog imprime les chaînes comme une liste de codes ASCII, car il traite les deux comme synonymes; ce format est assez difficile à lire). Il est utile lors des tests ou si vous souhaitez l'utiliser mcomme un solveur de démineur pratique (car il utilise un solveur de contraintes, il est très efficace).

Haskell, 193 169 168 octets

c '?'="*!"
c x=[x]
g x|t<-x>>" ",w<-length(words x!!0)+1=1==sum[1|p<-mapM c$t++x++t,and[sum[1|m<-[-1..1],n<-[j-w,j,j+w],p!!(m+n)=='*']==read[d]|(j,d)<-zip[0..]p,d>'/']]

Exemple d'utilisation: g "1121 1??* 12?* 0122"-> True.

Comment ça marche: faites la liste de toutes les cartes possibles avec les ?remplacées par *ou !( !signifie ignorer plus tard). Cela se fait via mapM c, mais avant de préfixer et d'ajouter un tas d'espaces à la chaîne d'entrée afin que notre indexation ne soit pas hors de portée. Pour chaque vérification du conseil d'administration si elle est une carte valide en boucle sur tous les éléments (index j) et si elle est un certain nombre ( d>'/') aussi par rapport à ses voisins (indice n, m), comptez le *et comparer au nombre. Enfin, vérifiez la longueur de la liste des cartes valides.

Mathematica, 214 192 190 190 180 176 174 168 165 165 octets

0&/@Cases[b="*";If[!FreeQ[#,q="?"],(x#0@MapAt[x&,#,#&@@#~Position~q])/@{b,0},BlockMap[If[#[[2,2]]==b,b,Count[#,b,2]]&,#~ArrayPad~1,{3,3},1]]&@#,#/.q->_,All]=={0}&

Contient U + F4A1 (usage privé). Cette fonction sans nom trouve toutes les combinaisons possibles pour "?"(c'est-à-dire remplacer tous les "?"s par "*"ou0 ) et vérifie s'il n'y a qu'une seule solution valide.

Explication

b="*";

Réglez bsur "*".

!FreeQ[#,q="?"]

Définissez qla chaîne "?". Vérifiez s'il y en a "?"dans l'entrée.

If[ ..., (x#0 ... ,0}, BlockMap[ ... ]]

Si True...

(x#0@MapAt[x&,#,#&@@#~Position~q])/@{b,0}

Remplacez la première occurrence de q(= "?") par b(= "*") ou 0(c'est-à-dire deux sorties) et appliquez à nouveau la fonction entière.

Si False...

#~ArrayPad~1

Remplissez l'entrée avec une couche de 0.

BlockMap[If[#[[2,2]]==b,b,Count[#,b,2]]&, ... ,{3,3},1]

Partitionnez l'entrée en 3 x 3 matrices avec décalage 1. Pour chaque partition, appliquez une fonction telle que si la valeur médiane est b(= "*"), la sortie est la b(= "*"), et si la valeur médiane n'est pas b(= "*"), la sortie est le nombre de b(= "*") dans l'entrée. Cette étape réévalue toutes les cellules numériques.

Cases[ ... ,#/.q->_,All]

À partir de tous les résultats, trouvez ceux qui correspondent à l'entrée

0&/@ ... =={0}

Vérifiez si l'entrée est de longueur 1.

Perl, 215 octets

213 octets de code + -p0drapeaux (2 octets).

/.*/;$c="@+";$_=A x$c."
$_".A x$c;s/^|$/A/mg;sub t{my($_)=@_;if(/\?/){for$i(0..8,"*"){t(s/\?/$i/r)}}else{$r=1;for$i(/\d/g){$r&=!/(...)[^V]{$c}(.$i.)[^V]{$c}(...)(??{"$1$2$3"=~y%*%%!=$i?"":R})/}$e+=$r}}t$_;$_=$e==1

L'idée du code est de tester toutes les possibilités et de voir s'il y en a une et une seule qui mène à une carte entièrement remplie et valide.

Plus lisible, le code ressemble à:

/.*/ ; $ c = "@ +" ; # compte la taille d'une ligne. 
$ _ = A x $ c . "\ n $ _" . A x $ c ; # ajoutez une ligne de "A" au début et une autre à la fin. 
s / ^ | $ / A / mg ; # ajoutez un "A" au début et à la fin de chaque ligne.                     

# La fonction qui résout réellement le problème sub t { my $ _ = pop ; # Obtenez le paramètre, stockez-le dans $ _ (argument par défaut pour regex). if ( / \? / ) { # s'il y a un autre caractère inconnu. pour $ i ( 0 .. 8 , "*" ) { # essayez toutes les possibilités 
            t ( s / \? / $ i / r ) # appel récursif où le premier caractère inconnu a été remplacé } } else {
 
     
        
            
        
     # plus de caractère inconnu, donc ici nous vérifions si la carte est valide 
        $ r = 1 ; # si r == 1 à la fin, alors le tableau est valide, sinon ce n'est pas pour $ i ( / \ d / g ) { # pour chaque numéro présent du tableau # le regex suivant vérifie s'il y a un nombre entouré par # trop ou trop peu de mines. # (comment ça marche: magique!) 
         $ r & =! /(...){^V{{$c}(.$i.)[^V{{$c}(...)(??{"$1$2$3"=~y%*%%! = $ i? "": R}) / } 
        $ e + = $ r # Incrémente le nombre de cartes valides. } } 
t $ _ ;  
          
            
            
             
        
    
 # Appelle la fonction précédente 
$ _ = $ e == 1 # Vérifie s'il n'y a qu'une seule carte valide ($ _ est implicitement imprimé grâce au drapeau -p). 

À propos de l'expression régulière au milieu:

/(...)[^V]{$c}(.$i.)[^V]{$c}(...)(??{"$1$2$3"=~y%*%%!=$i?"":R})/

Notez que [^V]signifie simplement "n'importe quel caractère, y compris \ n".
L'idée est donc: 3 caractères sur une ligne, puis 3 sur la suivante (avec $iau milieu), puis 3 sur la suivante. ces 3 groupes de 3 nombres sont alignés, grâce à [^V]{$c}et le nombre qui nous intéresse est au milieu.
Et puis, "$1$2$3"=~y%*%%compte le nombre de *(bombes) parmi ces 9 caractères: si c'est différent de $i, nous ajoutons une chaîne vide pour correspondre ( ""=> correspondance instantanée, l'expression régulière renvoie vrai), sinon, nous forçons un échec en essayant de faire correspondre R( qui ne peut pas être dans la chaîne).
Si les matchs regex, le conseil d' administration n'est pas valide, nous avons donc mis $rà 0avec$r&=!/.../ .
Et c'est pourquoi nous en ajoutonsApartout autour de chaque ligne: nous n'avons donc pas à nous soucier des bords des cas de nombres qui sont près des bords de la planche: ils auront Acomme voisins, qui ne sont pas des mines (bien sûr, à peu près n'importe quel char pourrait avoir du travail, J'ai choisi A).

Vous pouvez exécuter le programme à partir de la ligne de commande comme ça:

perl -p0E '/.*/;$c="@+";$_=A x$c."\n$_".A x$c;s/^|$/A/mg;sub t{my($_)=@_;if(/\?/){for$i(0..8,"*"){t(s/\?/$i/r)}}else{$r=1;for$i(/\d/g){$r&=!/(...)[^V]{$c}(.$i.)[^V]{$c}(...)(??{"$1$2$3"=~y%*%%!=$i?"":R})/}$e+=$r}}t$_;$_=$e==1' <<< "1121
1??*
12?*
0122"

La complexité ne pourrait pas être pire: c'est O(m*9^n)où nest le nombre de ?sur la carte, et mest le nombre de cellules sur la carte (sans compter la complexité de l'expression régulière au milieu, ce qui est probablement assez mauvais). Sur ma machine, cela fonctionne assez rapidement jusqu'à 4 ?, et commence à être plus lent 5, prend quelques minutes pour 6, et je n'ai pas essayé de plus grands nombres.

JavaScript (ES6), 221 229

g=>(a=>{for(s=i=1;~i;g.replace(x,c=>a[j++],z=j=0).replace(/\d/g,(c,p,g)=>([o=g.search`
`,-o,++o,-o,++o,-o,1,-1].map(d=>c-=g[p+d]=='*'),z|=c)),s-=!z)for(i=a.length;a[--i]='*?'[+(c=a[i]<'?')],c;);})(g.match(x=/\?/g)||[])|!s

Si toutes les entrées sont censées être valides - c'est-à-dire avec au moins 1 solution - alors je peux enregistrer un octet en changeant s==1avecs<2

Moins golfé

g=>{
  a = g.match(/\?/g) || []; // array of '?' in a
  s = 1; // counter of solutions
  for(i=0; ~i;) // loop to find all configurations of ? and *
  {
    // get next configuration
    for(i = a.length; a[--i] = '*?'[+( c = a[i] < '?')], c; );
    z = 0; // init at 0, must stay 0 if all cells count is ok
    g
    .replace(/\?/g,c=>a[j++],j=0) // put ? and * at right places
    .replace(/\d/g,(c,p,g)=>(
       // look for mines in all 8 directions
       // for each mine decrease c
       // if c ends at 0, then the count is ok
       [o=g.search`\n`,-o,++o,-o,++o,-o,1,-1].map(d=>c-=g[p+d]=='*'),
       z|=c // z stays at 0 if count is ok
    )) // check neighbour count
    s-=!z // if count ok for all cells, decrement number of solutions
  }
  return s==0 // true if exactly one solution found
}

Tester

F=
g=>(a=>{for(s=i=1;~i;g.replace(x,c=>a[j++],z=j=0).replace(/\d/g,(c,p,g)=>([o=g.search`
`,-o,++o,-o,++o,-o,1,-1].map(d=>c-=g[p+d]=='*'),z|=c)),s-=!z)for(i=a.length;a[--i]='*?'[+(c=a[i]<'?')],c;);})(g.match(x=/\?/g)||[])|!s

out=x=>O.textContent+=x+'\n'

Solvable=['1121\n1??*\n12?*\n0122'
,'1110\n1???\n1110\n0000'
,'1110\n3???\n??20\n*310'
,'****\n****\n****\n****'
,'0000\n0000\n0000\n0000'
,'1100\n*100\n2321\n??*2\n13*2\n1221\n1*10\n1110'
,'1121\n2*??\n2*31\n2220\n1*10']
Unsolvable=['1110\n2*31\n3*??\n2*4?\n112?'
,'01??11*211\n12??2323*1\n1*33*2*210\n12?2122321\n13?3101**1\n1***101221'
,'1***\n3*52\n2*31\n12??\n02??\n01??'
,'00000111\n000012*1\n00001*21\n22101110\n**100111\n?31123*1\n?311**31\n**113*20']
out('Solvable')
Solvable.forEach(t=>out(t+'\n'+F(t)+'\n'))
out('Unsolvable')
Unsolvable.forEach(t=>out(t+'\n'+F(t)+'\n'))

<pre id=O></pre>

JavaScript (Node.js) , 167 octets

s=>g=(r=c='',[p,...q]=s,w)=>w?0:p?(g(r+0,q,p=='*')+g(r+1,q,1/p),c==1):c-=-![...s].some((p,i)=>p>' '&&[-1,1,-q,-1-q,-2-q,q,q+1,q+2].map(j=>p-=~~r[i+j])|p,q=s.search`
`)

Essayez-le en ligne!

Bien que op dise "l'entrée sera toujours rectangulaire, a au moins une solution", le faux échantillon 3 ne correspond pas, donc j'ai toujours besoin d'une solution, pas <2

s=>(        // p.s. Here "block" can also mean \n
  c=0,          // possible mine count
  g=(           // recursive
    r='',       // mine states
    [p,...q]=s, // known info to check possible state for a block
    w           // invert condition, stop if true
  )=>
    w?0:
      p?(       // for each block
        g(r+0,q,p=='*')+   // possibly not bomb if doesn't say so
        g(r+1,q,1/p),      // number/newline can't be bomb
        c==1               // only one bomb
      ):
        c-=-![...s].some(  // no block doesn't satisfy
          (p,i)=>
            p>' '&& // \n don't mean number
                    // other symbols turn into NaN when counting
            [-1,1,-q,-1-q,-2-q,q,q+1,q+2].map(j=>p-=~~r[i+j])
                    // subtract each neighbor, OOB = 0
            |p,     // difference between intended and actual
            q=s.search('\n') // how many blocks in a line
        )
)