Can I sweep the mines?

Question

Minesweeper is a popular puzzle game where you must discover which tiles are "mines" without clicking on those tiles. Instead, you click on nearby tiles to reveal the number of adjacent mines. One downside about the game is that it is possible to end up in a scenario where there are multiple valid answers and you may only guess. For example, take the following board:

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

In this format, a number represents the number of adjacent mines, an * represents a known mine, and a "?" represents a potential mine. The unfortunate thing about this particular puzzle is that there are four distinct and valid potential solutions:

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*

This means the board is unsolvable. Here is an example of a solvable board:

1121
1??*
12?*
0122

This board is solvable because there is only one possible valid solution:

1121
1*4*
12**
0122

Your task is to write either a program or function that takes a valid minesweeper board and determines if it is solvable or not. By "valid minesweeper board", I mean that the input will always be rectangular, have at least one solution, and not contain any invalid characters.

Your input may be an array of characters, an array of strings, a string containing newlines, etc. The output must be a truthy value if it is solvable and a falsy value if it is not. I am not extremely worried about performance, but your solution must theoretically work for any size input.

As usual, standard loopholes apply and the shortest solution in bytes wins!

Examples:

The following examples are all solvable:

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

The following examples are all unsolvable:

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

Answer 1

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

An extra predicate that may be useful for testing (not part of the submission):

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

Prolog's definitely the right language for solving this task from the practical point of view. This program pretty much just states the rules of Minesweeper and lets GNU Prolog's constraint solver solve the problem from there.

z and i are utility functions (z does a sort of fold-like operation but on sets of three adjacent elements rather than 2; i transposes 3 lists of n elements into a list of n 3-tuples). We internally store a cell as x/y, where x is 1 for a mine and 0 for a nonmine, and y is the number of adjacent mines; c expresses this constraint on the board. r applies c to every row of the board; and so z(r,M) checks to see if M is a valid board.

Unfortunately, the input format required to make this work directly is unreasonable, so I also had to include a parser (which probably accounts for more code than the actual rules engine, and most of the time spent debugging; the Minesweeper rules engine pretty much worked first time, but the parser was full of thinkos). q converts a single cell between a character code and our x/y format. l converts one line of the board (leaving one cell that's known to be not a mine, but with an unknown number of neighbouring mines, at each edge of the line as a border); p converts the entire board (including the bottom border, but excluding the top one). All of these functions can be run either forwards or backwards, thus can both parse and pretty-print the board. (There's some annoying wiggling around with the third argument to p, which specifies the width of the board; this is because Prolog doesn't have a matrix type, and if I don't constrain the board to be rectangular, the program will go into an infinite loop trying progressively wider borders around the board.)

m is the main Minesweeper solving function. It parses the input string, generating a board with a correct border (via using the recursive case of p to convert most of the board, then calling the base case directly to generate the top border, which has the same structure as the bottom border). Then it calls z(r,[R|M]) to run the Minesweeper rules engine, which (with this call pattern) becomes a generator generating only valid boards. At this point, the board is still expressed as a set of constraints, which is potentially awkward for us; we could perhaps have a single set of constraints which could represent more than one board. Additionally, we haven't yet specified anywhere that each square contains at most one mine. As such, we need to explicitly "collapse the waveform" of each square, requiring it to be specifically either a (single) mine or a nonmine, and the easiest way to do this is to run it through the parser backwards (the var(V) on the q(63,V) case is designed to prevent the ? case running backwards, and thus deparsing the board forces it to be fully known). Finally, we return the parsed board from m; m thus becomes a generator which takes a partially unknown board and generates all the known boards consistent with it.

That's really enough to solve Minesweeper, but the question explicitly asks to check whether there's exactly one solution, rather than to find all solutions. As such, I wrote an extra predicate s which simply converts the generator m into a set, and then asserts that the set has exactly one element. This means that s will return truthy (yes) if there is indeed exactly one solution, or falsey (no) if there is more than one or less than one.

d is not part of the solution, and not included in the bytecount; it's a function for printing a list of strings as though it were a matrix, which makes it possible to inspect the boards generated by m (by default, GNU Prolog prints strings as a list of ASCII codes, because it treats the two synonymously; this format is fairly hard to read). It's useful during testing, or if you want to use m as a practical Minesweeper solver (because it uses a constraint solver, it's highly efficient).

Answer 2

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

Usage example: g "1121 1??* 12?* 0122" -> True.

How it works: make list of all possible boards with the ? replaced by either * or ! (! means ignore later). This is done via mapM c, but before we prepend and append a bunch of spaces to the input string so that our indexing won't be out of range. For each such board check if it's a valid board by looping over all elements (index j) and if it's a number (d>'/') also over its neighbors (index n, m), count the * and compare to the number. Finally check the length of the list of valid boards.

Answer 3

Perl, 215 bytes

213 bytes of code + -p0 flags (2 bytes).

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

The idea of the code is to test every possibility and see if there is one and only one that leads to a fully filled board that is valid.

More readable, the code looks like:

/.*/;$c="@+";           # count the size of a line.
$_=A x$c."\n$_".A x$c;  # add a line of "A" at the begining and another at the end.
s/^|$/A/mg;        # add a "A" at the start and the end of each line.

# The funcion that actually solves the problem
sub t { 
    my $_= pop; # Get the parameter, store it in $_ (default argument to regex).
    if (/\?/) {  # if there is another unknown char.
        for $i(0..8,"*") { # try every possibility
            t(s/\?/$i/r)  # reccursive call where the first unknown char has been replaced
        }
    } else { # no more unknown character, so here we check if the board is valid
        $r=1;  # if r == 1 at the end, then the board is valid, otherwise it's not
        for $i (/\d/g) { # for each number present of the board
            # the following regex checks if there is a number is surrounded by either 
            # too much or too little mines.
            # (how it works: magic!)
         $r&=!/(...)[^V]{$c}(.$i.)[^V]{$c}(...)(??{"$1$2$3"=~y%*%%!=$i?"":R})/ 
        }
        $e+=$r # Increment the number of valid boards.
    }
}
t$_; # Call the previous function
$_=$e==1 # Checks if there is only one valid board ($_ is implicitly printed thanks to -p flag).

About the regex in the middle :

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

Note that [^V] just stands for "any character, including \n".
So the idea is: 3 char on a line, then 3 on the next (with $i in the middle), then 3 on the next. those 3 groups of 3 numbers are aligned, thanks to [^V]{$c} and the number we're interested into is in the middle.
And then, "$1$2$3"=~y%*%% counts the number of * (bombs) among those 9 characters: if it's different from $i, we add an empty string to match ("" => instant matching, the regex returns true), otherwise, we force a fail by trying to match R (which can't be in the string).
If the regex matches, then the board isn't valid, so we set $r to 0 with $r&=!/.../.
And that's why we add some A everywhere around each line: so we don't have to worry about edges cases of numbers that are near the edges of the board: they'll have A as neighbors, which aren't mines (of course, roughly any char could have work, I chose A).

You can run the program from the command line like that :

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"

The complexity couldn't be worst: it's O(m*9^n) where n is the number of ? on the board, and m is the number of cells on the board (without counting the complexity of the regex in the middle, which is probably pretty bad). On my machine, it works pretty fast for up to 4 ?, and starts to be slower 5, takes a few minutes for 6, and I didn't try for larger numbers.

Answer 4

Mathematica, 214 192 190 180 176 174 168 165 bytes

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

Contains U+F4A1 (Private use). This unnamed function finds all possible combinations for "?" (i.e. replacing all "?"s with "*" or 0) and checks whether there is only one valid solution.

Explanation

b="*";

Set b to "*".

!FreeQ[#,q="?"]

Set q to the string "?". Check whether there is "?" in the input.

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

---

If True...

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

Replace the first occurrence of q(="?") with b(="*") or 0 (i.e. two outputs), and apply the entire function again.

---

If False...

#~ArrayPad~1

Pad the input with one layer of 0.

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

Partition the input into 3 x 3 matrices with offset 1. For each partition, apply a function such that if the middle value is b(="*"), the output is the b(="*"), and if the middle value is not b(="*"), the output is the number of b(="*") in the input. This step re-evaluates all the number cells.

---

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

From all of the results, find the ones that match the input

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

Check whether the input is length 1.

Answer 5

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

If all input is expected to be valid - that is with at least 1 solution - then I can save a byte changing s==1 with s<2

Less golfed

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>

Answer 6

JavaScript (Node.js), 167 bytes

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

Try it online!

Though op say "input will always be rectangular, have at least one solution", false sample 3 doesn't match, so I still require 1 solution, not <2 solution

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

Answer 7

APL (Dyalog Unicode), 78 bytes^SBCS

{1=+/∧/∘,¨{⍵[1;1]∊' *',⍕+/'*'=,⍵}⌺3 3¨(⊂⍵){' *'[⍵]@c⊢⍺}¨,⍳2⊣¨c←⍸'?'=⍵}(⊢↑⍨2⌈⍴)

Try it online!

A function that takes a 2-dimensional character matrix as its right argument, and gives 1 if the board is solvable (has unique solution) and 0 otherwise.

How it works

This is a straightforward implementation of the challenge description. Dimension extension is needed because the stencil operator isn't happy with too small arrays.

Ungolfed version:

sol←{
  coords←⍸'?'=⍵
  masks←,⍳2⊣¨coords
  replace←{' *'[⍺]@coords⊢⍵}
  check←∧/∘,{⍵[1;1]∊' *',⍕+/'*'=,⍵}⌺3 3
  1=+/masks(check replace)¨⊂⍵
}(⊢↑⍨2⌈⍴)

With comments:

sol←{  ⍝ ⍵←minesweeper board as a character matrix
  ⍝ 2D coordinates of '?'
  coords←⍸'?'=⍵

  ⍝ possible combinations of blank as 0 and mine as 1
  masks←,⍳2⊣¨coords
          2⊣¨coords  ⍝ (≢coords) copies of 2
        ,⍳           ⍝ cartesian product of 0..n-1 for each n in the above

  ⍝ create a board with selected mines
  replace←{' *'[⍺]@coords⊢⍵}
          {                }  ⍝ a function
                         ⊢⍵   ⍝ take the array ⍵
                  @coords     ⍝ replace the items at given coords
           ' *'[⍺]            ⍝ ... into blanks and mines as specified
                              ⍝ by boolean array ⍺

  ⍝ test if the complete board is valid
  check←∧/∘,{⍵[1;1]∊' *',⍕+/'*'=,⍵}⌺3 3
            {                     }⌺3 3  ⍝ for each 3x3 subarray (including ones centered at the edges)
                         ⍕+/'*'=,⍵       ⍝ s←count the mines and cast to string
             ⍵[1;1]∊' *',                ⍝ check if the center is one of blank, mine, or s
        ∧/∘,                             ⍝ reduce by AND for all subarrays

  ⍝ for all combinations, check if the board has unique solution
  1=+/masks(check replace)¨⊂⍵
      masks(      replace)¨⊂⍵  ⍝ generate all possible boards
            check              ⍝ check each board if it is a valid solution
  1=+/                         ⍝ check that there's exactly one valid solution in total

}(⊢↑⍨2⌈⍴)  ⍝ extend each dimension to have at least length 2 before calling main function
       ⍴   ⍝ dimensions
     2⌈    ⍝ max(n,2) for each dimension
  ⊢↑⍨      ⍝ extend the input to have ^ dimension; fill extended cells with blank