Minesweeper adalah permainan puzzle yang populer di mana Anda harus menemukan ubin mana yang merupakan "ranjau" tanpa mengklik ubin itu. Sebagai gantinya, Anda mengeklik ubin terdekat untuk mengungkap jumlah tambang yang berdekatan. Satu kelemahan tentang permainan ini adalah kemungkinan untuk berakhir dalam skenario di mana ada beberapa jawaban yang valid dan Anda hanya bisa menebak. Misalnya, ambil papan berikut:

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

Dalam format ini, angka mewakili jumlah tambang yang berdekatan, sebuah *mewakili tambang yang diketahui, dan "?" mewakili potensi tambang. Hal yang disayangkan tentang teka-teki khusus ini adalah bahwa ada empat solusi potensial yang berbeda dan valid :

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*

Ini berarti papan tidak terpecahkan . Berikut adalah contoh papan yang dapat dipecahkan :

1121
1??*
12?*
0122

Board ini dapat dipecahkan karena hanya ada satu solusi yang valid:

1121
1*4*
12**
0122

Tugas Anda adalah menulis baik program atau fungsi yang menggunakan papan kapal penyapu ranjau yang valid dan menentukan apakah dapat dipecahkan atau tidak. Dengan "papan kapal penyapu ranjau yang valid", maksud saya bahwa input akan selalu persegi panjang, memiliki setidaknya satu solusi, dan tidak mengandung karakter yang tidak valid.

Input Anda mungkin berupa array karakter, array string, string yang berisi baris baru, dll. Outputnya harus berupa nilai yang benar jika dapat dipecahkan dan nilai yang salah jika tidak. Saya tidak terlalu khawatir tentang kinerja, tetapi solusi Anda secara teoritis harus bekerja untuk input ukuran apa pun.

Seperti biasa, celah standar berlaku dan solusi terpendek dalam byte menang!

Contoh:

Contoh-contoh berikut semuanya dapat dipecahkan:

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

Semua contoh berikut tidak dapat dipecahkan:

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

Predikat tambahan yang mungkin berguna untuk pengujian (bukan bagian dari pengiriman):

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

Prolog jelas merupakan bahasa yang tepat untuk menyelesaikan tugas ini dari sudut pandang praktis. Program ini cukup banyak hanya menyatakan aturan Minesweeper dan memungkinkan pemecah kendala GNU Prolog memecahkan masalah dari sana.

zdan iadalah fungsi utilitas ( zmelakukan semacam operasi lipatan tetapi pada himpunan tiga elemen yang berdekatan, bukan 2; imentranspos 3 daftar elemen n ke dalam daftar n 3-tupel). Kami secara internal menyimpan sel sebagai , di mana x adalah 1 untuk tambang dan 0 untuk bukan tambang, dan y adalah jumlah tambang yang berdekatan; mengungkapkan kendala ini di papan tulis. berlaku untuk setiap baris papan; dan jadi memeriksa untuk melihat apakah papan yang valid.x/ycrcz(r,M)M

Sayangnya, format input yang diperlukan untuk membuat pekerjaan ini secara langsung tidak masuk akal, jadi saya juga harus menyertakan parser (yang mungkin menyumbang lebih banyak kode daripada mesin aturan aktual, dan sebagian besar waktu yang dihabiskan untuk debugging; mesin aturan Minesweeper cukup banyak bekerja pertama kali, tetapi parser itu penuh dengan thinkos). qmengkonversi sel tunggal antara kode karakter dan format kami . mengonversi satu baris papan (meninggalkan satu sel yang diketahui bukan tambang, tetapi dengan sejumlah ranjau yang berdekatan, di setiap tepi garis sebagai perbatasan);x/ylpmengkonversi seluruh papan (termasuk batas bawah, tetapi tidak termasuk yang paling atas). Semua fungsi ini dapat dijalankan baik maju atau mundur, sehingga dapat menguraikan dan mencetak papan. (Ada beberapa yang mengganggu dengan argumen ketiga p, yang menentukan lebar papan; ini karena Prolog tidak memiliki jenis matriks, dan jika saya tidak membatasi papan menjadi persegi panjang, program akan masuk ke loop tak terbatas mencoba semakin perbatasan yang lebih luas di sekitar papan.)

madalah fungsi pemecahan Minesweeper utama. Ini mem-parsing string input, menghasilkan papan dengan perbatasan yang benar (melalui menggunakan kasus rekursif puntuk mengkonversi sebagian besar papan, kemudian memanggil kasing langsung untuk menghasilkan perbatasan atas, yang memiliki struktur yang sama dengan perbatasan bawah). Maka itu panggilanz(r,[R|M])untuk menjalankan mesin aturan Minesweeper, yang (dengan pola panggilan ini) menjadi generator yang hanya menghasilkan papan yang valid. Pada titik ini, dewan masih dinyatakan sebagai serangkaian kendala, yang berpotensi canggung bagi kita; kita mungkin dapat memiliki satu set kendala yang dapat mewakili lebih dari satu papan. Selain itu, kami belum menentukan di mana saja bahwa setiap kotak berisi paling banyak satu tambang. Dengan demikian, kita perlu secara eksplisit "menciutkan bentuk gelombang" dari setiap kotak, yang mengharuskannya untuk menjadi tambang (tunggal) atau bukan tambang, dan cara termudah untuk melakukannya adalah dengan menjalankannya melalui parser mundur ( var(V)pada kasing q(63,V)dirancang untuk mencegah ?kasing mundur, dan dengan demikian merentang papan memaksa agar diketahui sepenuhnya). Akhirnya, kami mengembalikan papan yang diurai darim; mdengan demikian menjadi generator yang mengambil papan yang sebagian tidak dikenal dan menghasilkan semua papan yang diketahui konsisten dengannya.

Itu benar-benar cukup untuk menyelesaikan Minesweeper, tetapi pertanyaannya secara eksplisit meminta untuk memeriksa apakah ada satu solusi, daripada menemukan semua solusi. Karena itu, saya menulis predikat tambahan syang hanya mengubah generator mmenjadi satu set, dan kemudian menyatakan bahwa set tersebut memiliki tepat satu elemen. Ini berarti bahwa sakan mengembalikan kebenaran ( yes) jika memang ada satu solusi, atau falsey ( no) jika ada lebih dari satu atau kurang dari satu.

dbukan bagian dari solusi, dan tidak termasuk dalam bytecount; itu adalah fungsi untuk mencetak daftar string seolah-olah itu adalah matriks, yang memungkinkan untuk memeriksa papan yang dihasilkan oleh m(secara default, GNU Prolog mencetak string sebagai daftar kode ASCII, karena itu memperlakukan keduanya secara sinonim; format ini cukup sulit dibaca). Ini berguna selama pengujian, atau jika Anda ingin menggunakan msebagai pemecah Minesweeper praktis (karena menggunakan pemecah kendala, ini sangat efisien).

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

Contoh penggunaan: g "1121 1??* 12?* 0122"-> True.

Cara kerjanya: buat daftar semua papan yang mungkin dengan ?diganti dengan salah satu *atau !( !artinya abaikan nanti). Ini dilakukan melalui mapM c, tetapi sebelum kita menambahkan dan menambahkan sekelompok spasi ke string input sehingga pengindeksan kami tidak akan keluar dari jangkauan. Untuk setiap papan seperti itu periksa apakah itu papan yang valid dengan mengulang semua elemen (indeks j) dan jika itu angka ( d>'/') juga atas tetangganya (indeks n, m), hitung *dan bandingkan dengan angka. Akhirnya periksa panjang daftar papan yang valid.

Mathematica, 214 192 190 180 176 174 168 165 byte

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

Berisi U + F4A1 (Penggunaan pribadi). Fungsi tanpa nama ini menemukan semua kombinasi yang mungkin untuk "?"(yaitu mengganti semua "?"dengan "*"atau 0) dan memeriksa apakah hanya ada satu solusi yang valid.

Penjelasan

b="*";

Setel bke "*".

!FreeQ[#,q="?"]

Setel qke string "?". Periksa apakah ada "?"di input.

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

Jika True...

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

Ganti kemunculan pertama dari q(= "?") dengan b(= "*") atau 0(yaitu dua output), dan terapkan kembali seluruh fungsi.

Jika False...

#~ArrayPad~1

Pad input dengan satu layer 0.

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

Partisi input ke dalam matriks 3 x 3 dengan offset 1. Untuk setiap partisi, terapkan fungsi sedemikian rupa sehingga jika nilai tengahnya adalah b(= "*"), outputnya adalah b(= "*"), dan jika nilai tengahnya tidak b(= "*"), output adalah jumlah b(= "*") pada input. Langkah ini mengevaluasi kembali semua sel angka.

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

Dari semua hasil, cari yang cocok dengan input

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

Periksa apakah input panjang 1.

Perl, 215 byte

213 byte kode + -p0bendera (2 byte).

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

Gagasan kode adalah untuk menguji setiap kemungkinan dan melihat apakah ada satu dan hanya satu yang mengarah ke papan penuh yang valid.

Lebih mudah dibaca, kode ini terlihat seperti:

/.*/ ; $ c = "@ +" ; # hitung ukuran garis. 
$ _ = A x $ c . "\ n $ _" . A x $ c ; # tambahkan baris "A" di awal dan yang lain di akhir. 
s / ^ | $ / A / mg ; # tambahkan "A" di awal dan akhir setiap baris.                     

# The funcion yang benar-benar memecahkan masalah sub t { saya $ _ = pop ; # Dapatkan parameter, simpan dalam $ _ (argumen default untuk regex). if ( / \? / ) { # jika ada karakter tidak dikenal lainnya untuk $ i ( 0 .. 8 , "*" ) { # coba setiap kemungkinan 
            t ( s / \? / $ i / r ) # panggilan rekursif di mana char pertama yang tidak diketahui telah diganti } } else {
 
     
        
            
        
     # tidak ada lagi karakter yang tidak dikenal, jadi di sini kami memeriksa apakah papan tersebut valid 
        $ r = 1 ; # if r == 1 di akhir, maka board itu valid, kalau tidak itu bukan untuk $ i ( / \ d / g ) { # untuk setiap angka yang hadir dari board # regex berikut memeriksa apakah ada angka yang dikelilingi oleh salah satu tambang yang terlalu banyak atau terlalu sedikit. # (cara kerjanya: magic!) 
         $ r & =! /(...)[^V[{$c}(.$i.)[^V[{$c}(...)(??{"$1$2$3"=~y%*%%! = $ i? "": R}) / } 
        $ e + = $ r # Menambah jumlah papan yang valid. } } 
t $ _ ;  
          
            
            
             
        
    
 # Panggil fungsi sebelumnya 
$ _ = $ e == 1 # Memeriksa apakah hanya ada satu papan yang valid ($ _ dicetak secara implisit berkat flag -p). 

Tentang regex di tengah:

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

Perhatikan bahwa [^V]kepanjangan dari "karakter apa saja, termasuk \ n".
Jadi idenya adalah: 3 char pada satu baris, kemudian 3 pada berikutnya (dengan $idi tengah), kemudian 3 pada berikutnya. 3 kelompok dari 3 angka tersebut disejajarkan, terima kasih [^V]{$c}dan nomor yang kami minati berada di tengah.
Dan kemudian, "$1$2$3"=~y%*%%hitung jumlah *(bom) di antara 9 karakter tersebut: jika berbeda dari itu $i, kami menambahkan string kosong untuk mencocokkan ( ""=> pencocokan instan, regex mengembalikan true), jika tidak, kami memaksakan kegagalan dengan mencoba mencocokkan R( yang tidak bisa berada di string).
Jika pertandingan regex, maka dewan tidak valid, jadi kami mengatur $runtuk 0dengan $r&=!/.../.
Dan itu sebabnya kami menambahkan beberapaAdi mana-mana di sekitar setiap baris: jadi kita tidak perlu khawatir tentang tepi kasus angka-angka yang berada di dekat tepi papan: mereka akan memiliki Atetangga, yang bukan tambang (tentu saja, kira-kira arang mana pun bisa bekerja, Saya memilih A).

Anda dapat menjalankan program dari baris perintah seperti itu:

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"

Kompleksitasnya tidak mungkin terburuk: itu adalah di O(m*9^n)mana njumlah ?di papan tulis, dan mjumlah sel di papan tulis (tanpa menghitung kompleksitas regex di tengah, yang mungkin sangat buruk). Di mesin saya, ini bekerja cukup cepat hingga 4 ?, dan mulai lebih lambat 5, butuh beberapa menit selama 6, dan saya tidak mencoba untuk jumlah yang lebih besar.

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

Jika semua masukan diharapkan berlaku - yang dengan setidaknya 1 solusi - maka saya dapat menyimpan byte berubah s==1dengans<2

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

Uji

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 byte

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

Cobalah online!

Meskipun op mengatakan "input akan selalu persegi panjang, memiliki setidaknya satu solusi", sampel 3 tidak cocok, jadi saya masih membutuhkan 1 solusi, bukan <2 solusi

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