Minesweeper Solver

34

7

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

TimWolla

Posted 2014-03-13T22:07:42.003

Reputation: 1 878

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. – Claudiu – 2014-03-14T00:42:47.277

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...) – FDinoff – 2014-03-14T01:44:43.243

@FDinoff Imagine a flag standing at 1 2, the two 2s would have 1 mine left. Because the mine for the two 1s at the borders touches the 2s as well there neither can be a mine at 0 2 nor at 1 3. – TimWolla – 2014-03-14T02:08:38.280

There are situations where you can predict a move with 100% accuracy if you know the number of mines but otherwise can only guess. Are we provided the total number of mines or should we neglect this case? – Howard – 2014-03-14T07:25:01.947

@Howard I missed that one. I'll edit in a minute. – TimWolla – 2014-03-14T10:28:27.133

1Possibly F or P looks better flag than ! :) – VisioN – 2014-03-14T10:42:45.980

Although it can be easily inferred from the examples, it still might be helpful to explicitly note that the board is zero-indexed. Also, does "best chance of survival" apply to the opening move? I haven't done the math yet, but I suspect all positions are not equal. – Jonathan Van Matre – 2014-03-14T14:57:54.410

@JonathanVanMatre It is noted: “(starting at zero)”. It does not apply to the opening move (In fact: The Windows Minesweeper generates the field after the opening move). – TimWolla – 2014-03-14T15:07:50.493

@TimWolla That shows how long it has been since I played WinMinesweeper. Last time I used it, you started with a blank field. Sorry I missed the parenthetical...my brain must have said "It's in parens, it's not important." This is why I would be terrible at LISP. :) – Jonathan Van Matre – 2014-03-14T15:10:47.050

1@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 :) – TimWolla – 2014-03-14T17:13:01.050

2Fun 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. – undergroundmonorail – 2014-03-15T08:14:03.817

Answers

17

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.

Dr. belisarius

Posted 2014-03-13T22:07:42.003

Reputation: 5 345

Asked: 2014-03-13T22:07:42.003

Viewed: 2 687 times

Active: 2014-12-15T19:44:18.793