17
\$\begingroup\$

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.

Counting 3BV

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)

Solved Minesweeper board Clicks required


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
\$\endgroup\$
  • \$\begingroup\$ Is an array of integers okay as input? Each integer codes one row. \$\endgroup\$ – Karl Napf Jun 8 '16 at 19:21
  • \$\begingroup\$ @KarlNapf No. The input should be recognizable as a board as shown. \$\endgroup\$ – mbomb007 Jun 8 '16 at 20:20
  • \$\begingroup\$ Could you provide more test cases, possibly including the input based on the displayed images, and maybe a max dimensions test case? \$\endgroup\$ – miles Jun 8 '16 at 20:47
15
\$\begingroup\$

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.

enter image description here

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.

\$\endgroup\$
9
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

MATL, 24 22 21 bytes (non-competing)

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 
\$\endgroup\$
  • \$\begingroup\$ Noncompeting why? \$\endgroup\$ – CalculatorFeline May 28 '17 at 17:05
  • 1
    \$\begingroup\$ @CalculatorFeline Unfortunately the bwlabeln functionality was introduced to MATL after the challenge was posted. \$\endgroup\$ – Suever May 28 '17 at 17:13

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.