Minesweeper Solver

34

Kami sudah membuat bidang Minesweeper , tetapi seseorang benar-benar harus menyapu ranjau yang dihasilkan sebelum PCG meledak!

Tugas Anda adalah menulis Solver Minesweeper yang kompatibel dengan versi yang sedikit dimodifikasi dari solusi yang diterima dari "Working Minesweeper" (tindakan dipisahkan oleh spasi untuk memungkinkan bidang yang lebih besar).

Input: Bidang Minesweeper, bidang yang dipisahkan oleh spasi. Baris pertama menunjukkan jumlah total tambang.

  • x: Tidak tersentuh
  • !: Bendera
  • Digit: Jumlah tambang di sekitar bidang itu

Contoh: 

10
0 0 1 x x x x x
0 0 2 x x x x x
0 0 2 ! x x x x
0 0 1 2 x x x x
0 0 0 1 x x x x
1 1 0 2 x x x x
x 1 0 2 x x x x
1 1 0 1 x x x x

Output: Langkah Anda berikutnya dalam format action row column(mulai dari nol)

Tindakan yang Valid:

  • 0: Buka
  • 1: Tempatkan bendera

Contoh:

0 1 2

Aturan:

  • Anda menulis program lengkap yang mengambil bidang tunggal sebagai input (baik STDIN atau argumen baris perintah) dan mengeluarkan satu tindakan (STDOUT). Karenanya, Anda tidak dapat menyimpan status, kecuali untuk !.
  • Pilihan Anda harus mengikuti peluang terbaik untuk bertahan hidup. (Yaitu jika ada 100% langkah aman, ambillah)
  • Ini adalah kode-golf ; solusi terpendek (dalam UTF-8 byte) menang

Tes:

Tes ini melayani tujuan pengujian untuk situasi yang jelas umum; program Anda harus bekerja untuk setiap bidang tes.

Di:

4
x x x x
1 2 x x
0 1 2 x
0 0 1 x

Keluar (semua ini):

1 1 2
0 0 2
0 1 3

Di:

2
x x x
1 ! x
1 1 x

Keluar (semua ini):

0 0 0
0 0 1
0 1 2
0 2 2
1 0 2

Di:

10
x x x x x x x x
1 3 3 x x x x x
0 1 ! 3 3 4 x x
0 2 3 ! 2 3 x x
0 1 ! 2 2 ! x x

Keluar (semua ini):

1 1 5
1 0 2

Di:

2
x x x
2 3 1
! 1 0

Keluar (semua ini):

0 0 1
1 0 0
1 0 2
code-golf game minesweeper TimWolla
sumber
Bagus! 1) Mungkin untuk menguji seseorang harus menulis uji harness: diberi bidang, itu mencetak setiap langkah yang diambil, dan apakah program menang. Program harus menang di peta tanpa ambiguitas. 2) Saya ingin tahu apakah ada yang akan menggunakan aksi flag. Sepertinya itu tidak perlu.
Claudiu
Untuk tes pertama. Mengapa Anda bisa pindah ke 0 0 2atau 0 1 3. Saya tidak bisa melihat bagaimana salah satu dari mereka dianggap aman. (Saya tidak harus cukup baik di kapal penyapu ranjau ...)
FDinoff
1
Mungkin Fatau Pterlihat lebih baik daripada bendera !:)
VisioN
1
@JonathanVanMatre Lapangan ini kosong, tetapi dijamin pembukaan pertama Anda bukan milikku, karena tambang ditempatkan setelah klik pertama :)
TimWolla
2
Fakta menyenangkan: Hanya ada sejumlah papan terbatas yang tersedia (setidaknya dalam versi XP, yang merupakan versi kanonik di kancah kompetisi). Papan bergeser saat Anda mengklik tempat pertama untuk memastikan bahwa Anda tidak mengklik tambang, tetapi selain itu sudah memutuskan papan mana yang akan Anda gunakan.
undergroundmonorail

Jawaban:

17

Mathematica

Masih belum golf. Membutuhkan lebih banyak pekerjaan pada format I / O.

t = {{0, 0, 1, x, x, x, x, x}, {0, 0, 2, x, x, x, x, x}, {0, 0, 2, F, x, x, x, x}, 
     {0, 0, 1, 2, x, x, x, x}, {0, 0, 0, 1, x, x, x, x}, {1, 1, 0, 2, x, x, x, x}, 
     {x, 1, 0, 2, x, x, x, x}, {1, 1, 0, 1, x, x, x, x}};
(*Sqrt[2] is  1.5*)
c = Sequence; p = Position;
nums = p[t, _?NumberQ];
fx = Nearest[p[t, x]];
flagMinus[flag_] := If[Norm[# - flag] < 1.5, t[[c @@ #]]--] & /@ nums
flagMinus /@ p[t, F];
g@x_List := Tr[q[#] & /@ x]
eqs = MapIndexed[t[[c @@ (nums[[#2]][[1]])]] == g[#1] &, (fx[#, {8, 1.5}] & /@nums)];
vars = Union@Cases[eqs, _q, 4];
s = Solve[Join[eqs, Thread[0 <= vars < 2]], vars, Integers];
res = (Transpose@s)[[All, All, 2]];
i = 1; plays = Select[{i++, #[[1]], Equal @@ #} & /@ res, #[[3]] &];
Flatten /@ ({#[[2]] /. 1 -> F, List @@ vars[[#[[1]]]] - 1} & /@ plays)

(*
{{0, 0, 3}, {F, 1, 3}, {F, 2, 4}, {0, 3, 4}, {0, 4, 4}, 
 {F, 5, 4}, {F, 6, 0}, {F, 6, 4}, {0, 7, 4}}
*)

Edit: Bonus Track

Saya membuat taman bermain interaktif yang menghitung probabilitas bom dengan menghitung semua solusi yang mungkin untuk konfigurasi yang diberikan:

Grafik Mathematica

Petunjuk untuk mengujinya tanpa memasang Mathematica:

  1. Unduh http://pastebin.com/asLC47BW dan simpan sebagai * .CDF
  2. Dowload lingkungan CDF gratis dari Wolfram Research di https://www.wolfram.com/cdf-player/ (bukan file kecil)

Slider mengubah dimensi papan. Ini hanya program samar, tidak sepenuhnya diuji, silakan laporkan bug apa pun. Saya belum menerapkan fitur "jumlah total bom yang tersedia di kapal". Diasumsikan tak terbatas.

Belisarius
sumber