Buscaminas es un popular juego de rompecabezas en el que debes descubrir qué fichas son "minas" sin hacer clic en esas fichas. En cambio, haces clic en las fichas cercanas para revelar la cantidad de minas adyacentes. Una desventaja del juego es que es posible terminar en un escenario donde hay múltiples respuestas válidas y solo puedes adivinar. Por ejemplo, tome la siguiente tabla:

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

En este formato, un número representa el número de minas adyacentes, un *representa una mina conocida y un "?" representa una mina potencial. Lo desafortunado de este rompecabezas en particular es que hay cuatro soluciones potenciales distintas y válidas :

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*

Esto significa que el tablero no tiene solución . Aquí hay un ejemplo de una placa solucionable :

1121
1??*
12?*
0122

Esta placa es solucionable porque solo hay una posible solución válida:

1121
1*4*
12**
0122

Su tarea es escribir un programa o función que tome un tablero de buscaminas válido y determine si es solucionable o no. Por "tablero de buscaminas válido", quiero decir que la entrada siempre será rectangular, tendrá al menos una solución y no contendrá ningún carácter no válido.

Su entrada puede ser una matriz de caracteres, una matriz de cadenas, una cadena que contiene nuevas líneas, etc. La salida debe ser un valor verdadero si es solucionable y un valor falso si no lo es. No estoy extremadamente preocupado por el rendimiento, pero su solución debe funcionar teóricamente para cualquier entrada de tamaño.

Como de costumbre, se aplican las lagunas estándar y gana la solución más corta en bytes.

Ejemplos:

Los siguientes ejemplos tienen solución:

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

Los siguientes ejemplos son todos irresolubles:

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 bytes

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 predicado adicional que puede ser útil para la prueba (no forma parte del envío):

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

Prolog es definitivamente el lenguaje correcto para resolver esta tarea desde el punto de vista práctico. Este programa simplemente establece las reglas de Buscaminas y permite que el solucionador de restricciones de GNU Prolog resuelva el problema desde allí.

zy ison funciones de utilidad ( zrealiza una especie de operación tipo pliegue pero en conjuntos de tres elementos adyacentes en lugar de 2; itranspone 3 listas de n elementos en una lista de n 3-tuplas). Almacenamos internamente una celda como , donde x es 1 para una mina y 0 para una no mina, e y es el número de minas adyacentes; expresa esta restricción en el tablero. se aplica a cada fila del tablero; y entonces verifica si es un tablero válido.x/ycrcz(r,M)M

Desafortunadamente, el formato de entrada requerido para que esto funcione directamente no es razonable, por lo que también tuve que incluir un analizador (que probablemente representa más código que el motor de reglas real, y la mayor parte del tiempo dedicado a la depuración; el motor de reglas del Buscaminas funcionaba bastante bien) primera vez, pero el analizador estaba lleno de thinkos). qConvierte una sola celda entre un código de caracteres y nuestro formato. convierte una línea del tablero (dejando una celda que se sabe que no es una mina, pero con un número desconocido de minas vecinas, en cada borde de la línea como borde);x/ylpconvierte todo el tablero (incluido el borde inferior, pero excluyendo el superior). Todas estas funciones pueden ejecutarse hacia adelante o hacia atrás, por lo tanto, pueden analizar e imprimir el tablero. (Hay algunas molestias molestas con el tercer argumentop, que especifica el ancho del tablero; Esto se debe a que Prolog no tiene un tipo de matriz, y si no restrinjo el tablero para que sea rectangular, el programa entrará en un bucle infinito intentando bordes progresivamente más amplios alrededor del tablero).

mes la principal función de resolución de Buscaminas. Analiza la cadena de entrada, genera un tablero con un borde correcto (mediante el uso del caso recursivo de ppara convertir la mayor parte del tablero, luego llama al caso base directamente para generar el borde superior, que tiene la misma estructura que el borde inferior). Entonces llamaz(r,[R|M])para ejecutar el motor de reglas Buscaminas, que (con este patrón de llamada) se convierte en un generador que genera solo tableros válidos. En este punto, el tablero todavía se expresa como un conjunto de restricciones, lo cual es potencialmente incómodo para nosotros; quizás podríamos tener un solo conjunto de restricciones que podrían representar más de una placa. Además, aún no hemos especificado en ningún lugar que cada cuadrado contenga como máximo una mina. Como tal, tenemos que explícitamente "colapsar la forma de onda" de cada cuadrado, lo que requiere que sea específicamente un (único) mina o un nonmine, y la forma más sencilla de hacerlo es ejecutar a través de las revés analizador (el var(V)de la q(63,V)El estuche está diseñado para evitar que el ?estuche corra hacia atrás y, por lo tanto, el análisis del tablero obliga a que sea completamente conocido). Finalmente, devolvemos el tablero analizado dem; mpor lo tanto, se convierte en un generador que toma una placa parcialmente desconocida y genera todas las placas conocidas compatibles con ella.

Eso es realmente suficiente para resolver el Buscaminas, pero la pregunta explícitamente es verificar si hay exactamente una solución, en lugar de encontrar todas las soluciones. Como tal, escribí un predicado adicional sque simplemente convierte el generador men un conjunto y luego afirma que el conjunto tiene exactamente un elemento. Esto significa que sdevolverá verdadero ( yes) si de hecho hay exactamente una solución, o falsey ( no) si hay más de uno o menos de uno.

dno es parte de la solución y no está incluido en el bytecount; es una función para imprimir una lista de cadenas como si fuera una matriz, lo que hace posible inspeccionar las placas generadas por m(de forma predeterminada, GNU Prolog imprime cadenas como una lista de códigos ASCII, porque trata a los dos como sinónimos; este formato es bastante difícil de leer) Es útil durante las pruebas, o si desea usarlo mcomo un solucionador de buscaminas práctico (porque usa un solucionador de restricciones, es altamente eficiente).

Haskell, 193 169 168 bytes

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>'/']]

Ejemplo de uso: g "1121 1??* 12?* 0122"-> True.

Cómo funciona: haga una lista de todos los tableros posibles con el ?reemplazado por uno *o !( !significa ignorar más adelante). Esto se hace a través de mapM c, pero antes de anteponer y agregar un montón de espacios a la cadena de entrada para que nuestra indexación no esté fuera de rango. Para cada uno de estos tableros, verifique si es un tablero válido haciendo un bucle sobre todos los elementos (índice j) y si es un número ( d>'/') también sobre sus vecinos (índice n, m), cuente *y compare con el número. Finalmente verifique la longitud de la lista de tablas válidas.

Mathematica, 214 192 190 180 176 174 168 165 bytes

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}&

Contiene U + F4A1 (uso privado). Esta función sin nombre busca todas las combinaciones posibles para "?"(es decir, reemplaza todas las "?"s con "*"o 0) y comprueba si solo hay una solución válida.

Explicación

b="*";

Establecer ba "*".

!FreeQ[#,q="?"]

Establecer qen la cadena "?". Compruebe si hay "?"en la entrada.

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

Si True...

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

Reemplace la primera aparición de q(= "?") con b(= "*") o 0(es decir, dos salidas), y aplique de nuevo toda la función.

Si False...

#~ArrayPad~1

Rellene la entrada con una capa de 0.

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

Particione la entrada en 3 x 3 matrices con desplazamiento 1. Para cada partición, aplique una función tal que si el valor medio es b(= "*"), la salida es el b(= "*"), y si el valor medio no es b(= "*"), el salida es el número de b(= "*") en la entrada. Este paso vuelve a evaluar todas las celdas numéricas.

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

De todos los resultados, encuentre los que coincidan con la entrada

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

Compruebe si la entrada es longitud 1.

Perl, 215 bytes

213 bytes de código + -p0banderas (2 bytes).

/.*/;$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

La idea del código es probar todas las posibilidades y ver si hay una y solo una que conduzca a un tablero completamente lleno que sea válido.

Más legible, el código se ve así:

/.*/ ; $ c = "@ +" ; # cuenta el tamaño de una línea.           
$ _ = A x $ c . "\ n $ _" . A x $ c ; # agregue una línea de "A" al principio y otra al final. 
s / ^ | $ / A / mg ; # agregue una "A" al principio y al final de cada línea.          

# La función que realmente resuelve el problema sub t { my $ _ = pop ; # Obtenga el parámetro, guárdelo en $ _ (argumento predeterminado para regex). if ( / \? / ) { # si hay otro carácter desconocido. para $ i ( 0 .. 8 , "*" ) { # prueba todas las posibilidades 
            t ( s / \? / $ i / r ) # llamada recursiva donde el primer personaje desconocido ha sido reemplazado } } más {
 
     
        
            
        
      # no más caracteres desconocidos, así que aquí verificamos si el tablero es válido 
        $ r = 1 ; # si r == 1 al final, entonces el tablero es válido, de lo contrario no es por $ i ( / \ d / g ) {  
          # por cada número presente en el tablero
             # el siguiente regex verifica si hay un número rodeado por # minas demasiado o muy poco. # (cómo funciona: ¡magia!) 
         $ r & =! /(...)[^Vfont>{$c}(.$i.)[^Vfont>{$c}(...)(??{"$1$2$3"=~y%*%%! = $ i? "": R}) / } 
        $ e + = $ r # Incrementa el número de tableros válidos. } } 
t $ _ ;
            
             
        
    
 # Llame a la función anterior 
$ _ = $ e == 1 # Comprueba si solo hay una placa válida ($ _ se imprime implícitamente gracias al indicador -p). 

Sobre la expresión regular en el medio:

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

Tenga en cuenta que [^V]solo significa "cualquier carácter, incluyendo \ n".
Entonces la idea es: 3 caracteres en una línea, luego 3 en el siguiente (con $ien el medio), luego 3 en el siguiente. esos 3 grupos de 3 números están alineados, gracias [^V]{$c}y el número que nos interesa está en el medio.
Y luego, "$1$2$3"=~y%*%%cuenta el número de *(bombas) entre esos 9 caracteres: si es diferente de $i, agregamos una cadena vacía para que coincida ( ""=> coincidencia instantánea, la expresión regular devuelve verdadero), de lo contrario, forzamos una falla al intentar hacer coincidir R( que no puede estar en la cadena).
Si los partidos de expresiones regulares, entonces la tarjeta no es válida, por lo que nos propusimos $ra 0con $r&=!/.../.
Y es por eso que agregamos algunosAen todas partes alrededor de cada línea: para que no tengamos que preocuparnos por los bordes de los números que están cerca de los bordes del tablero: tendrán Acomo vecinos, que no son minas (por supuesto, casi cualquier personaje podría tener trabajo, Yo elegí A)

Puede ejecutar el programa desde la línea de comando así:

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 complejidad no podría ser peor: es O(m*9^n)dónde nestá el número de ?en el tablero, y mes el número de celdas en el tablero (sin contar la complejidad de la expresión regular en el medio, que probablemente sea bastante mala). En mi máquina, funciona bastante rápido hasta 4 ?, y comienza a ser más lento 5, toma unos minutos para 6, y no intenté con números más grandes.

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 se espera que toda la entrada sea válida, es decir, con al menos 1 solución, entonces puedo guardar un byte cambiando s==1cons<2

Menos 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
}

Prueba

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 bytes

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`
`)

Pruébalo en línea!

Aunque op dice "la entrada siempre será rectangular, tenga al menos una solución", la muestra falsa 3 no coincide, por lo que todavía necesito 1 solución, no <2 solución

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
        )
)