Calculate the 3BV of a Minesweeper Board

Question

The 3BV of a Minesweeper board represents the minimum number of left clicks required to solve the board if you already know the solution. It stands for "Bechtel's Board Benchmark Value". Here's his site explaining it.

Below is a solved Minesweeper board. The flags indicate mines; tiles without mines indicate the count of adjacent mines, including diagonally, except that tiles that should have "0" are left blank instead. The image shows which tiles need to be clicked in order to solve the board.

Clicks counted towards the 3BV are:

• One for each flood-filled area of blank tiles (zero mines adjacent) and their non-blank neighbors.
• One for each other non-mine tile.

---

Another Example (3BV = 39)

---

Given a 2D array of values, 0 for clear and 1 for a mine (or a boolean), return the 3BV.

A board's dimensions will be at least 8x8, and at most 24x30, inclusive. Your program should handle all possible boards, not just the examples.

Note: A board will never contain only mines.

Example I/O:

[[0,0,0,0,0,0,0,0],
[0,0,0,1,0,0,0,0],
[0,0,0,1,0,0,1,0],
[0,1,0,0,1,0,0,0],
[0,0,1,0,0,0,0,1],
[0,0,0,1,0,0,0,0],
[0,0,0,0,0,0,1,0],
[0,0,0,0,0,0,0,1]]

23

[[0,0,1,0,0,0,1,1,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,0,1,0,0,0],
[0,0,0,0,0,1,1,1,0,0,1,0,0,0,0,0,0,1,0,0,1,0,1,1,0,0,0,0,0,0],
[0,1,0,0,0,0,1,0,0,1,0,1,0,0,1,0,0,1,0,1,1,0,0,0,1,0,1,0,1,0],
[0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,1,0,0,0],
[0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0],
[0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,1,1,0,1],
[0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,1,1],
[0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0],
[0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0],
[0,0,1,0,0,0,1,0,0,1,0,0,1,0,0,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0],
[1,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,1,0,0,0,0,1,1],
[0,0,0,0,0,0,0,0,0,0,1,0,0,1,0,0,0,1,1,0,1,1,0,0,0,0,1,1,0,0],
[0,0,0,0,0,1,0,1,1,0,0,0,0,0,0,1,0,1,1,0,0,0,1,0,0,0,1,1,0,0],
[0,1,1,1,0,0,0,0,0,1,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0],
[0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,1,0,0,1,0,0,1,0,0,0,0,1,0,0,0],
[0,0,1,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,1,1,0,0,0,0,0,0,0]]

187

Answer 1

MATLAB, 92 90 86 83 79 74 72 bytes

x=input('');I=@(x)~imdilate(x,ones(3));[C,N]=bwlabel(I(x));nnz(I(C)-x)+N

This solution accepts the input in the form of a 2D matrix of 0's and 1's and will display the 3BV value for the provided input.

Here is slightly modified demo in Octave for those of you without MATLAB.

Explanation

The input matrix is dilated using a 3 x 3 matrix of 1's and then inverted (using ~) which identifies all of the points that do not have mines as neighbors (1) or do (0). To determine the number of connected regions, we use bwlabel to label each connected region of 1's. The first output is the label matrix (0 where the input was zero and any value in the range 1...N where there was a 1 in the input where N is the index of the connected group that it belongs to). The second output is the number of regions (the number of clicks required to open them). The result of the bwlabel is shown in the image on the left.

We expand the first output of bwlabel using imdilate (all non-zeros are expanded) using a 3 x 3 matrix of 1's. The result is shown in the image in the middle.

To determine the remaining clicks, we then count the squares that are not in this expanded region (~imdilate()) and not a mine (-x) (white squares in the image on the right) and add this to the total number of open regions (the number of different colors in the image on the left) to get the 3BV.

Answer 2

Octave, 86 84 79 66 bytes

@(x)nnz(~imdilate(c=imerode(~x,o=ones(3)),o)-x)+max(bwlabel(c)(:))

This solution creates an anonymous function named ans which can then be passed a 2D matrix of 0's and 1's. The logic is the same as my MATLAB answer but uses a few tricks that Octave has to offer to save space.

This solution requires that the image package is installed.

Demo here

Answer 3

MATL, 24 22 21 bytes

1 byte saved thanks to @Luis

4Y6Z+~l2#ZIw7MZ+G+~z+

Try it at MATL Online

Explanation

Again, this is similar to my MATLAB and Octave answers to this question.

        % Implicitly grab input array
4Y6     % Push the literal [1 1 1; 1 1 1; 1 1 1] to the stack
Z+      % Perform 2D convolution of the input with this array
~       % Negate the result
l2#ZI   % Call bwlabeln which dilates each open region and the second output
        % returns the number of open regions
w       % Flip the top two stack elements
7M      % Push the literal [1 1 1; 1 1 1; 1 1 1] to the stack again
Z+      % Perform 2D convolution
G+      % Explicitly grab the input and add it to the result
~z      % Count the number of 0's in the result (the remaining number of clicks)
+       % Add the total number of remaining clicks to the number of open regions