Saper to popularna gra logiczna, w której musisz odkryć, które kafelki są „kopalniami”, bez klikania na te kafelki. Zamiast tego klikasz na pobliskie kafelki, aby odsłonić liczbę sąsiadujących min. Jednym minusem gry jest to, że można skończyć w scenariuszu, w którym istnieje wiele prawidłowych odpowiedzi i można się tylko domyślać. Na przykład weź następującą tablicę:

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

W tym formacie liczba reprezentuje liczbę sąsiednich min, *reprezentuje znaną minę i „?” reprezentuje potencjalną kopalnię. Niefortunną rzeczą w tej konkretnej układance jest to, że istnieją cztery różne i ważne potencjalne rozwiązania:

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*

Oznacza to, że plansza jest nierozwiązywalna . Oto przykład rozwiązywalnej planszy:

1121
1??*
12?*
0122

Tę tablicę można rozwiązać, ponieważ istnieje tylko jedno możliwe prawidłowe rozwiązanie:

1121
1*4*
12**
0122

Twoim zadaniem jest napisanie programu lub funkcji, która pobiera prawidłową tablicę trałowców i określa, czy jest ona do rozwiązania, czy nie. Przez „prawidłową planszę trałowca” rozumiem, że dane wejściowe będą zawsze prostokątne, mają co najmniej jedno rozwiązanie i nie będą zawierały żadnych nieprawidłowych znaków.

Dane wejściowe mogą być tablicą znaków, tablicą ciągów, ciągiem zawierającym znaki nowego wiersza itp. Wynik musi być prawdziwą wartością, jeśli można ją rozwiązać, i wartością fałszowania, jeśli nie jest. Nie martwię się zbytnio o wydajność, ale twoje rozwiązanie musi teoretycznie działać dla każdego rozmiaru wejściowego.

Jak zwykle obowiązują standardowe luki i wygrywa najkrótsze rozwiązanie w bajtach!

Przykłady:

Wszystkie poniższe przykłady można rozwiązać:

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

Następujących przykładów nie da się rozwiązać:

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 bajtów

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

Dodatkowy predykat, który może być przydatny do testowania (nie stanowi części zgłoszenia):

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

Prolog jest zdecydowanie właściwym językiem do rozwiązania tego zadania z praktycznego punktu widzenia. Ten program w zasadzie określa tylko zasady Saperów i umożliwia rozwiązanie problemu ograniczeniom GNU Prolog.

zi isą funkcjami użytkowymi ( zwykonuje rodzaj operacji składania, ale na zestawach trzech sąsiednich elementów zamiast 2; itransponuje 3 listy n elementów na listę n 3-krotek). Wewnętrznie przechowujemy komórkę jako , gdzie x wynosi 1 dla kopalni, a 0 dla kopalni, a y jest liczbą sąsiednich kopalń; wyraża to ograniczenie na tablicy. dotyczy każdego rzędu planszy; i dlatego sprawdza, czy jest to ważna tablica.x/ycrcz(r,M)M

Niestety format wejściowy wymagany do bezpośredniego działania tej funkcji jest nieuzasadniony, więc musiałem także dołączyć parser (który prawdopodobnie odpowiada za więcej kodu niż rzeczywisty silnik reguł i przez większość czasu spędzanego na debugowaniu; silnik reguł Saper właściwie działał za pierwszym razem, ale parser był pełen myśli). qkonwertuje pojedynczą komórkę między kodem znaków a naszym formatem. konwertuje jedną linię planszy (pozostawiając jedną komórkę, o której wiadomo, że nie jest kopalnią, ale z nieznaną liczbą sąsiadujących min, na każdej krawędzi linii jako granicę);x/ylpkonwertuje całą planszę (w tym dolną ramkę, ale wyłączając górną). Wszystkie te funkcje można uruchamiać do przodu lub do tyłu, dzięki czemu można zarówno analizować, jak i ładnie drukować tablicę. (Jest trochę denerwujące poruszanie się z trzecim argumentem do p, który określa szerokość tablicy; dzieje się tak, ponieważ Prolog nie ma typu matrycy, a jeśli nie ograniczę płytki do prostokątności, program przejdzie do nieskończona pętla próbująca stopniowo poszerzać granice wokół planszy.)

mjest główną funkcją rozwiązywania Saperów. Analizuje ciąg wejściowy, generując tablicę z poprawną ramką (poprzez użycie rekurencyjnego przypadku pdo konwersji większości tablicy, a następnie wywołanie skrzynki bazowej bezpośrednio w celu wygenerowania górnej granicy, która ma taką samą strukturę jak dolna granica). Potem dzwoniz(r,[R|M])do uruchomienia silnika reguł Saper, który (przy tym wzorcu wywołań) staje się generatorem generującym tylko prawidłowe tablice. W tym momencie tablica jest nadal wyrażana jako zestaw ograniczeń, co jest dla nas potencjalnie niezręczne; moglibyśmy mieć jeden zestaw ograniczeń, które mogłyby reprezentować więcej niż jedną tablicę. Ponadto nie określono jeszcze nigdzie, że każdy kwadrat zawiera co najwyżej jedną kopalnię. W związku z tym musimy wyraźnie „zwinąć kształt fali” każdego kwadratu, wymagając, aby była to konkretnie (pojedyncza) kopalnia lub kopalnia, a najłatwiejszym sposobem na to jest przepuszczenie go przez parser do tyłu ( var(V)na q(63,V)obudowa jest zaprojektowana w taki sposób, aby zapobiec ?przesuwaniu się obudowy do tyłu, a zatem odłożenie płyty wymusza jej pełną znajomość). Na koniec zwracamy przeanalizowaną tablicęm; mw ten sposób staje się generatorem, który bierze częściowo nieznaną płytkę i generuje wszystkie znane tablice z nią zgodne.

To naprawdę wystarczy, aby rozwiązać Saper, ale pytanie wyraźnie dotyczy sprawdzenia, czy istnieje dokładnie jedno rozwiązanie, zamiast znalezienia wszystkich rozwiązań. Jako taki napisałem dodatkowy predykat, sktóry po prostu przekształca generator mw zestaw, a następnie zapewnia, że ​​zestaw ma dokładnie jeden element. Oznacza to, że szwróci prawdę ( yes), jeśli rzeczywiście istnieje dokładnie jedno rozwiązanie, lub falsey ( no), jeśli istnieje więcej niż jedno lub mniej niż jedno.

dnie jest częścią rozwiązania i nie jest uwzględniony w bajcie; jest to funkcja służąca do drukowania listy ciągów, tak jakby to była matryca, co umożliwia sprawdzenie wygenerowanych kart m(domyślnie GNU Prolog drukuje ciągi jako listę kodów ASCII, ponieważ traktuje oba synonimy; ten format jest dość trudny do odczytania). Jest przydatny podczas testowania lub jeśli chcesz używać go mjako praktycznego solvera Saperów (ponieważ używa solvera ograniczeń, jest bardzo wydajny).

Haskell, 193 169 168 bajtów

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

Przykład użycia: g "1121 1??* 12?* 0122"-> True.

Jak to działa: make lista wszystkich możliwych desek z ?wyrazami albo *albo !( !środki ignorować później). Odbywa się to poprzez mapM c, ale zanim dodamy i dodamy kilka spacji do ciągu wejściowego, aby nasze indeksowanie nie było poza zakresem. Dla każdej takiej tablicy sprawdź, czy jest to poprawna tablica, zapętlając wszystkie elementy (indeks j), a jeśli jest liczbą ( d>'/') również nad sąsiadami (indeks n, m), policz *i porównaj z liczbą. Na koniec sprawdź długość listy prawidłowych tablic.

Mathematica 214 192 190 180 176 174 168 165 bajtów

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

Zawiera U + F4A1 (użytek prywatny). Ta nienazwana funkcja znajduje wszystkie możliwe kombinacje dla "?"(tj. Zastępuje wszystkie "?"s "*"lub 0) i sprawdza, czy istnieje tylko jedno prawidłowe rozwiązanie.

Wyjaśnienie

b="*";

Ustaw bna "*".

!FreeQ[#,q="?"]

Ustaw qciąg "?". Sprawdź, czy jest "?"na wejściu.

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

Jeśli True...

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

Zamień pierwsze wystąpienie q(= "?") na b(= "*") lub 0(tj. Dwa wyjścia) i zastosuj ponownie całą funkcję.

Jeśli False...

#~ArrayPad~1

Wypełnij wejście jedną warstwą 0.

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

Podziel dane wejściowe na macierze 3 x 3 z przesunięciem 1. Dla każdej partycji zastosuj funkcję taką, że jeśli środkowa wartość to b(= "*"), to wyjście to b(= "*"), a jeśli środkowa wartość nie jest b(= "*"), wyjście to liczba b(= "*") na wejściu. Ten krok ponownie ocenia wszystkie komórki liczbowe.

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

Ze wszystkich wyników znajdź te, które pasują do danych wejściowych

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

Sprawdź, czy wejście ma długość 1.

Perl, 215 bajtów

213 bajtów kodu + -p0flagi (2 bajty).

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

Ideą kodu jest przetestowanie każdej możliwości i sprawdzenie, czy istnieje jedna i tylko jedna, która prowadzi do w pełni wypełnionej planszy, która jest ważna.

Bardziej czytelny kod wygląda następująco:

/.*/ ; $ c = "@ +" ; # policz rozmiar linii. 
$ _ = A x $ c . „\ n $ _” . A x $ c ; # dodaj wiersz „A” na początku, a drugi na końcu. 
s / ^ | $ / A / mg ; # dodaj „A” na początku i na końcu każdej linii.                     

# Funkcja, która faktycznie rozwiązuje problem sub t { my $ _ = pop ; # Pobierz parametr, zapisz go w $ _ (domyślny argument do wyrażenia regularnego). if ( / \? / ) { # jeśli istnieje inny nieznany znak. dla $ i ( 0 .. 8 , „*” ) { # wypróbuj każdą możliwość 
            t ( s / \? / $ i / r ) # wywołanie rekurencyjne, w którym zastąpiono pierwszy nieznany znak } } else {
 
     
        
            
        
      # nie więcej nieznany znak, więc tutaj sprawdzamy, czy tablica jest poprawna 
        $ r = 1 ; # Jeśli r == 1 na końcu, a następnie rada jest ważne, w przeciwnym razie nie jest to dla $ i ( / \ d / g ) { # dla każdej liczby obecnych na pokładzie # następujące kontrole regex, jeśli nie jest otoczony jest liczbą przez # za dużo lub za mało min. # (jak to działa: magia!) 
         $ r & =! /(...)[^V]{$c}(.$i.)[^V]{$c}(...)(??{"$1$2$3"=~y%*%%! = $ i? "": R}) / } 
        $ e + = $ r # Zwiększ liczbę prawidłowych płyt. } } 
t $ _ ;  
          
            
            
             
        
    
 # Wywołaj poprzednią funkcję 
$ _ = $ e == 1 # Sprawdza, czy jest tylko jedna poprawna płyta ($ _ jest domyślnie drukowane dzięki opcji -p). 

O wyrażeniu regularnym w środku:

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

Pamiętaj, że [^V]oznacza „dowolny znak, w tym \ n”.
Pomysł jest następujący: 3 znaki na linii, następnie 3 na następnej (ze $iśrodkiem), a następnie 3 na następnej. te 3 grupy 3 liczb są wyrównane dzięki, [^V]{$c}a liczba, którą jesteśmy zainteresowani, znajduje się pośrodku.
A następnie "$1$2$3"=~y%*%%liczy liczbę *(bomb) wśród tych 9 znaków: jeśli jest różny od $i, dodajemy pusty ciąg do dopasowania ( ""=> natychmiastowe dopasowanie, wyrażenie regularne zwraca wartość true), w przeciwnym razie wymuszamy niepowodzenie, próbując dopasować R( który nie może być w ciągu).
Jeśli regex meczów, następnie płyta nie jest ważna, więc ruszyliśmy $rdo 0z $r&=!/.../.
I dlatego dodajemy trochęAwszędzie wokół każdej linii: więc nie musimy się martwić o przypadki liczb na krawędziach, które znajdują się w pobliżu krawędzi planszy: będą mieli Ajak sąsiedzi, którzy nie są kopalniami (oczywiście z grubsza każdy char może mieć pracę, Wybrałem A).

Możesz uruchomić program z wiersza poleceń w następujący sposób:

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"

Złożoność nie może być najgorsza: O(m*9^n)tutaj njest liczba ?na planszy i mliczba komórek na planszy (nie licząc złożoności wyrażenia regularnego w środku, co jest prawdopodobnie dość złe). Na mojej maszynie działa dość szybko dla maksymalnie 4 ?i zaczyna być wolniejszy 5, zajmuje 6 minut dla 6, a ja nie próbowałem większych liczb.

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

Jeśli oczekuje się, że wszystkie dane wejściowe będą poprawne - czyli z co najmniej 1 rozwiązaniem - to mogę zapisać zmianę bajtu za s==1pomocąs<2

Mniej golfa

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
}

Test

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 bajtów

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

Wypróbuj online!

Chociaż op mówi „dane wejściowe zawsze będą prostokątne, mają co najmniej jedno rozwiązanie”, fałszywa próbka 3 nie pasuje, więc wciąż potrzebuję 1 rozwiązania, a nie <2 rozwiązania

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