34
\$\begingroup\$

We already generated Minesweeper fields, but someone really has to sweep those generated mines before PCG blows up!

Your task is to write a Minesweeper Solver that is compatible with a slightly modified version of the accepted solution of “Working Minesweeper” (actions are separated by spaces to allow for larger fields).

Input: A Minesweeper field, fields separated by spaces. The first line denotes the total number of mines.

  • x: Untouched
  • !: Flag
  • Digit: Number of mines around that field

Example:

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: Your next step in the format action row column (starting at zero)

Valid Actions:

  • 0: Open it
  • 1: Place a flag

Example:

0 1 2

Rules:

  • You write a complete program that takes a single field as input (either STDIN or command line arguments) and outputs a single action (STDOUT). Therefore, you cannot save states, except for !.
  • Your choice must follow the best odds for survival. (i.e. if there is a 100% safe move, take it)
  • This is ; the shortest solution (in UTF-8 bytes) wins

Tests:

These tests serve the purpose of testing for common clear situations; your program must work for every test field.

In:

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

Out (any of these):

1 1 2
0 0 2
0 1 3

In:

2
x x x
1 ! x
1 1 x

Out (any of these):

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

In:

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

Out (any of these):

1 1 5
1 0 2

In:

2
x x x
2 3 1
! 1 0

Out (any of these):

0 0 1
1 0 0
1 0 2
\$\endgroup\$
  • \$\begingroup\$ Nice! 1) Perhaps for testing someone should write a test harness: given a field, it prints each step taken, and whether the program wins. The program should win on maps without any ambiguity. 2) I wonder if anyone will use the flag action. Seems like it should never be necessary. \$\endgroup\$ – Claudiu Mar 14 '14 at 0:42
  • \$\begingroup\$ For the first test. Why are you able to move to 0 0 2 or 0 1 3. I can't see how either one of the those would be considered safe. (I must not be good enough at minesweeper...) \$\endgroup\$ – FDinoff Mar 14 '14 at 1:44
  • 1
    \$\begingroup\$ Possibly F or P looks better flag than ! :) \$\endgroup\$ – VisioN Mar 14 '14 at 10:42
  • 1
    \$\begingroup\$ @JonathanVanMatre The field is a blank one, but it is guaranteed your first opening is not a mine, as the mines are placed after the first click :) \$\endgroup\$ – TimWolla Mar 14 '14 at 17:13
  • 2
    \$\begingroup\$ Fun fact: There are only a finite number of boards available (at least in the XP version, which is the canonical one in the competitive scene). The board is shifted around as you click the first spot to ensure that you're not clicking a mine, but other than that it's already decided which board you'll use. \$\endgroup\$ – undergroundmonorail Mar 15 '14 at 8:14
17
+250
\$\begingroup\$

Mathematica

Still not golfed. Needs some more work on I/O formats.

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

I made up an interactive playground that calculates bomb probabilities by calculating all possible solutions for a given configuration:

Mathematica graphics

Instructions for testing it without Mathematica installed:

  1. Download http://pastebin.com/asLC47BW and save it as *.CDF
  2. Dowload the free CDF environment from Wolfram Research at https://www.wolfram.com/cdf-player/ (not a small file)

The slider changes the board dimensions. This is just a sketchy program, not fully tested, please report any bugs. I haven't implemented a "total number of available bombs on board" feature. It's assumed infinite.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.