Campo Minado é um jogo de quebra-cabeça popular, onde você deve descobrir quais peças são "minas" sem clicar nessas peças. Em vez disso, você clica em blocos próximos para revelar o número de minas adjacentes. Uma desvantagem do jogo é que é possível acabar em um cenário em que há várias respostas válidas e você pode apenas adivinhar. Por exemplo, considere a seguinte placa:

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

Nesse formato, um número representa o número de minas adjacentes, um *representa uma mina conhecida e um "?" representa uma mina em potencial. O lamentável desse quebra-cabeça em particular é que existem quatro soluções possíveis distintas e 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*

Isso significa que o conselho é insolúvel . Aqui está um exemplo de uma placa solucionável :

1121
1??*
12?*
0122

Esta placa é solucionável porque existe apenas uma solução válida possível:

1121
1*4*
12**
0122

Sua tarefa é escrever um programa ou função que use uma placa de caça-minas válida e determine se é solucionável ou não. Por "placa de caça-minas válida", quero dizer que a entrada sempre será retangular, terá pelo menos uma solução e não conterá caracteres inválidos.

Sua entrada pode ser uma matriz de caracteres, uma matriz de cadeias, uma cadeia contendo novas linhas, etc. A saída deve ser um valor verdadeiro, se for solucionável, e um valor falso, se não for. Não estou extremamente preocupado com o desempenho, mas sua solução deve teoricamente funcionar para qualquer tamanho de entrada.

Como sempre, as brechas padrão se aplicam e a solução mais curta em bytes vence!

Exemplos:

Os seguintes exemplos são todos solucionáveis:

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

Os exemplos a seguir são todos insolúveis:

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),[_]).

Um predicado extra que pode ser útil para testes (não faz parte do envio):

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

O Prolog é definitivamente o idioma certo para resolver esta tarefa do ponto de vista prático. Este programa praticamente estabelece as regras do Minesweeper e permite que o solucionador de restrições do GNU Prolog resolva o problema a partir daí.

ze isão funções utilitárias ( zrealiza uma espécie de operação semelhante a dobra, mas em conjuntos de três elementos adjacentes em vez de 2; itranspõe 3 listas de n elementos para uma lista de n 3 tuplas). Armazenamos internamente uma célula como , onde x é 1 para uma mina e 0 para uma não mina e y é o número de minas adjacentes; expressa essa restrição no quadro. aplica - se a todas as linhas do tabuleiro; e assim verifica se é um quadro válido.x/ycrcz(r,M)M

Infelizmente, o formato de entrada necessário para fazer esse trabalho diretamente não é razoável, então eu também precisei incluir um analisador (que provavelmente é responsável por mais código do que o mecanismo de regras real e a maior parte do tempo gasto na depuração; o mecanismo de regras do Minesweeper praticamente funcionou primeira vez, mas o analisador estava cheio de pensamentos). qconverte uma única célula entre um código de caractere e nosso formato. converte uma linha do tabuleiro (deixando uma célula que se sabe não ser uma mina, mas com um número desconhecido de minas vizinhas, em cada extremidade da linha como uma borda);x/ylpconverte o quadro inteiro (incluindo a borda inferior, mas excluindo a borda superior). Todas essas funções podem ser executadas para frente ou para trás, portanto, podem analisar e imprimir o quadro de maneira bonita. (Há algumas oscilações irritantes com o terceiro argumento para p, que especifica a largura da placa; isso ocorre porque o Prolog não possui um tipo de matriz e, se eu não restringir a placa a ser retangular, o programa entrará em um loop infinito tentando bordas progressivamente mais amplas ao redor do quadro.)

mé a principal função de resolução do Campo Minado. Ele analisa a sequência de entrada, gerando uma placa com uma borda correta (usando o caso recursivo de ppara converter a maior parte da placa e chamando o caso base diretamente para gerar a borda superior, que tem a mesma estrutura da borda inferior). Então chamaz(r,[R|M])para executar o mecanismo de regras do Campo Minado, que (com esse padrão de chamada) se torna um gerador que gera apenas placas válidas. Nesse ponto, o conselho ainda é expresso como um conjunto de restrições, o que é potencialmente estranho para nós; talvez pudéssemos ter um único conjunto de restrições que poderiam representar mais de uma diretoria. Além disso, ainda não especificamos em nenhum lugar que cada quadrado contenha no máximo uma mina. Como tal, precisamos explicitamente "recolher a forma de onda" de cada quadrado, exigindo que seja especificamente uma mina (única) ou uma não mina, e a maneira mais fácil de fazer isso é executá-la no analisador de trás para a frente ( var(V)no q(63,V)A caixa foi projetada para impedir que a ?caixa se mova para trás e, portanto, a separação da placa o força a ser totalmente conhecida). Finalmente, retornamos o quadro analisado dem; mtorna-se assim um gerador que pega uma placa parcialmente desconhecida e gera todas as placas conhecidas consistentes com ela.

Isso é realmente suficiente para resolver o Campo Minado, mas a pergunta pede explicitamente para verificar se existe exatamente uma solução, em vez de encontrar todas as soluções. Como tal, escrevi um predicado extra sque simplesmente converte o gerador mem um conjunto e, em seguida, afirma que o conjunto possui exatamente um elemento. Isso significa que sretornará yesverdade ( ) se houver de fato exatamente uma solução ou falsey ( no) se houver mais de uma ou menos de uma.

dnão faz parte da solução e não está incluído no bytecount; é uma função para imprimir uma lista de strings como se fosse uma matriz, o que possibilita inspecionar as placas geradas por m(por padrão, o GNU Prolog imprime strings como uma lista de códigos ASCII, porque trata os dois como sinônimos; este formato é bastante difícil de ler). É útil durante o teste ou se você deseja usar mcomo um solucionador prático do Campo Minado (porque usa um solucionador de restriçõ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>'/']]

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

Como funciona: faça uma lista de todas as placas possíveis com as ?substituídas por um *ou !( !significa ignorar mais tarde). Isso é feito via mapM c, mas antes de adicionar e acrescentar vários espaços à string de entrada, para que nossa indexação não fique fora do intervalo. Para cada tal verificação bordo se é uma placa válida por looping sobre todos os elementos (índice j) e se é um número ( d>'/') também em relação aos seus vizinhos (índice n, m), contar o *e comparar com o número. Por fim, verifique o comprimento da lista de painéis válidos.

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

Contém U + F4A1 (uso privado). Esta função sem nome localiza todas as combinações possíveis para "?"(ou seja, substitui todos os "?"s por "*"ou 0) e verifica se há apenas uma solução válida.

Explicação

b="*";

Defina bcomo "*".

!FreeQ[#,q="?"]

Defina qpara a sequência "?". Verifique se há "?"na entrada.

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

Se True...

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

Substitua a primeira ocorrência de q(= "?") por b(= "*") ou 0( ou seja, duas saídas) e aplique toda a função novamente.

Se False...

#~ArrayPad~1

Almofada a entrada com uma camada de 0.

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

Particione a entrada em matrizes 3 x 3 com deslocamento 1. Para cada partição, aplique uma função tal que, se o valor do meio for b(= "*"), a saída for o b(= "*"), e se o valor do meio não for b(= "*"), o output é o número de b(= "*") na entrada. Esta etapa reavalia todas as células numéricas.

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

De todos os resultados, encontre os que correspondem à entrada

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

Verifique se a entrada tem comprimento 1.

Perl, 215 bytes

213 bytes de código + -p0sinalizadores (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

A idéia do código é testar todas as possibilidades e verificar se existe uma e apenas uma que leva a um quadro totalmente preenchido válido.

Mais legível, o código se parece com:

/.*/ ; $ c = "@ +" ; # conte o tamanho de uma linha. 
$ _ = A x $ c . "\ n $ _" . A x $ c ; # adicione uma linha de "A" no início e outra no final. 
s / ^ | $ / A / mg ; # adicione um "A" no início e no final de cada linha.                     

# A função que realmente resolve o problema sub t { my $ _ = pop ; # Obtenha o parâmetro, armazene-o em $ _ (argumento padrão para regex). if ( / \? / ) { # se houver outro caractere desconhecido. para $ i ( 0 .. 8 , "*" ) { # tente todas as possibilidades 
            t ( s / \? / $ i / r ) # chamada reccursiva em que o primeiro caractere desconhecido foi substituído } } else {
 
     
        
            
        
     # não é mais um personagem desconhecido, então aqui verificamos se o quadro é válido 
        $ r = 1 ; # if r == 1 no final, o quadro é válido, caso contrário, não é para $ i ( / \ d / g ) { # para cada número presente no quadro # o seguinte regex verifica se há um número entre eles por minas demais ou muito pequenas. # (como funciona: mágica!) 
         $ r & =! /(...)[^V{{cc(($i.))^V{{$c}(...)(??{"$1$2$3"=~y%*%%! = $ i? "": R}) / } 
        $ e + = $ r # Incrementa o número de placas válidas. } } 
t $ _ ;  
          
            
            
             
        
    
 # Chame a função anterior 
$ _ = $ e == 1 # Verifica se existe apenas uma placa válida ($ _ é impressa implicitamente graças ao sinalizador -p). 

Sobre a regex no meio:

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

Note que [^V]apenas significa "qualquer caractere, incluindo \ n".
Portanto, a idéia é: 3 caracteres em uma linha, depois 3 na próxima (com $ino meio) e depois 3 na próxima. esses 3 grupos de 3 números estão alinhados, graças ao [^V]{$c}número em que estamos interessados ​​está no meio.
E, então, "$1$2$3"=~y%*%%conta o número de *(bombas) entre esses 9 caracteres: se for diferente $i, adicionamos uma string vazia para corresponder ( ""=> correspondência instantânea, a regex retorna true); caso contrário, forçamos uma falha ao tentar corresponder R( que não pode estar na string).
Se os jogos de regex, então a bordo não é válido, então vamos definir $ra 0com $r&=!/.../.
E é por isso que adicionamos algunsAem todos os lugares em torno de cada linha: para que não tenhamos de nos preocupar com casos extremos de números que estão próximos dos limites do quadro: eles terão Acomo vizinhos, que não são minas (é claro, praticamente qualquer caractere poderia ter trabalho, Eu escolhi A).

Você pode executar o programa na linha de comando assim:

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"

A complexidade não poderia ser pior: é O(m*9^n)onde nestá o número de ?no quadro e mo número de células no quadro (sem contar a complexidade da regex no meio, o que provavelmente é muito ruim). Na minha máquina, ele funciona muito rápido para até 4 ?e começa a ficar mais lento 5, leva alguns minutos para 6 e não tentei números maiores.

JavaScript (ES6), 222222

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

Se toda a entrada for válida - ou seja, com pelo menos 1 solução -, eu posso salvar uma alteração de byte s==1coms<2

Menos golfe

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
}

Teste

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

Experimente online!

Embora op diga "a entrada sempre será retangular, tenha pelo menos uma solução", a amostra falsa 3 não corresponde, por isso ainda preciso de 1 solução, não <2 solução

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